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

Напомним, что событие соответствует некоторому узлу, представляет собой момент завершения одной или большего числа работ и может быть отправным моментом для начала последующих работ.

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

Пусть l_j^р— наиболее ранний возможный срок наступ­ления j-го события, j=0,1, 2, ..., n, где n+1— число событий (узлов) в сети. Величина t_ij —продолжительность работы, соединяющей два события (узлы) — i-е и j-е.

Поскольку j-е событие не может произойти, пока не будут завершены все работы, ведущие к j-му узлу, и поскольку рабо­та не может начаться, пока не произойдет предшествующее ей событие, наиболее ранний возможный срок наступления каждо­го события вычисляется как продолжительность самого длинно­го пути от начального события до данного. Так как в сети установлена правильная нумерация, то l_j^р можно вычислять последовательно, начиная с l₀^р =0 , по формуле

Применяя формулу (1), предлагается запоминать для каждого j значение l_j^р и номер i(j), на котором достигается максимальное значение. Это позволит по окончании вычислений найти не только величину наиболее длинного пути, но и сам этот путь.

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

Длину критического пути обозначим Т_кр. Тогда Т_кр=l_n^р. Узлы, через которые проходит критический путь можно легко получить, исходя из следующего алгоритма :

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

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

3. начальный узел всегда имеет номер 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) .