Определение критического пути.

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

Метод определения такого пути рассмотрим на примере.

Пусть задана сетевая модель с исходным событием 0 и завершающем событием 6. У стрелок даны оценки времени, необходимые для выполнения каждой операции.

Расчет критического пути включает два этапа.

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

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

Рассмотрим теперь прямой проход.

Пусть - ранний срок начала всех операций, выходящих из события i. Таким образом, является ранним сроком наступления события i. Если принять i=0, т.е. считать, что номер исходного события сети равен нулю, то при расчете сети . вычисления при прямом проходе выполняются по формуле:

Следовательно, чтобы вычислить ES j для события j, нужно сначала определить ES i начальных событий всех операций (i, j), входящих в событие j .

Обратный проход начинается с завершающего события сети. При этом целью является определение - поздних сроков окончания всех операций, входящих в событие i. Если принять i=n, где n - завершающее событие сети, то является отправной точкой обратного прохода. В общем виде для любого события i

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

Операция (i, j) принадлежит критическому пути, если она удовлетворяет следующим трем условиям:

ES i = LC i ,

ES j = LC j ,

ES j - ES i = LC j - LC i = D ij .

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

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