Завдання оптимізації часу виконання проекту

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

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

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

Позначимо ресурси по роботах , , … відповідно , , ….

Нехай робота із часом її виконання лежить на критичному шляху, а – деяка робота, що лежить на некритичному шляху, і час її виконання – .

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

Кошти , вкладені в роботу , тобто , приводять до зменшення часу її виконання:

.

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

; . (2.5)

Позначимо – коефіцієнт перерахування.

Тоді формули (2.5) приймуть вид:

; .

При таких операціях має виконуватися умова: сума знятих з некритичних робіт коштів повинна дорівнювати сумі вкладених коштів на критичні роботи: , де М – число робіт, на які кошти вкладалися, а N – число робіт, з яких кошти знімалися.

Загальний строк виконання всього комплексу робіт визначається цільовою функцією:

. (2.6)

Тут – номера тих робіт критичного шляху, кошти яких не змінилися.

Потрібно так перерозподілити кошти з некритичних робіт на критичні, щоб функція (2.6) прийняла найменше значення.

Скільки коштів можна взяти з некритичної роботи? Ясно, що все взяти не можна. кошти, що знімаються, визначаються наявністю резервів часу. Нехай вільний резерв часу роботи рівний . Тоді повинна виконуватися умова , звідки – обмеження на кошти, що знімаються з роботи .

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

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