Сетевое планирование: построение сетевого графика

Сетевое планирование - это способ описать проект в виде графа, где узлы (события) фиксируют моменты завершения работ, а дуги (работы) показывают, что одни задачи нельзя начать, пока не закончены другие. Ключевой результат построения сетевого графика - нахождение критического пути: самой длинной цепочки последовательно зависимых работ, которая определяет минимальный срок всего проекта. Любое опоздание на критической работе немедленно сдвигает дату окончания, тогда как некритические работы имеют резерв. Чтобы сразу увидеть механику метода, поиграйте с калькулятором ниже: он выполняет прямой и обратный проходы и показывает критический путь для шести работ при любых введённых продолжительностях.

Что такое сетевой граф и его элементы

Сетевой граф в методе критического пути (CPM, Critical Path Method) - это ориентированный ациклический граф. Его элементы:

• Событие (вершина, кружок на схеме) - факт завершения одной или нескольких работ, открывающий возможность начать следующие. Событие не имеет продолжительности.
• Работа (стрелка) - процесс, требующий времени и ресурсов. Каждая работа характеризуется продолжительностью $t_{ij}$, где $i$ - начальное событие, $j$ - конечное.
• Фиктивная работа (пунктирная стрелка) - зависимость между событиями без затрат времени ($t_{ij} = 0$); используется для отображения логических связей, которые нельзя выразить прямой стрелкой.

Рассчитать для своей задачи

Граф строится слева направо: начальное событие (одно) - слева, завершающее (одно) - справа. Нумерация узлов не обязана быть последовательной, но обычно удобно нумеровать так, чтобы для каждой работы $(i, j)$ выполнялось $i < j$ - это облегчает ручной проход и исключает путаницу.

Прямой проход: ранние времена событий

Прямой проход вычисляет $T_{\text{ран}}[j]$ - самое раннее время, когда событие $j$ может наступить. Начальному событию приписывают $T_{\text{ран}}[0] = 0$. Для каждого следующего события:

$T_{\text{ран}}[j] = \max_{(i,j) \in E} \bigl(T_{\text{ран}}[i] + t_{ij}\bigr).$

Максимум берётся по всем работам, входящим в событие $j$: чтобы оно наступило, должны завершиться все предшествующие работы. Проход ведётся в топологическом порядке (от меньших номеров к большим при правильной нумерации).

Пример для шести работ (топология из калькулятора выше, продолжительности по умолчанию: A=4, B=5, C=6, D=3, E=4, F=5):

Таким образом, самый ранний срок завершения всего проекта - 16 дней.

Рассчитать для своей задачи

Обратный проход: поздние времена событий

Обратный проход вычисляет $T_{\text{поз}}[i]$ - самое позднее допустимое время события $i$, при котором проект ещё укладывается в срок. Завершающему событию присваивают $T_{\text{поз}}[n] = T_{\text{ран}}[n]$ (или директивный срок, если он задан). Для остальных событий, двигаясь справа налево:

$T_{\text{поз}}[i] = \min_{(i,j) \in E} \bigl(T_{\text{поз}}[j] - t_{ij}\bigr).$

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

Для нашего примера:

Резервы событий и критический путь

Резерв события $R[i] = T_{\text{поз}}[i] - T_{\text{ран}}[i]$ показывает, на сколько можно сдвинуть наступление события без нарушения срока. Событие критическое, если $R[i] = 0$.

Критический путь проходит через все критические события и состоит из критических работ. Работа $(i, j)$ критическая, если:

$R[i] = 0, \quad R[j] = 0, \quad T_{\text{ран}}[i] + t_{ij} = T_{\text{ран}}[j].$

В нашем примере: $R[0]=0$, $R[1]=0$, $R[3]=0$, $R[4]=0$, $R[2]=7-7=0$. Проверяем работы:

• A(0-1): $0+4=4$ - да, критическая.
• C(1-3): $4+6=10 \ne 11$ - нет.
• D(1-2): $4+3=7$ - критическая.
• E(2-3): $7+4=11$ - критическая.
• F(3-4): $11+5=16$ - критическая.

Критический путь: 0-1-2-3-4 через работы A-D-E-F, длина 4+3+4+5=16 дней.

Резервы работ

Для каждой работы рассчитывают два вида резервов:

Полный резерв $R_{\text{п}}(i,j) = T_{\text{поз}}[j] - T_{\text{ран}}[i] - t_{ij}$ - максимальное время, на которое можно задержать начало работы, не увеличивая общую длительность проекта. Использование полного резерва «съедает» резервы других работ на том же пути.

Свободный резерв $R_{\text{св}}(i,j) = T_{\text{ран}}[j] - T_{\text{ран}}[i] - t_{ij}$ - время, на которое можно задержать работу, не затрагивая ранние времена последующих событий. Свободный резерв принадлежит только данной работе.

Для работы C(1-3) при дефолтных значениях: $R_{\text{п}} = T_{\text{поз}}[3] - T_{\text{ран}}[1] - 6 = 11 - 4 - 6 = 1 \text{ дн.}$ $R_{\text{св}} = T_{\text{ран}}[3] - T_{\text{ран}}[1] - 6 = 11 - 4 - 6 = 1 \text{ дн.}$

Для работы B(0-2): $R_{\text{п}} = 7 - 0 - 5 = 2 \text{ дн.}, \quad R_{\text{св}} = 7 - 0 - 5 = 2 \text{ дн.}$

Рассчитать для своей задачи

Пример построения сетевого графика шаг за шагом

Рассмотрим полный расчёт при продолжительностях A=4, B=5, C=6, D=3, E=4, F=5.

Шаг 1. Прямой проход:

$T_{\text{ран}}[0]=0, \quad T_{\text{ран}}[1]=4, \quad T_{\text{ран}}[2]=\max(5, 7)=7,$ $T_{\text{ран}}[3]=\max(10, 11)=11, \quad T_{\text{ран}}[4]=16.$

Шаг 2. Обратный проход:

$T_{\text{поз}}[4]=16, \quad T_{\text{поз}}[3]=11, \quad T_{\text{поз}}[2]=7,$ $T_{\text{поз}}[1]=\min(5, 4)=4, \quad T_{\text{поз}}[0]=0.$

Шаг 3. Резервы событий: $R[0]=0$, $R[1]=0$, $R[2]=0$, $R[3]=0$, $R[4]=0$ - все нулевые в данном примере.

Шаг 4. Критический путь: работы A, D, E, F; события 0-1-2-3-4; длина 16 дней.

Шаг 5. Резервы работ:

• A, D, E, F: $R_{\text{п}} = R_{\text{св}} = 0$ (критические).
• B(0-2): $R_{\text{п}} = 7-0-5=2$, $R_{\text{св}} = 7-0-5=2$.
• C(1-3): $R_{\text{п}} = 11-4-6=1$, $R_{\text{св}} = 11-4-6=1$.

Обратите внимание: если увеличить продолжительность работы C до 8 дней, то $T_{\text{ран}}[3]$ вырастет до 12, а критический путь перейдёт на цепочку 0-1-3-4 = 4+8+5 = 17 дней. Попробуйте это в калькуляторе выше.

Частые ошибки

• Неверный порядок прямого прохода. При наличии нескольких путей к событию берётся максимум, а не минимум. Ошибка «взяли первый попавшийся» ведёт к занижению $T_{\text{ран}}$ и, как следствие, к нереалистичному расписанию.
• Смешение прямого и обратного проходов. Обратный проход выполняется строго после прямого и двигается справа налево. Попытка совместить оба прохода в один проход приводит к ошибкам в $T_{\text{поз}}$.
• Забытые фиктивные работы. Фиктивная работа необходима, когда два события должны совпасть логически, но у них нет общей реальной работы. Её отсутствие искажает зависимости.
• Директивный срок меньше длины критического пути. В этом случае $T_{\text{поз}}[n] < T_{\text{ран}}[n]$, и резервы событий становятся отрицательными - это сигнал, что проект не укладывается в заданный срок ни при каком планировании.
• Путаница между полным и свободным резервом. Полный резерв показывает максимальный сдвиг без нарушения срока всего проекта, но за счёт резервов других работ; свободный резерв - безопасный сдвиг только данной работы. Использовать полный резерв без согласования с менеджером проекта опасно.

FAQ

Что такое критический путь и как его найти? Критический путь - самый длинный путь от начального до конечного события в сетевом графе. Его длина определяет минимальный срок проекта. Находят его через прямой и обратный проходы: критические события имеют нулевой резерв $R[i] = T_{\text{поз}}[i] - T_{\text{ран}}[i] = 0$, а критические работы соединяют только критические события с условием $T_{\text{ран}}[i] + t_{ij} = T_{\text{ран}}[j]$.

Может ли в сетевом графике быть несколько критических путей? Да. Если несколько путей от начала до конца имеют одинаковую максимальную длину, они все критические. Это усложняет управление проектом: задержка на любом из них сдвигает срок. При увеличении продолжительности одной из некритических работ до уровня критических путей появляется ещё один критический путь.

Чем метод CPM отличается от метода PERT? CPM (Critical Path Method) использует фиксированную детерминированную продолжительность каждой работы. PERT (Program Evaluation and Review Technique) применяет три оценки для каждой работы: оптимистичную, наиболее вероятную и пессимистичную, вычисляя ожидаемую продолжительность по формуле $t_e = (t_o + 4t_m + t_p)/6$. CPM удобен, когда продолжительности известны точно (строительство, производство); PERT - когда они неопределённы (R&D, исследования).

Коротко

Построение сетевого графика сводится к трём шагам: прямой проход (ранние времена событий через максимум), обратный проход (поздние времена через минимум) и вычисление резервов. Критический путь проходит через события с нулевым резервом и определяет минимальный срок проекта; его длина равна $T_{\text{ран}}$ завершающего события. Полный резерв работы $R_{\text{п}} = T_{\text{поз}}[j] - T_{\text{ран}}[i] - t_{ij}$ показывает, насколько безопасно сдвинуть задачу, не выходя за дедлайн.