6.6.2. Метод критического пути

Конечным результатом применения метода критического пути (СРМ) будет построение временного графика выполнения проекта (см. рис. 6.50). Для этого проводятся специальные вычисления, в результате чего получаем следующую информацию.

1. Общая длительность выполнения проекта.

2. Разделение множества процессов, составляющих проект, на критические и некритические.

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

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

□ - самое раннее возможное время наступления события j, Aj - самое позднее возможное время наступления события j, DtJ - длительность процесса (i, j).

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

Проход вперед. Вычисления начинаются в узле 1 и заканчиваются в последнем узле п.

Начальный шаг. Полагаем П1 = 0; это указывает на то, что проект начинается в нулевой момент времени.

Основной шаг j. Для узла j определяем узлы р, q, v, непосредственно связанные с узлом j процессами (р, j), (q, j), (v,j), для которых уже вычислены самые ранние времена наступления соответствующих событий. Самое раннее время наступления события j вычисляется по формуле

= тах{Ц, + Dpj, Uq + Dqi, ...,□ + DJ.

Проход вперед завершается, когда будет вычислена величина □ для узла п.

По определению величина Пу равна самому длинному пути (длительности) от начала проекта до узла (события) j.

Проход назад. В этом проходе вычисления начинаются в последнем узле п и заканчиваются в узле 1.

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

Основной шаг j. Для узла j определяем узлы р, q, v, непосредственно связанные с узлом j процессами (j, р), (j, q), (/, v), для которых уже вычислены самые поздние времена наступления со-

ответствующих событий. Самое позднее время наступления события j вычисляется по формуле

Д; = пип{Д, - Djp, Д, - D .... Д - DJ.

Проход назад завершается при вычислении величины Д, для узла 1.

Процесс (i, j) будет критическим, если выполняются три условия.

1. Д, = Ц

2. Д, = Ц

3. Д,-Д, = Ц-Ц=Д,

Если эти условия не выполняются, то процесс некритический. Критические процессы должны образовывать непрерывный путь через всю сеть от начального события до конечного.

Пример 6.6.2

Найдем критический путь для сети проекта, показанной на рис. 6.54. Длительность всех процессов дана в днях.

Обозначения: Проход вперед: [ZF Проход назад: Л -Критический путь: (7)-

Конец прохода. назад

Начало f

прохода

вперед

Начало прохода назад

Ч Конец прохода вперед

Рис. 6.54. Проходы вперед и назад для проекта из примера 6.6.2

Проход вперед

Узел 1. Полагаем Oi = 0.

Узел 2. П2 = +D12 = 0 + 5 = 5.

Узел 3. □, = max{D, + D13> + DJ = тах{0 + 6, 5 + 3} = 8. Узел 4. П4 = П2 +D2i = 5 + 8 = 13.

Узел 5. = тах{П3 + D3i, П4 + DJ = тах{8 + 2, 13 + 0} = 13. Узел 6. □, = тах{П3 + DM, П4 + Di6, Ds + DJ =

= тах{8 + 11,13 + 1, 13 + 12} = 25. Таким образом, расчеты показывают, что проект можно выполнить за 25 дней.

Проход назад

Узел 6. Полагаем Д6 = П6 = 25. Узел 5. Д5 = Д6 - D56 = 25 - 12 = 13.

Узел 4. Д4 = гшп{Д6 - D46, Д5 - DJ = min{25 -1,13-0} = 13. Узел 3. Д3 = гшп{Д6 - D36, Д6 - DJ = min{25 - 11, 13 - 2} = 11. Узел 2. Д2 = min{A4 - D24, Д3 - D23} = min{13 - 8, 11 - 3} = 5. Узел 1. Д, = min{A3 - DJ3, Д2 - D12} = min{ll - 6, 5 - 5} = 0. Вычисления без ошибок всегда приводят к результату Д, = 0.

Результаты вычислений, выполняемых при проходах вперед и назад, показаны на рис. 6.54. Правила определения критических процессов показывают, что критический путь составляют процессы 1->2->4->5->6, т.е. этот путь проходит от начального узла 1 до конечного узла 6. Сумма длительностей критических процессов (1, 2), (2, 4), (4, 5) и (5, 6) равна длительности всего проекта (т.е. 25 дней). Отметим, что процесс (4, 6) удовлетворяет первым двум условиям критического пути (Д4 = □ = 13 и Д6 = □ = 25), но не удовлетворяет третьему условию (□, - П4 # D46). Поэтому данный процесс не является критическим.

УПРАЖНЕНИЯ 6.6.2

1. Найдите критический путь для сети проекта, показанной на рис. 6.55.

Рис. 6.55. Сеть проекта для упражнения 1

2. Найдите критические пути для сетей проектов, показанных на рис. 6.56.

3. Найдите критический путь в задаче из упражнения 6.6.1.6.

4. Найдите критический путь в задаче из упражнения 6.6.1.8.

5. Найдите критический путь в задаче из упражнения 6.6.1.9.