==Описание алгоритма==
Полагаем, что ребра в графе ориентированы от работы, к работам, зависимым от нее.
Введем понятие ''вынужденного'' дедлайна <tex>d'_i</tex> — {{---}} максмальное время, до которого необходимо выполнить <tex>i</tex>-ую работу, чтобы успеть
выполнить все работы из <tex>S(i)</tex>, где <tex>S(i)</tex> — множество работ, зависящих (не обязательно непосредственно) от <tex>i</tex>-ой работы.
Заметим, что эта величина может принимать отрицательные значения.
{{Утверждение #1
|statement= В расписании с обычными дедлайнами нет опозданий тогда и только тогда, когда нет опозданий в расписании с
"вынужденными" дедлайнами.|proof= <tex>\Leftarrow</tex> Так как "вынужденные" дедлайны меньше обычныхПоскольку вынужденный дедлайн не нарушен, то в эту сторону утверждение очевидно, больший его обычный дедлайн, также не будет нарушен. <tex>\Rightarrow</tex> Напрямую следует По определению вынужденного дедлайна, <tex>d'_i</tex> {{---}} максимальное время окончания работы <tex>i</tex>, при которомещё можно успеть выполнить все работы из определения <tex>S(i)</tex>. Значит, если для <tex>i</tex> был нарушен вынужденный дедлайн, то не все работы из <tex>S(i)</tex> выполнены вовремя, то естьбыл нарушен хотя бы один обычный дедлайн, что противоречит условию. Более формально, пусть был нарушен вынужденный дедлайн. Найдём работу <tex>i</tex> с нарушенным вынужденным дедлайном, такую, что <tex>\forall k \in S(i) : d'_k </tex> {{---}} не нарушено. Это всегда можно сделать в силу ацикличности графа.Рассмотрим формулу для подсчёта вынужденного дедлайна: <tex>d'_i = \min\{d_i, \min\{d'_j - \lceil \frac{g(i, d'_j)}{2} \rceil\}\}</tex>, где <tex>j \in S(i)</tex>. Минимум достигся либо на <tex>d_i</tex>, что невозможно в силу того, что обычные дедлайны не нарушены, либо на каком-то<tex>j \in S(i)</tex>. В этом случае, <tex>d'_i = d'_j - \lceil\frac{g(i, d'_j)}{2}\rceil</tex>. Значит, если <tex>d'_i</tex> нарушено, то будет также нарушен вынужденный дедлайн для какого-то <tex>k \in S(i)</tex>, так как осталось меньше, чем <tex>d'_j - d'_i > \lceil \frac{g(i, d'_j)}{2} \rceil</tex> единиц времени. Это противоречит условии выбора <tex>i</tex>.
}}
