Оптимізація сіткових графіків

⇐ ПредыдущаяСтр 3 из 3

Оптимізація сіткових графіків проводиться з метою поліпшення плану комплексу робіт. Така задача виникає, коли критичний шлях не вкладається в необхідні або задані терміни виконання і необхідно вкладення додаткових ресурсів або перерозподіл наявних. Інше завдання полягає в тому, що якщо час виконання всього комплексу робіт укладається в заданий термін з надлишком, то, розтягнувши деякі роботи, ми можемо заощадити деякі засоби.

При цьому можна виділити наступні основні принципи оптимізації:

1) форсування критичних робіт, при якому змінюється довжина критичного шляху;

2) послідовне виконання робіт замінюється паралельним;

3) перерозподіл ресурсів між роботами критичного і некритичного шляхів;

4) організаційні та технологічні зміни виконання робіт.

Дамо постановку деяких завдань оптимізації в формульного запису.

Завдання 1.Ооптимізація з вкладенням додаткових коштівКомплекс складається з робіт a₁, а₂,..., а_n з часом виконання t₁, t₂,..., t_n. Відомий критичний шлях

де Т₀ − заданий термін виконання комплексу робіт. Причому підсумовування поширюється на критичні роботи.

Відомо, що вкладення певної суми х додаткових коштів в роботу а_i_, скорочує час виконання з t_i до t_i = f (x) <t_i.

Запитується, які додаткові кошти х₁, х₂,..., х_n слід вкласти в кожну роботу, щоб, по-перше, термін виконання комплексу був не вище заданого Т₀і, по-друге, сума вкладених коштів досягала мінімуму.

Таким чином, потрібно визначити невід'ємні значення змінних x₁, х₂,..., х_n (додаткові вкладення) так, щоб виконувалася умова

де підсумовування виконується за всіма критичними роботами нового шляху (отриманого після перерозподілу коштів і зміни часів), і щоб при цьому загальна сума додаткових вкладень була мінімальна:

У загальному вигляді поставлена задача відноситься до класу задач нелінійного програмування. Однак, якщо обмежитися порівняно невеликими змінами плану (такими, при яких час виконання робіт приблизно лінійно залежить від вкладених додаткових коштів, а критичний шлях не змінюється), поставлена задача стає задачею лінійного програмування і може бути вирішена вже відомими нам способами.

Завдання 2. Оптимізація з перерозподілом наявних коштів Є сукупність робіт а₁, а₂,..., а_n з часом виконання t₁, t₂,..., tn. Час виконання комплексу робіт виражається формулою

На некритичних роботах є деякі резерви часу. Користуючись цими резервами, тобто перекидаючи якісь кошти з некритичних робіт на критичні, можна зменшити час виконання критичних робіт і тим самим термін виконання всього комплексу.

Є певний незмінний запас рухомих засобів В, який розподілено між роботами а₁, а₂,..., а_n так, що кожній роботі відповідає кількість рухомих засобів, рівне відповідно b₁, b₂,..., b_n:

Відомо, що кількість коштів х> 0, зняте з роботи а_i_, збільшує час її виконання з t_i до

а кількість засобів х_i_, вкладене додатково в роботу а_i, зменшує час її виконання до t^”_i= <t_i.

Питається: як треба перерозподілити наявні рухомі засоби В між роботами для того, щоб термін виконання комплексу був мінімальним?

Позначимо x_i − кількість рухомих засобів, перекинутих на роботу а_i (х_i негативно, якщо з роботи знімається якась кількість коштів).

Величини x_i повинні задовольняти обмеженням

. (8. 1)

Природно, що сума коштів, що знімаються з якихось робіт, повинна дорівнювати сумі коштів, що додаються до інших робіт, так що

. (8. 2)

Після перекидання коштів для тих робіт, на які вони перекидаються, новий час буде дорівнювати

а для тих робіт, з яких кошти знімаються, вони будуть рівні

Загальний термін виконання комплексу робіт буде:

, (8. 3)

де перша сума поширюється на всі роботи, на які переносяться кошти, якщо вони входять в критичний шлях;

друга − на всі роботи, з яких переносяться кошти, якщо вони входять в критичний шлях.

Природно вважати, що перенесення засобів має сенс тільки з некритичних робіт на критичні, при цьому не треба забувати, що некритичні роботи можуть переходити в критичні. Цей факт необхідно враховувати при обчисленні Т, коли в обох сумах беруться до уваги критичні роботи.

Отже, перед нами стоїть завдання: знайти такі значення змінних x_i

(i = щоб виконувалися обмеження (8. 1), (8. 2), а функція (8.3) зверталася до мінімум.

Завдання ставиться до класу задач нелінійного програмування навіть у випадку, коли функції f_i и - можуть виявитися лінійними. Істотно нелінійним у функції (69) є те, що значення i, j − номери робіт, самі залежать від x_i. Загальних способів вирішення таких завдань не розроблено, однак для деяких випадків можна скласти алгоритми визначення раціонального рішення.

Завдання 3. Оптимізація сітьових графіків з економією вкладених засобів за рахунок зниження темпів виконання окремих робіт на некритичних шляхах.Є комплекс робіт а₁, а₂,..., а_n з часом виконання t_1, t₂,..., t_n. Для цього комплексу знайдений критичний шлях і встановлено, що мінімальний час виконання комплексу Т <Т₀, де Т_{0 −}заданий термін виконання. Передбачається знизити темпи виконання деяких робіт з тим, щоб термін виконання комплексу довести до заданого значення Т₀; за рахунок цього передбачається отримати економію коштів. Збільшення часу виконання роботи а_i на (тобто доведення часу виконання роботи а_i до t_i + ) вивільняє деякі засоби x_i, які залежать від затримки

Позначимо _i час затримки роботи а_i. Сума часів виконання робіт, що лежать на критичному шляху, не повинна перевищувати Т₀:

Потрібно вибрати такі невід'ємні значення змінних , щоб сума вивільнених коштів досягала максимуму:

Поставлена задача також відноситься до класу задач нелінійного програмування. У випадку, коли мова йде тільки про незначні затримки _i вдається звести її до задачі лінійного програмування (якщо функції f_i близькі до лінійних в діапазоні можливих значень _i, а критичний шлях при затримках не змінюється).

Імовірнісні тимчасові оцінки сітьових моделей

Тимчасові оцінки тривалості виконання окремих робіт комплексу можуть бути детермінованими і імовірнісними. Детермінована оцінка задається одним числом − t_ij.

На практиці оцінки тривалості безлічі робіт не можуть бути визначені однозначно і мають великий невизначеністю. У цьому випадку використовуються імовірнісні оцінки тривалості робіт, розрахунок цих оцінок можна здійснювати двома способами.

Перший спосіб полягає в тому, що час виконання роботи розглядається як безперервна випадкова величина, що заповнює інтервал, обмежений межами, апріорно задається відповідальними виконавцями у вигляді мінімальної (оптимістичній) оцінки тривалості t_min=а і максимальної (неоптимістичні) t_max = b.

Одночасно вони дають і найбільш ймовірну оцінку тривалості робіт t_нв=m

Мінімальна, або оптимістична, оцінка тривалості визначається виходячи з припущення, що роботи будуть виконуватися за найсприятливішого збігу обставин. Це означає, що швидше завершити роботу практично неможливо.

Максимальна, або неоптимістичні, оцінка визначається для самого несприятливого збігу обставин виконання роботи. Ця оцінка передбачає більшу, ніж зазвичай, кількість невдач, зривів, перешкод і т.д. Однак стихійні лиха та нещасні випадки при цьому до числа несприятливих умов не відносяться. Найбільш ймовірна оцінка тривалості визначається для найчастіше зустрічаються умов виконання робіт.

Як правило, характеристики а, b і m визначаються на основі експертних оцінок. За цим величинам розраховується математичне сподівання тривалості роботи

а також дисперсія для тривалості операції

Як показує досвід, визначення оцінки т викликає труднощі у відповідальних виконавців, у той же час визначення оцінок а і b таких ускладнень не викликає, тому в багатьох випадках кращі формули, запропоновані видомим вченим Д. І. Голенко:

З цих формул видно, що чим більший розмах (b-а), тим більше невизначеність, і навпаки.

Другий спосіб охоплює більш загальний випадок, коли характеристики а і b невідомі. Відхилення випадкової величини t_i (часу виконання роботи а_i) від її заздалегідь заданого значення t_i) може бути в обидві сторони, як у велику (запізнення), так і в меншу (випередження).

При цьому виникають наступні запитання:

- яка ймовірність того, що фактичний час виконання комплексу робіт Т не перевершить заданої величини Т₀?

- як слід організувати комплекс робіт для того, щоб величина Т не перевершила заданого Т₀ з досить високою ймовірністю?

Розглянемо перше питання (тим більше, що для відповіді на друге, перш за все, треба відповісти на перше). Припустимо, що часи виконання роботі t_1,t₂,…, tn являють собою випадкові величини з відомими законами розподілу і для простоти будемо вважати, що ці випадкові величини незалежні і щільності їх рівні

Розглянута функція цих випадкових величин − загальний час виконання всього комплексу робіт

Поставлена задача буде вирішена, якщо вдасться знайти функцію розподілу випадкової величини Т:

(8.4)

Тоді підставляючи в неї замість t величину Т₀, ми знайдемо шукану ймовірність.

Укрупнення сітьових моделей

При використанні системи сітьового планування управління великими комплексами робіт виникає потреба в укрупненні деталізованої зведеної сітьової моделі. Це необхідно у разі, коли сітьовий графік представляється на розгляд керівництву, а також коли необхідно усунути надмірну деталізацію і підвищити наочність графіка.

Укрупненням сітьової моделі називається процес створення сітьового графіка, меншою за обсягом, більш загальної за змістом і виконаної за певними правилами.

Процес укрупнення проводиться на основі фактичного матеріалу − первинних сітьових графіків, зшитих в зведену мережу. Причому укрупнення не повинно порушувати логіки графіка, забезпечуючи при цьому уявлення загальної картини розробку об'єкта.

Укрупнення мережі повинно проводитися з дотриманням таких правил:

а) ділянка сіті (група взаємопов'язаних робіт) може бути замети однієї укрупненої роботою, якщо ця ділянка має чітко фіксовані один вхідний і одне вихідна події;

б) не можна вводити в укрупнену сіть будь-які події, яких немає в деталізованої сіті;

в) вхідні і вихідні події для мереж різних рівнів повинні мати однакові визначення;

г) укрупнювати слід тільки такі групи робіт, які закріплені за одним відповідальним виконавцем.

Найбільш поширеним способом укрупнення є укрупнення групи операцій графіка, незалежних від інших, без порушення логіки процесу. Наприклад, в деталізованої сітьової моделі, зображеної на рис. 8.9, а, кожна з робіт 1 і 2, 3 і 7, 8 і 9, 6 і 11 (роботи тут задані номерами над стрілками) після укрупнення замінена однією роботою, як показано на рис. 8.9. У число вибраних для укрупнення подій повинні входити вихідне і завершальне події.

Рис. 8.9

Слід зауважити, що можливі й інші способи укрупнення сітьових графіків в залежності від того, в яких термінах задана сітьова модель.

Зшивання сітьових моделей

При плануванні великих розробок і великих комплексів ропи до розробки сітьового графіка бере участь кілька виконавців. Кожному з них доручається розробка приватного сітьового графіка, що є окремим шматком загального графіка.

Після формування приватних сітьових графіків складається зведена сітьова модель на основі зшивання сітьових моделей, тобто з'єднання двох або декількох графіків в одну мережу за певними правилами.

Процес зшивання проходить тим успішніше, чим ретельніше опрацьовані попередні етапи побудови мережі, тобто успішне зшивання приватних графіків у зведену сітьову модель можливе лише за єдиної ступеня деталізації.

Основою для зшивання служать так звані граничні події. Ці події належать різним мережам, але мають, як правило, однакові визначення та позначення.

Порядок розташування граничних подій щодо один одного і правила їх зшивання наступні:

1. Граничне подія є вихідним в одній мережі і вхідним в іншій (рис. 8.10).

2. Одна вихідна гранична подія мережі зшивається з двома або кількома граничними подіями іншої мережі.

3. Внутрішнє граничне подія одного сітьового графіка зшивається з внутрішнім граничним подією іншого графіка.

Слід зазначити, що граничні події часто краще зшивати фіктивними роботами. Цим досягається суворе розмежування відповідальності виконавців робіт, від виконання яких залежить звершення граничних подій.

N правил	Мережа до зшивання		Мережа після зшивання
N правил	Мережа а	Мережа б	Мережа після зшивання
правило 1
правило 2

Рис. 8.10

Дата добавления: 2018-05-12; просмотров: 830; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 1 23

Мы поможем в написании ваших работ!