Расчёт критического пути сетевого графика: формулы

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

Топология для расчёта

Возьмём сетевой график с шестью событиями (0 - начальное, 5 - конечное) и восемью работами:

Топология нарочно сложнее классического примера из пяти работ: есть развилка сразу после старта (A и B), «диагональная» работа C, срезающая путь через два события, и две ветки, сходящиеся в конце (через G и через H). На таком графе видно, где расчёт даёт неочевидный результат: путей максимальной длины может быть сразу два, а работа с нулевым резервом обоих своих событий не обязана быть критической.

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

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

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

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

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

Расчёт для нашей топологии при указанных выше длительностях:

Самый ранний срок завершения проекта - 21 день. К событию 3 ведут сразу две работы, D и связка C-E, и обе дают одинаковые 12 дней - первый признак, что в графике будет не один, а два критических пути.

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

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

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

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

Резервы событий и ловушка с критичностью работы

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

Казалось бы, раз события 0 и 2 оба критические ($R[0]=R[2]=0$), то и работа B(0-2) между ними тоже критическая. Но это не так - в этом главная ловушка расчёта. Условие критичности работы строже нулевого резерва её концов:

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

Для B: $T_{\text{ран}}[0] + 6 = 6$, но $T_{\text{ран}}[2] = 7$ - равенство не выполняется, значит B не критическая, хотя оба её события формально безрезервные. Причина в том, что событие 2 определяется не работой B, а более длинной цепочкой A-C ($4+3=7$). Проверка всех восьми работ даёт критические A, C, D, E, G и некритические B, F, H.

Полный и свободный резерв работы

Для каждой некритической работы считают два разных резерва, и путать их - вторая типичная ошибка расчёта.

Полный резерв - на сколько можно сдвинуть или растянуть работу, не выходя за срок всего проекта:

$$R_{\text{п}}(i,j) = T_{\text{поз}}[j] - T_{\text{ран}}[i] - t_{ij}.$$

Свободный резерв - на сколько можно сдвинуть работу, не трогая при этом раннее время следующего события:

$$R_{\text{св}}(i,j) = T_{\text{ран}}[j] - T_{\text{ран}}[i] - t_{ij}.$$

Возьмём работу F(2-4) длительностью 7 дней: $R_{\text{п}} = 15 - 7 - 7 = 1$ день, а $R_{\text{св}} = 14 - 7 - 7 = 0$ дней. Разница показательна: у F есть день запаса относительно всего проекта (событие 4 некритическое, $R[4]=1$), но нет ни дня запаса относительно момента, когда должно наступить событие 4 по расчёту. Задержать F можно без срыва проекта, но это сдвинет зафиксированное раннее время события 4 - безопасно, только если от него больше ничего не зависит.

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

Когда критических путей несколько

В нашем примере ровно два пути набирают максимальную длину 21 день: A-D-G ($4+8+9=21$) и A-C-E-G ($4+3+5+9=21$). Это нормальная ситуация для сетевых графиков: задержка на любом из двух путей одинаково сдвигает срок проекта, поэтому оба требуют одинакового контроля.

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

Критический путь не закреплён навсегда за одной цепочкой работ - он определяется текущими длительностями и может «переключиться» при их изменении. Увеличьте B всего на 2 дня (с 6 до 8) - путь B-E-G вырастет до $8+5+9=22$ дней и станет новым и единственным критическим путём, а прежние A-D-G и A-C-E-G (по-прежнему по 21 дню) станут некритическими. Проверить это можно прямо в калькуляторе выше, сдвинув ползунок B.

Пример полного расчёта

Соберём весь алгоритм в один проход по шагам - именно так оформляют решение в контрольной работе:

1. Прямой проход: $T_{\text{ран}} = [0,\ 4,\ 7,\ 12,\ 14,\ 21]$ для событий 0-5 (расчёт - в разделе выше).
2. Обратный проход: $T_{\text{поз}} = [0,\ 4,\ 7,\ 12,\ 15,\ 21]$.
3. Резервы событий: $R = [0, 0, 0, 0, 1, 0]$ - критичны все события, кроме события 4.
4. Критические работы: проверка условия $T_{\text{ран}}[i]+t_{ij}=T_{\text{ран}}[j]$ при нулевых резервах концов даёт A, C, D, E, G; работа B отсеивается, несмотря на нулевые резервы своих событий.
5. Критический путь: длина 21 день, представлен двумя равными путями A-D-G и A-C-E-G.
6. Резервы некритических работ: B - полный 1, свободный 1; F - полный 1, свободный 0; H - полный 1, свободный 1.

Если сам сетевой график ещё не построен - то есть неизвестно, как разложить список работ с предшественниками на события и дуги, - этот шаг разобран отдельно в статье про построение сетевого графика методом CPM; здесь же мы считаем критический путь на уже готовой топологии.

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

• Нулевой резерв обоих событий принимают за признак критичности работы. Как на работе B выше - это необходимое, но не достаточное условие; проверяйте равенство $T_{\text{ран}}[i]+t_{ij}=T_{\text{ран}}[j]$.
• Путают полный и свободный резерв. Полный - запас относительно всего проекта, свободный - запас, не трогающий раннее время следующего события; свободный всегда не больше полного.
• В прямом проходе берут первую попавшуюся входящую работу вместо максимума. Если к событию ведут несколько работ, нужен максимум суммы - иначе $T_{\text{ран}}$ занижается и расчёт съезжает.
• Обратный проход начинают раньше, чем закончен прямой. Поздние времена нельзя посчитать, пока не известны все ранние - только последовательно.
• Не проверяют, что критических путей может быть несколько. Одна «первая найденная» цепочка легко пропускает второй путь той же длины.

FAQ

С чего начать расчёт, если топология графика уже дана? С прямого прохода: начальному событию $T_{\text{ран}}=0$, дальше по возрастанию номеров - максимум по входящим работам. Только когда посчитаны все ранние времена, включая конечное событие, переходят к обратному проходу.

Как проверить расчёт критического пути на ошибку? Пересчитать длину каждого пути от начала до конца вручную и сравнить с $T_{\text{ран}}$ последнего события - они обязаны совпасть. Отрицательный резерв события означает, что в проходах перепутаны максимум и минимум.

Может ли резерв события быть отрицательным? При обычном расчёте - нет: $T_{\text{поз}}$ последнего события всегда равен его же $T_{\text{ран}}$. Отрицательные резервы появляются, только если директивный срок проекта меньше длины критического пути - сигнал, что план не укладывается в срок ни при каком порядке работ.

Коротко

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