Наиболее ранний срок наступления события

Конечный узел критического пути всегда имеет номер n,

Если узел с номером j принадлежит критическому пути, то номер предшествующего ему узла равен i(j) (см.формулу (1)),

Начальный узел всегда имеет номер 0.

Длина критического пути определяет минимальное время, необходимое для завершения проекта.

Пример 2.

Для всех узлов (событий) сети из примера 1 определить наиболее ранний возможный срок наступ­ления события и критический путь.

Последовательно применяя формулу (1) для j=0,1,2,3,…,8, получаем

l₀^р=0, предшествующего события здесь нет.

l₁^р=max{l₀^р+t_0,1}=max{0+4}=4, i(1)=0.

l₂^р=max{l₀^р+t_0,2}=max{0+6}=6, i(2)=0.

l₃^р=max{l₂^р+t_2,3}=max{6+7}=13, i(3)=2.

l₄^р=max{l₀^р+t_0,4, l₃^р+t_3,4}=max{0+9,13+0}=13, i(4)=3.

l₅^р=max{l₁^р+t_1,5, l₃^р+t_3,5}=max{4+8,13+0}=13, i(5)=3.

l₆^р=max{l₄^р+t_4,6, l₅^р+t_5,6}=max{13+10,13+6}=23, i(6)=4.

l₇^р=max{l₆^р+t_6,7}=max{23+4}=27, i(7)=6.

l₈^р=max{l₇^р+t_7,8}=max{27+9}=36, i(8)=7.

Итак, для каждого события найден наиболее ранний возможный срок его наступ­ления, определяющий момент времени, начиная с которого это событие становится возможным. Длина критического пути равна Т_кр= l₈^р=36. Критический путь проходит через следующие узлы сети:

8, i(8)=7, i(7)=6, i(6)=4, i(4)=3, i(3)=2, i(2)=0.

Следовательно, в данном примере критический путь имеет вид

(0,2)-(2,3)-(3,4)-(4,6)-(6,7)-(7,8).

Наиболее поздний срок наступления события

Наиболее поздним допустимым сроком наступ­ления i-го события является наиболее поздний срок завершения всех работ, идущих к i-му узлу, не влияющий на время завершения всего проекта за Т_кр.

Пусть l_i^п ¾ наиболее поздний допустимый срок наступления i-го собы­тия. Чтобы гарантировать, что продолжительность критического пути не бу­дет превышена, необходимо положить l_n^п =Т_кр.

Начиная с n-го события, двигаемся в обратном направлении к событию 0, вычисляя очередное l_i^п при i<n по формуле

и номер j*(i), при котором достигается минимум.

Пример 3.

Для всех узлов (событий) сети из примера 1 определить наиболее поздний допустимый срок наступ­ления события.

Полагаем l₈^п =Т_кр=36. Затем последовательно применяя формулу (2) для j=8,…,1, получаем

l₇^п=min{l₈^п- t_7,8}=min{36-9}=27, j*(i)=8,

l₆^п=min{l₇^п-t_6,7}=min{27-4}=23, j*(i)=7,

l₅^п=min{l₆^п-t_5,6}=min{23-6}=17, j*(i)=6,

l₄^п=min{l₆^п-t_4,6}=min{23-10}=13, j*(i)=6,

l₃^п=min{l₄^п-t_3,4, l₅^п-t_3,5}=min{13-0,17-0}=13, j*(i)=4,

l₂^п=min{l₃^п-t_2,3}=min{13-7}=6, j*(i)=3,

l₁^п=min{l₅^п-t_1,5}=min{17-8}=9, j*(i)=5,

l₀^п=min{l₁^п-t_0,1,l₄^п-t_0,4, l₂^п-t_0,2}=min{9-4,13-9,6-6}=0, j*(i)=2.

Отметим, что при правильно проведенных вычислениях всегда должно получиться l₀^п =0.