Алгоритм для обчислення пізніх термінів звершення подій

Розглянемо роботи, які витікають з j-ої події, тобто роботи (; ); (; ); …; (; ). Позначимо множину цих робіт (рис. 10).

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

;

;

...;

.

або

;

...;

.

Всі ці нерівності виконуватимуться при виконанні єдиної нерівності

. (6)

.

.

.

Рис. 10. Графічне зображення множини

Отже, найбільш пізнім з допустимих термінів звершення j–ої події, тобто максимально допустимим часом між початковою і j-ою подією при незмінному критичному шляху, буде термін, що визначається рівністю

, (7)

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

Формула (7) містить алгоритмдля обчислення , а саме:

· відправляючись від кінцевої події, для якої = , за формулою (7) спочатку розраховуються пізні терміни звершення тих подій, з яких виходитимуть лише роботи, що закінчуються в кінцевій події графіка;

· відправляючись від тільки що знайдених пізніх термінів, за допомогою тієї ж формули знаходять нову серію пізніх термінів і так далі аж до початкової події, для якої = =0.

Звернемо увагу, що для обчислення пізніх термінів за вказаним алгоритмом необхідно знати критичний час, який, як показано вище, знаходиться в результаті обчислень ранніх термінів за попереднім алгоритмом. Тому пізні терміни можна знайти лише після того, як знайдені ранні терміни. Корисно запам'ятати також, що ранні терміни звершення подій знаходяться за так званим алгоритмом «руху вперед» - від початкової події до кінцевої, тоді як пізні терміни знаходяться за алгоритмом «руху назад»- від кінцевої події до початкової.

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

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

.

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

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

Значить, максимальний шлях , продовжений максимальним шляхом , дає критичний шлях , тобто . Навпаки, якщо , то , звідки витікає рівність = .