Визначення критичного шляху

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

Графічно події зображуються кружками. розділеними на три рівних сегмента (радіусами під кутом в 120 °); роботи зображуються суцільними лініями зі стрілками на кінці. орієнтованими зліва направо; фіктивні роботи зображуються пунктирними лініями зі стрілками на кінці. орієнтованими зліва направо.

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

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

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

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

Стосовно до Рис. 5 обчислення починаються с. Далі отримаємо:

На цьому обчислення першого етапу закінчуються.

Другий етап починається з завершального події мережі, для якого вважаємо. де n - завершальна подія. Потім, для будь-якої події i. де min береться по всіх операціях, які виходять з i -го події. Далі отримаємо:

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

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

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

На Рис. 6 критичний шлях включає операції B, D, F, I, L>. Критичний шлях визначає найкоротшу можливість всього проекту в цілому. Зауважимо, що операції (2, 4), (3, 5), (3, 6) і (4, 6) задовольняють умовам (1) і (2), але не умові (3). Тому вони не є критичними. Відзначимо також, що критичний шлях представляє собою безперервний ланцюжок операцій, що сполучає початкове подія мережі з завершальним.