Изменения

{{Шаблон:Задача|definition = Даны два одинаковых станка, на которых необходимо обработать <tex>n</tex> деталей. Каждую деталь можно обрабатывать на любом станке. Время, необходимое для обработки любой детали, одинаково и равно одному. Для каждой детали известны момент времени, докоторого необходимо закончить работу над этой деталью — <tex>d_i</tex>, а также номера деталей, зависимых от нее. Необходимо минимизировать максимальное опоздание, где опоздание рассчитывается какразность между временем, когда была закончена обработка детали, и временем дедлайна для этойдетали.}}  ==Описание алгоритма==

Введем понятие "''вынужденного" '' дедлайна <tex>d'_i</tex>~{{--- }} максимальное время, до которого необходимо выполнить <tex>i</tex>-ую ю работу, чтобы успетьвыполнить все работыиз <tex>S(i)</tex>, где <tex>S(i)</tex> {{---}} множество работ, зависящие от нее зависящих (не обязательно непосредственно)от <tex>i</tex>-й работы.

Обозначим через $S(i)$~--- множество работ, зависящих от $i$-ой работы, а через <tex>g(i, d)</tex>~--- количество работ <tex>k</tex> из <tex>S(i)</tex>,таких что <tex>d'_k \le leqslant d</tex>, где <tex>k \in S(i)</tex>.Будем считать, что {{Утверждение|statement=Пусть уже посчитаны работы для всех <tex>j \in S(i)</tex>. Тогда, если <tex>j \in S(i)</tex>, тогда то <tex>i</tex>-ая я работадолжна быть закончена до <tex>d'_j - \left\lceil \fracdfrac{g(i, d'_j)}{2} \right\rceil</tex>. Это следует из факта, что для всех работ |proof=Рассмотрим все работы <tex>k \in S(i)</tex>, для которых <tex>d'_k \le 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 \fracdfrac{g(i, d'_j)}{2} \right\rceil\}\}</tex>, где <tex>j \in S(i)</tex>. Для вершин, исходящая степень которых равна нулю, вынужденный дедлайн по определению вынужденного дедлайна, считаем его равным обычному дедлайну.Для подсчета "вынужденных" дедлайнов будем поддерживать список <tex>L</tex>, содержащий вершины, отсортированных отсортированные в порядке неубывания "вынужденных" ''дедлайнов''. Для вершин''Дедлайн'' равен вынужденному дедлайну, для которых эта величина еще не посчитанаесли он уже посчитан, считаем ее равной и обычному дедлайну{{---}} в противном случае.Будем рассматривать вершины в порядке, обратном топологической сортировке графа, то есть, начиная с вершин нулевой исходящей степени. Пусть на текущем шаге мы рассматриваем работу с номером <tex>i</tex>. Перебирая вершины из <tex>S(i)</tex> в порядке списка <tex>L</tex>, пересчитываем "вынужденный" дедлайн для<tex>i</tex>-ой й вершины по формуле, указанной выше. После , после чего обновляем ее дедлайн этой вершины в списке <tex>L</tex>. Используя для нахождения <tex>S(i)</tex> алгоритм Фишера-Мейерса, можно добиться лучшей асимптотики, чем наивным методом. Данный алгоритм будет описан ниже.После подсчета "вынужденных" дедлайнов, оптимальное расписание считается жадным алгоритмом.На каждом шаге на для обработки на станках выбираются работы с минимальным "вынужденным" дедлайном, для которых все необходимые работы уже выполнены. Одновременно с этим считается максимальное опоздание.

==Доказательство корректности=={{Утверждение |about=#1

"вынужденными" дедлайнами.|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 - \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>.

{{Утверждение |about=#2

|proof= Пусть <tex>x(1), x(2),...,x(n)</tex>~{{---}} расписание, построенное этим алгоритмом, где <tex>x(i)</tex>~{{--- }} время начала обработки <tex>i</tex>-ой й детали. Пусть в этом расписании существует работа, опаздывающая по обычным дедлайнам. Согласно утверждению 1, в этом расписании также существует работа, опаздывающая по "вынужденным" дедлайнам. Пусть <tex>i</tex> {{---}} такая работа с минимальным временем начала, удолетворяющая то есть, удовлетворяющая следующему условию: <tex>d'_i < x(i) + 1</tex>. Следуя алгоритму, в каждый момент времени <tex>t</tex>, такой что <tex>t < x(i)</tex>, хотя бы одна работа с номером <tex>j</tex>, такая что <tex>d'_j \le leqslant d'_i</tex> должна быть выполнена, так как, иначе, по алгоритму, вместо <tex>i</tex>-й на этом шаге была бы выбрана работа <tex>j</tex>, имеющая меньшее <tex>d'</tex> и, по построению модифицированных дедлайнов, независимая от <tex>i</tex>.

 '''Первый случай''': в какой-то момент времени только одна работа с номером <tex>k</tex>, такая что <tex>d'_k \le leqslant d'_i</tex> выполнена.

<tex>j</tex>, которые выполнялись в момент времени с <tex>t+1</tex> до <tex>x(i)</tex> выполняется <tex>d'_j \le leqslant d'_i</tex>, кроме того, ни один станок не простаивал в течении этого периода. Все работы <tex>j</tex>, выполненные в период <tex>[t+1; x(i)]</tex>, а также, работа <tex>i</tex>, должны быть зависимы от <tex>k</tex>, потому что, иначе, только <tex>j</tex> должна быть выполнена до момента времени <tex>t+1</tex>. Так как было опоздание,  <tex>\left\lceil \dfrac{g'(k, d'_i)}{2} \right\rceil \geqslant \left\lceil\dfrac{2(x(i) - t) - 1}{2} \right\rceil = x(i) - t</tex> Из определения вынужденных дедлайнов, <tex>d'_k \leqslant d'_i - \left\lceil \dfrac{g(k, d'_i)}2 \right\rceil</tex><tex>\leqslant d'_i - x(i) + t < x(i) + 1 - x(i) + t = t + 1</tex> Значит, работа <tex>k</tex> тоже опоздала, что противоречит минимальности выбора <tex>x(i)</tex>. '''Второй случай''': в каждый момент времени такой, что <tex>0 \leqslant t < x(i)</tex> выполняются две работы. По написанному выше,для всех этих работ <tex>j</tex>, выполняется <tex>d'_j \leqslant d'_i</tex>.  Тогда есть хотя бы <tex>2x(i) + 1</tex> работ таких, что <tex>d'_j \leqslant d'_i < x(i) + 1</tex>. Их невозможно сделать за <tex>x(i)</tex> времени, а значит, в каждом таком расписании есть опоздание.}} {{Утверждение|about=#3|statement=При сдвиге всех <tex>d_i</tex> на <tex>l</tex>, <tex>d'_i</tex> сдвинутся также на это число.|proof=Для работ, от которых ничего не зависит, по определению <tex>d'_i = d_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>}} {{Теорема|statement=Алгоритм строит оптимальное расписание.|proof=Пускай каким-то образом было вычислено оптимальное значение <tex>l_{max}</tex>. Тогда, по второму утверждению, если сдвинуть вседедлайны на <tex>l_{max}</tex>, то алгоритм получит для них оптимальное расписание.  По третьему утверждению, для любого сдвига будет получено расписание с одним и тем же опозданием. Значит, для сдвига на <tex>l_{max}</tex> оно также будет оптимальным.  В силу того, что для любого сдвига будет построено оптимальное расписание, алгоритм находит оптимальное расписание.