3622
правки
Изменения
м
→Доказательство корректности
<tex dpi = "200" >P2 \mid prec, p_i=1 \mid L_{max}</tex>
{{Шаблон:Задача
|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>-ой й работы.
Заметим, что эта величина может принимать отрицательные значения.
Обозначим через <tex>g(i, d)</tex> количество работ <tex>k</tex> из <tex>S(i)</tex>,
таких что <tex>d'_k \le leqslant d</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 \le leqslant d'_j</tex>. Пусть работу <tex>i</tex> закончили выполнять в
момент времени <tex>d</tex>. Нужно до момента времени <tex>d'_j</tex> выполнить ещё <tex>g(i, d'_j)</tex> работ.
Так как в нашем распоряжении находятся две машины, то время их выполнения будет не менее, чем <tex>\left\lceil \fracdfrac{g(i, d'_j)}{2} \right\rceil</tex>. Поскольку необходимо выполнить все эти работы до <tex>d'_j</tex>, то <tex>i</tex>-ая я работа должна быть закончена до момента времени<tex>d'_j - \left\lceil \fracdfrac{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>\forall k \in S(i) : d'_k </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>d_i</tex>, что невозможно в силу того, что обычные дедлайны не нарушены, либо на каком-то<tex>j \in S(i)</tex>. В этом случае, <tex>d'_i = d'_j - \left\lceil\fracdfrac{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 \fracdfrac{g(i, d'_j)}{2} \right\rceil</tex> единиц времени. Это
противоречит условии выбора <tex>i</tex>.
}}
|statement= Если существует расписание без опоздание, то приведенный выше алгоритм найдет такое расписание.
|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>t</tex>, такое что <tex>t < x(i)</tex>, обладающее таким свойством. Тогда для всех работ c номером
<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 \fracdfrac{g'(k, d'_i)}{2} \right\rceil \ge geqslant \left\lceil\fracdfrac{2(x(i) - t) - 1}{2} \right\rceil = x(i) - t</tex>
Из определения вынужденных дедлайнов,
<tex>d'_k \le leqslant d'_i - \left\lceil \fracdfrac{g(k, d'_i)}2 \right\rceil</tex><tex>\le leqslant d'_i - x(i) + t < x(i) + 1 - x(i) + t = t + 1</tex>
Значит, работа <tex>k</tex> тоже опоздала, что противоречит минимальности выбора <tex>x(i)</tex>.
'''Второй случай''': в каждый момент времени такой, что <tex>0 \le leqslant t < x(i)</tex> выполняются две работы. По написанному выше,для всех этих работ <tex>j</tex>, выполняется <tex>d'_j \le leqslant d'_i</tex>.
Тогда есть хотя бы <tex>2x(i) + 1</tex> работ таких, что <tex>d'_j \le leqslant d'_i < x(i) + 1</tex>.
Их невозможно сделать за <tex>x(i)</tex> времени, а значит, в каждом таком расписании есть опоздание.
}}
Рассмотрим остальные в порядке топологической сортировки. Тогда, по индукции, для всех потомков рассматриваемой вершины
утверждение будет верно. Также, так как <tex>d'_k + l \le leqslant d'_j + l \iff d'_k \le leqslant d'_j</tex>,
<tex>(d_i + l)' = \min\{d_i + l, \min\{d'_j + l - \left\lceil\fracdfrac{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>\mathcal{O}(n^3)</tex> алгоритмом Флойда-Уоршелла. Второй {{---}} при помощи метода четырех русских за <tex>\mathcal{O}(\dfrac{n^3}{\log n})</tex>. Третий {{---}} применить алгоритм Фишера-Мейера для построения замыкания графа за <tex>\mathcal{O}(n^{\log_2 7})</tex>.
При подсчете вынужденных дедлайнов, за <tex>\mathcal{O}(n)</tex> считается вынужденный дедлайн одной работы. Так как всего работ <tex>n</tex>, суммарное время подсчета вынужденных дедлайнов {{---}} <tex>\mathcal{O}(n^2)</tex>.
При, непосредственно, составлении расписания, на каждом шаге за <tex>\mathcal{O}(n)</tex> обрабатываются одна или две работы. Значит, все работы будут обработаны также за <tex>\mathcal{O}(n^2)</tex>.
Итоговая сложность {{---}} <tex>\mathcal{O}(TrCl + n^2)</tex>.
== См. также ==
* [[PpmtnriLmax|<tex>P \mid pmtn, r_i \mid L_{max}</tex>]]
==Источники информации==
* M.J. Fischer and A.R. Meyer, [http://rjlipton.files.wordpress.com/2009/10/matrix1971.pdf «Boolean Matrix Multiplication and Transitive Closure»].
* P. Brucker. «Scheduling Algorithms» (2006), 5th edition, стр. 145-149.
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Теория расписаний]]
