3622
правки
Изменения
м
→Доказательство корректности
{{Утверждение
|statement=Пусть уже посчитаны работы для всех <tex>j \in S(i)</tex>. Тогда, если <tex>j \in S(i)</tex>, то <tex>i</tex>-я работа
должна быть закончена до <tex>d'_j - \left\lceil \dfrac{g(i, d'_j)}{2} \right\rceil</tex>.
|proof=Рассмотрим все работы <tex>k \in S(i)</tex>, для которых <tex>d'_k \leqslant d'_j</tex>. Все эти работы будут выполнены после
окончания обработки детали с номером <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>, содержащий вершины, отсортированные в порядке
После подсчета вынужденных дедлайнов, оптимальное расписание считается жадным алгоритмом.
На каждом шаге на для обработки на станках выбираются работы с минимальным вынужденным дедлайном, для которых все необходимые
работы уже выполнены. Одновременно с этим считается максимальное опоздание.
==Доказательство корректности==
такую, что <tex>\forall k \in S(i) : d'_k </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>d_i</tex>, что невозможно в силу того, что обычные дедлайны не нарушены, либо на каком-то
<tex>j \in S(i)</tex>. В этом случае, <tex>d'_i = d'_j - \left\lceil\dfrac{g(i, d'_j)}{2}\right\rceil</tex>.
Значит, если <tex>d'_i</tex> нарушено, то будет также нарушен вынужденный дедлайн для какого-то <tex>k \in S(i)</tex>,
так как осталось меньше, чем <tex>d'_j - d'_i > \left\lceil \dfrac{g(i, d'_j)}{2} \right\rceil</tex> единиц времени. Это
противоречит условии выбора <tex>i</tex>.
}}
утверждение будет верно. Также, так как <tex>d'_k + l \leqslant d'_j + l \iff d'_k \leqslant d'_j</tex>,
<tex>(d_i + l)' = \min\{d_i + l, \min\{d'_j + l - \left\lceil\dfrac{g(i, d'_j)}{2}\right\rceil\}\}</tex> для <tex>j \in S(i)</tex>.
Вынеся за минимум общее слагаемое, по определению вынужденных дедлайнов, получим искомую формулу <tex>(d_i + l)' = d'_i + l</tex>
