ермін завершення всього проекту в цілому. Наведемо запис алгоритму, безпосередньо вичислювального характеристики РНАЧ і РВИП.
АЛГОРИТМ 1.
Дані: Мережевий графік G робіт V, заданий списками предше (v), vГЋV.
Результати: Найбільш ранні можливі терміни початку і виконання робіт РНАЧ (v), РВИП (v), vГЋV.
Крок 1. Оголосити можливі ранні терміни початку РНАЧ (v) і виконання РВИП (v) робіт рівними нулю. Поточної вершиною оголосити першу вершину v k = v 1.
Крок 2. Всім вершин v попереднім поточної вершині v k , значення РНАЧ (v k ) присвоїти максимум зі значень РВИП (v) і РНАЧ (v k ). Значення РВИП (v k ) покласти рівним значенню РНАЧ (v k ) плюс час виконання самої роботи поточної вершини t (v k ). p> Крок 3. Якщо є наступна вершина (робота) після поточної, то оголосити її поточної вершиною v k , інакше перейти в Крок 5.
Крок 4. Повернутися в Крок 2.
Крок 5. Видати найбільш ранні можливі терміни початку і виконання робіт РНАЧ (v), РВИП (v), vГЋV, кінець роботи алгоритму.
Нехай T - плановий термін виконання проекту W. Ясно, що Т повинно задовольняти нерівності Т> = РВИП (V n +1 ). p> Через ПВИП (v) (відповідно ПНАЧ (v)) позначимо найбільш пізній допустимий термін виконання (початку) роботи v, тобто такий термін, який не збільшує термін Т реалізації всього проекту.
Значення можливих і допустимих термінів виконання робіт дозволяють визначити резерви часу для виконання тієї чи іншої роботи. Повний резерв (іноді його називають сумарний) часу виконання робіт визначається за формулою:
PE3EPB (v) = ПHAЧ (v)-PHAЧ (v).
Значення PE3EPB (v) дорівнює максимальній затримці у виконанні роботи v, що не впливає на плановий термін Т. Зрозуміло, що справедливо і така рівність: РЕЗЕРВ (v) = ПВИП (v)-РВИП (v).
Роботи, що мають нульовий резерв часу, називаються критичними. Через будь-яку таку роботу проходить деякий максимальний sp-шлях у мережі G. Критичні роботи характеризуються тим, що будь-яка затримка у їх виконанні автоматично веде до збільшення часу виконання всього проекту.
Наведемо запис алгоритму, безпосередньо вичислювального характеристики ПВИП і ПНАЧ. br/>
АЛГОРИТМ 2.
Дані: Мережевий графік G робіт V, заданий списками предше (v), vГЋV, плановий термін закінчення проекту - Т.
Результати: Найбільш пізні допустимі терміни виконання та початку робіт ПВИП (v) і ПНАЧ (v).
В
Крок 1. Оголосити для всіх робіт vГЋV значення найбільш пізнього строку виконання робіт рівним Т - значенням планового терміну закінчення проекту і вершину v p фіктивної роботи p оголосити поточної v k .
Крок 2. Присвоїти значення ПНАЧ поточної роботи v k рівним значенню ПВИП роботи і відняти час виконання поточної роботи.
Крок 3. Присвоїти значенням ПВИП (v) для всіх робіт vГЋПРЕДШ (v) попередніх поточної роботі v k мінімальне значення із значень ПВИП виконання роботи v або ПНАЧ виконання поточної роботи v k , якщо таких немає перейти в Крок 4. p> Крок 4. Якщо мається попередня вершина (робота) до поточної, то оголосити її поточної, інакше перейти в Крок 6.
Крок 5. Перейти в Крок 2. p> Крок 6. Видати найбільш пізні допустимі строки виконання і початку робіт ПВИП (v) і ПНАЧ (v), кінець роботи алгоритму.
Проілюструємо роботу наведених алгоритмів на наступних прикладах:
Приклад 1: Проект гаража для стоянки автонавантажувачів.
n
Найменування роботи
передує ющіе роботи
Час ви-конання t (v k )
1
Початок проекту (фіктівн. робота)
Ні
0
2
зрізає рослинного шару грунту
1
5
3
Монтаж каркаса
2
30
4
Обшивка стін профнастилом
3
15
5
Покрівля з профнастилу
3
12
6
Заповнення отвору воротами
4
5
7
Масляна забарвлення воріт і профнастилу
5,6
10
8
Щебеневе основа під підлоги
7
3
9
Асфальтове покриття
...
