10.3.2. Анализ критического пути с применением стрелочных графов

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

Рис. 10.11. Нанесение на стрелочный граф сроков, соответствующих операциям

Можно провести подобный анализ в терминах сроков наступления каждого события. Производится расчет наиболее раннего срока, к которому может завершиться каждое событие. Этот срок называется наиболее ранним сроком события (earliest event time - ЕЕТ). Общая продолжительность выполнения проекта определяется конечного узла графа. исходного события равен нулю.

Для того чтобы выявить критические операции, необходимо, начиная с конца графа, вычислить наиболее поздние сроки событий (latest event time - LET) к которым события могут закончиться. События, для которых выполняются соотношения

или

Пример 10.5. Применив ЕЕТ повторим задачу из примера 10.4 при условии, что продолжительность выполнения фиктивных операций равна нулю. Решение

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

Рис. 10.12. Стрелочный граф для примера 10.5 с указанием ЕЕТ и событий - наиболее ранний срок события. А - наиболее поздний срок события (стандартный срок, дней)

Полученные значения сроков наносятся на стрелочный граф, как это показано на рис. 10.12.

ЕЕТ последнего события равно 39 дням, которые также определяют общую продолжительность выполнения проекта.

Таблица 10.6. Расчет значений для примера 10.5 (см. скан)

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

Найденные значения сроков наносятся на стрелочный граф, изображенный на рис. 10.12.

Операция является критической, если для нее справедливы следующие соотношения:

и

Из рисунка 10.12 видно, что критическими, как и ранее, являются операции

Таблица 10.7. Расчет значений для примера 10.5 (см. скан)

Любые замедления на критическом пути приведут к задержке срока выполнения всего проекта. Между тем для некритических путей можно допустить некоторые задержки при выполнении составляющих их операций или пересмотреть график их выполнения. Запас времени, который существует в схеме проекта, называется резервом времени. Различают несколько видов резерва времени, возникающих под влиянием различных воздействий, которые оказывает запас времени на схему выполнения проекта. Общим резервом называется количество времени, на которое можно увеличить продолжительность операции в результате продления срока ее выполнения или пересмотра плана, не влияющего на продолжительность выполнения проекта в целом. Свободным резервом называется количество времени, на которое можно увеличить продолжительность операции в результате продления срока ее выполнения или пересмотра плана, не оказывающего воздействия на наиболее ранний срок выполнения любой последующей операции. Иногда используют третий вид, так называемый независимый резерв времени. Он не оказывает никакого влияния на предшествующие или последующие операции. Для любой операции

а также

и

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

Пример 10.6. По данным примера 10.5 для каждой операции найдем общий резерв времени.

Таблица 10.8. Расчет резерва времени операций для примера 10.5 (дней) (см. скан)

Операции, общий резерв времени которых равен нулю, являются критическими. На рис. 10.13 построен график Ганта, и отмечены возможно наиболее ранние сроки начала операций.

Рис. 10.13. График Ганта для примера 10.5