Критическим называется путь, имеющий максимальную суммарную продолжительность; этот путь называется "критическим", поскольку от него зависит продолжительность выполнения всего плана, — сокращение продолжительности других путей не приведет к сокращению времени выполнения всего плана в целом, но задержка начала любого действия в критическом пути замедлит осуществление всего плана. На этом рисунке критический путь показан жирными линиями. Для осуществления всего плана за минимальное суммарное время действия в критическом пути следует выполнять без задержки между ними. С другой стороны, действия, лежащие вне критического пути, имеют определенный запас времени — временное окно, в течение которого они могут быть выполнены. Это окно задается в терминах самого раннего возможного времени начали, ES, и самого позднего возможного времени начала, LS. Разность LS - ES называется резервом времени для действия. Как показано на рис. 12.1, для выполнения всего плана потребуется 85 минут, каждое действие в критическом пути имеет резерв времени 0 (такое условие имеет место во всех расписаниях), а каждое действие в работе по сборке с1 имеет десятиминутное окно, в пределах которого оно может быть начато. Значения времени ES и LS для всех действий, вместе взятые, составляют расписание, представляющее собой решение данной задачи.

Ниже приведены формулы, которые служат определением значений ES и LS, а также лежат в основе алгоритма динамического программирования, применяемого для их вычисления.

Идея этого алгоритма состоит в том, что вначале следует присвоить терму ES( Start) значение 0. Затем, как только будет выявлено действие Б, такое, что все действия, непосредственно предшествующие в, имеют присвоенные значения ES, терму ES(B) присваивается максимальное из самых ранних значений времени завершения этих непосредственно предшествующих действий, где самое раннее время завершения действия определяется как самое раннее время начала плюс его продолжительность. Этот процесс повторяется до тех пор, пока каждому действию не присваивается значение ES. Значения LS вычисляются аналогичным образом, в ходе передвижения в обратном направлении от действия Finish. Проработку деталей этого алгоритма оставляем читателю в качестве упражнения.

Сложность алгоритма критического пути составляет всего лишь 0{Nb), где Ν — количество действий; b— максимальный коэффициент ветвления на входе или выходе любого действия. (Чтобы убедиться в этом, достаточно отметить, что вычисления значений LS и ES осуществляются по одному разу для каждого действия, а в каждом вычислении происходит итерация, самое большее, по b других действий.) Поэтому, если дано частичное упорядочение действий, задача поиска расписания с минимальной продолжительностью решается очень просто.