3622
правки
Изменения
м
→Описание алгоритма
окончания обработки детали с номером <tex>i</tex>. Для них <tex>d'_k \leqslant d'_j</tex>. Пусть работу <tex>i</tex> закончили выполнять в
момент времени <tex>d</tex>. Нужно до момента времени <tex>d'_j</tex> выполнить ещё <tex>g(i, d'_j)</tex> работ.
Так как в нашем распоряжении находятся две машины, то время их выполнения будет не менее, чем <tex>\left\lceil \dfrac{g(i, d'_j)}{2} \right\rceil</tex>.
Поскольку необходимо выполнить все эти работы до <tex>d'_j</tex>, то <tex>i</tex>-я работа должна быть закончена до момента времени
<tex>d'_j - \left\lceil \dfrac{g(i, d'_j)}{2} \right\rceil</tex>.
}}
Тогда финально получаем формулу для вычисления «вынужденного» дедлайна для <tex>i</tex>-й работы:
<tex>d'_i = \min\{d_i, \min\{d'_j - \left\lceil \dfrac{g(i, d'_j)}{2} \right\rceil\}\}</tex>, где <tex>j \in S(i)</tex>.
Для вершин, исходящая степень которых равна нулю, по определению вынужденного дедлайна, считаем его равным обычному дедлайну.
Для подсчета вынужденных дедлайнов будем поддерживать список <tex>L</tex>, содержащий вершины, отсортированные в порядке
После подсчета вынужденных дедлайнов, оптимальное расписание считается жадным алгоритмом.
На каждом шаге на для обработки на станках выбираются работы с минимальным вынужденным дедлайном, для которых все необходимые
работы уже выполнены. Одновременно с этим считается максимальное опоздание.
==Доказательство корректности==
