Лекція 9. Сіткове планування та управління (спу). Аналіз та оптимізація.

Аналіз і оптимізація сіткового графіка.

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

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

Коефіцієнтом напруженості К_н роботи (i,j)називається відношення тривалості відрізків шляху, які не співпадають між собою і розміщених між одними й тими самими подіями, одним із яких є шлях максимальної тривалості, що проходить через дану роботу, а іншим – критичний шлях:

Кн(i,j) =	t (Lmax) – t ‘кр	(6.1)
	t кр -- t ‘кр

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

t _кр - тривалість (довжина) критичного шляху;

t‘_кр- тривалість відрізка розглянутого шляху, що збігає з критичним шляхом.

Формулу (6.1)можна легко привести до виду:

Кн(i,j) = 1 -	R(i,j)	(6.2)
	t кр -- t ‘кр

де R(i,j) – повний резерв часу роботи (i,j).

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

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

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

7. мінімізація часу виконання комплексу робіт при заданій його вартості;

8. мінімізація вартості комплексу робіт при заданому часі виконання проекту.

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

Оптимізація сіткового графіка методом «час – вартість».

При використанні методу «час – вартість» передбачається, що зменшення тривалості роботи пропорційне зростанню її вартості. Кожна робота (i,j) характеризується тривалістю t(i,j), що може знаходитися в межах

a(i,j) ≤ t(i,j) ≤ b(i,j) (6.3)

де a(i,j) – мінімально можлива (екстренна) тривалість роботи (i,j), яку можна здійснити в умовах розробки;

b(i,j) – нормальна тривалість виконання роботи (i,j).

При цьому вартість c(i,j) роботи (i,j) лежить в межах від c_min(i,j) (при нормальній тривалості роботи) до c_max(i,j) (при екстремальній тривалості роботи). Зміна тривалості Δt(i,j) = b(i,j) - t(i,j) роботи (i,j) у межах (6.3) відповідає зміні вартості роботи Δc(i,j). Залежність зміни вартості Δc(i,j) від зміни тривалості роботи Δt(i,j) визначається коефіцієнтом витрат на прискорення роботи (див. мал. 6.3)

h(i,j) =	Δc(i,j)	=	cmax(i,j) - cmin(i,j)	(6.4)
	Δt(i,j)		b(i,j) – a(i,j)

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

C =

∑ i,j

c(i,j)

(6.5)

зменшиться на величину

ΔC =

∑ i,j

Δc(i,j) =

∑ i,j

[b(i,j) - t(i,j)] h(i,j) =

∑ i,j

Δt(i,j) h(i,j)

(6.6)

Для проведення часткової оптимізації сіткового графіка крім тривалостей робіт t(i,j), необхідно знати їхні граничні значення a(i,j) і b(i,j), а також коефіцієнти витрат на прискорення робіт h(i,j), що обчислюються по формулі (6.4). Тривалість кожної роботи t(i,j) доцільно збільшити на величину резерву часу роботи так, щоб не змінити ранні (очікувані) терміни настання всіх подій сітки, тобто на величину вільного резерву часу роботи R_в(i,j).

Мал. 6.3.