Наступления событий (обратный проход)

Шаг 1. Положить L(n) =Е(n).

Шаг 2. Для i = n-1,n-2,......,0 вычислить

L(i)=min {L(j)-d_ij}," j:(ij)є A

где минимум берется по всем работам, начинающимся в i -м узле и входящим в любой j -й узел.

Действуя описанным выше способом, рассчитаем наиболее ранние возможные сроки наступления событий и наиболее поздние допустимые сроки наступления событий (пример приведен на рис. 4). Наиболее ранние возможные сроки наступления событий отображены в квадратиках рядом с самим событием, над квадратиками расположены наиболее поздние допустимые сроки наступления событий.

Рис. 4

Теперь, используя результаты вычислений при прямом и обратном проходах, можно определить работы критического пути. Работа (i, j) принадлежит критическому пути, если она удовлетворяет следующим трем условиям:

E(i) -ранние сроки начала всех работ, выходящих из события i.

L(i) -поздние сроки окончания всех работ, входящих в событие i.

d_ij - продолжительность работы, соединяющей i-тое и j- тое события.

1. E(i)=L(i)

2. E(j)=L(j)

3. E(j)-E(i)=L(j)-L(i)=d_ij

По существу, эти условия означают, что между ранним сроком: начала (окончания) и поздним сроком начала (окончания) критической работы запас времени отсутствует.

Например, на рис. 3, критический путь составляют работы: 1,2,4,8,9, (из 6 до 8 события фиктивная работа),12,13,15,16,18 - эти работы выделены другим цветом на графике.

Таблица 2 - Работы по проекту с резервами времени

Резервы времени критических работ рав ен нулю.

Какое максимальное количество времени можно выделить для ее выполнения без задержки своевременного окончания всего проекта? Работа (i,j) может начаться не ранее Е(i) и должна закончиться не позднее L(j). Таким образом, без задержки окончания проекта на выполнение работы (i, j) можно выделить не более L(j)-Е(i) единиц времени. Следовательно, при выполнении этой работы можно допустить максимальную задержку L(j)-Е(i)-d_ij>=0. Величина L(j)-E(i)-d_ij называется полным резервом времени работы (i,j).