Задача определения продолжительности проекта

Рис. 6. Поиск критического пути

Операции, принадлежащие критическому пути, называются критическими. Остальные (некритические) операции имеют резерв времени, характеризуемый максимальной задержкой операции, при которой продолжительность проекта не изменяется. Критические операции имеют нулевой резерв. Приведем соответствующие формулы.

Алгоритм 9. Предположим, что выполнение комплекса операций (проекта) начинается в нулевой момент времени. Обозначим Q0 - множество событий, не требующих выполнения ни одной из операций, то есть входы сети; Qi - множество событий, непосред-ственно предшествующих событию i, то есть множество вершин j сети, для которых существует дуга (j; i). Положим

t- = max j t- = max (t- + j).

' jeQo ' jQ 1

Величина t- называется ранним моментом (временем) свершения i-го события и характеризует время, раньше которого это событие произойти не может. Длина критического пути

T = max t-

i

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

Поздним моментом t+ свершения события называется максимальное время его наступления, не изменяющее продолжительности проекта. Обозначим Ri - множество событий, непосредст-

венно следующих за событием i, то есть множество вершин J сети, для которых существует дуга (i;J). Вычислим для каждой вершины-события i длину li максимального пути от этой вершины до выхода сети - события, заключающегося в завершении всего комплекса операций:

U = max (lj + tj).

J^Ri

Положим t+ = T - lit i = 1, n .

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

чтобы событие i произошло не позднее момента t+, i = 1,n .

Полным резервом Ati события i называется разность между его поздним и ранним моментами свершения, то есть

At, = t+ - t:, i = 1,n.

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