18/11
1 - 3 - 5 - 6 в†’ 10/5 + 12/6 + 9/6 = 31/17
Знаходження критичного шляху.
Шлях 1 - 3 - 5 - 6 - найбільш тривалий з повних шляхів називається критичним.
31/17 - це мінімальний час виконання робіт для досягнення поставленої задачі є критичним терміном і позначається tкр. Робота і події, що лежать на критичному шляху, називають критичними. p> Якщо виконання будь-якої критичної роботи буде затримано, це затримає виконання всього комплексу робіт.
Щоб прискорити виконання поставленого завдання, необхідно скоротити терміни виконання критичних робіт.
Некритичні роботи можуть володіти резервами часу, на яке можна затримати виконання некритической робіт, скоротивши при цьому витрати на виконання всього комплексу робіт.
Для визначення резервів часу подій необхідно розрахувати ранні та пізні терміни здійснення подій.
Ранній (або очікуваний) термін tp (j) вчинення j-го події визначається тривалістю максимального шляху, що передує цьому події.
tp (j) = max t (Lnj),
де t (Lnj) - будь-який шлях, що передує j-му події, тобто шлях від вихідного до j-го події мережі. Якщо подія має кілька попередніх шляхів, а отже кілька попередніх подій i, то для оцінки раннього строку вчинення j-го події слід вибирати максимальний з попередніх шляхів,
tp (j) = maxi, j [tp (i) + t (i, j)].
Розрахунок раннього терміну настання подій для прикладу на рис. 1. p> tp1 = 0;
tp2 = tp1 + t (1, 2) = 0 + 4 = 4;
tp3 = tp1 + t (1, 3) = 0 + 10 = 10;
tp4 = tp2 + t (2, 4) = 4 + 6 = 10;
tp5 = max [tp4 + t (4, 5); tp2 + t (2, 5); tp3 + t (3, 5)] = max [(10 + 11); (4 + 5); (10 + 12)] = [21; 9; 22] = 22;
tp6 = tp5 + t (5; 6) = 22 + 9 = 31
Затримка звершення події по відношенню до свого раннього терміну не відіб'ється на терміні звершення завершального події (а значить, і на терміні виконання комплексу робіт) до тих пір, поки сума терміну звершення цього події і тривалість максимального з наступних за ним шляхів не перевищить довжини критичного шляху.
Тому пізній (або граничний) термін tp (j) звершення j-го події дорівнює:
tp (j) = tкр - max t (Lnj)
де Lnj - будь-який шлях наступний за j-м подією, тобто шлях від j-го до завершального події мережі.
Якщо подія j має кілька наступних шляхів i, то пізній термін звершення j-го події знаходиться як мінімальний з наступних шляхів.
tp (j) = min j, i [tn (i) - t (j, i)].
Розрахунок пізніх термінів звершення подій.
tn6 = tкр = 31;
tn5 = tn6 - t (5, 6) = 31 - 9 = 22;
tn4 = tn5 - t (4, 5) = 22 - 11 = 11;
tn3 = tn5 - t (3, 5) = 22 - 12 = 10;
tn2 = min [tn4 - t (2, 4); tn5 - t (2, 5)] = [(11 - 6); (22 - 5)] = [5, 17] = 5;
tn1 = min [tn2 - t (1, 2); tn3 - t (1, 3)] = [(5 - 4); (10...
