P2precpi1Lmax — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: « =Описание алгоритма= Полагаем, что ребра в графе ориентированы от работы, к работам, зави...»)
 
м (rollbackEdits.php mass rollback)
 
(не показано 14 промежуточных версий 6 участников)
Строка 1: Строка 1:
 +
<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>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>S(i)</tex>,
+
Обозначим через <tex>g(i, d)</tex> количество работ <tex>k</tex> из <tex>S(i)</tex>,
таких что <tex>d'_k \le d</tex>, где <tex>k \in S(i)</tex>.
+
таких что <tex>d'_k \leqslant d</tex>.
Будем считать, что уже посчитаны работы для всех <tex>j \in S(i)</tex>. Тогда, если <tex>j \in S(i)</tex>, тогда <tex>i</tex>-ая работа
+
 
должна быть закончена до <tex>d'_j - \lceil \frac{g(i, d'_j)}{2} \rceil</tex>. Это следует из факта, что для всех работ <tex>k \in S(i)</tex>,  
+
{{Утверждение
для которых <tex>d'_k \le d'_j</tex> должны быть выполнены на двух машинах после окончания времени обработки <tex>i</tex>-ой детали,  
+
|statement=Пусть уже посчитаны работы для всех <tex>j \in S(i)</tex>. Тогда, если <tex>j \in S(i)</tex>, то <tex>i</tex>-я работа
но до времени <tex>d'_j</tex>. Тогда финально получаем формулу для вычисления "вынужденного" дедлайна для <tex>i</tex>-ой работы:  
+
должна быть закончена до <tex>d'_j - \left\lceil \dfrac{g(i, d'_j)}{2} \right\rceil</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>.  
+
|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>L</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>i</tex>. Перебирая вершины из <tex>S(i)</tex> в порядке списка <tex>L</tex>, пересчитываем "вынужденный" дедлайн для
+
<tex>d'_j - \left\lceil \dfrac{g(i, d'_j)}{2} \right\rceil</tex>.
<tex>i</tex>-ой вершины по формуле, указанной выше. После чего обновляем ее дедлайн в списке <tex>L</tex>. Используя для нахождения
+
}}
<tex>S(i)</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>i</tex>. Перебирая вершины из <tex>S(i)</tex> в порядке списка <tex>L</tex>, пересчитываем вынужденный дедлайн для
 +
<tex>i</tex>-й вершины по формуле, указанной выше, после чего обновляем дедлайн этой вершины в списке <tex>L</tex>.  
 +
 
 +
После подсчета вынужденных дедлайнов, оптимальное расписание считается жадным алгоритмом.
 +
На каждом шаге на для обработки на станках выбираются работы с минимальным вынужденным дедлайном, для которых все необходимые  
 +
работы уже выполнены. Одновременно с этим считается максимальное опоздание.
  
=Доказательство корректности=
+
==Доказательство корректности==
{{Утверждение #1
+
{{Утверждение  
 +
|about=#1
 
|statement= В расписании с обычными дедлайнами нет опозданий тогда и только тогда, когда нет опозданий в расписании с
 
|statement= В расписании с обычными дедлайнами нет опозданий тогда и только тогда, когда нет опозданий в расписании с
"вынужденными" дедлайнами.
+
вынужденными дедлайнами.
|proof= <tex>\Leftarrow</tex> Так как "вынужденные" дедлайны меньше обычных, то в эту сторону утверждение очевидно.
+
|proof=  
<tex>\Rightarrow</tex> Напрямую следует из определения вынужденного дедлайна.
+
<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>.
 
}}
 
}}
  
{{Утверждение #2
+
{{Утверждение  
 +
|about=#2
 
|statement= Если существует расписание без опоздание, то приведенный выше алгоритм найдет такое расписание.
 
|statement= Если существует расписание без опоздание, то приведенный выше алгоритм найдет такое расписание.
|proof= Пусть <tex>x(1), x(2),...,x(n)</tex>~---расписание, построенное этим алгоритмом, где <tex>x(i)</tex>~--- время  
+
|proof= Пусть <tex>x(1), x(2),...,x(n)</tex> {{---}} расписание, построенное этим алгоритмом, где <tex>x(i)</tex> {{---}} время  
начала обработки <tex>i</tex>-ой детали. Пусть в этом расписании существует работа, опаздывающая по обычным дедлайнам. Согласно  
+
начала обработки <tex>i</tex>-й детали. Пусть в этом расписании существует работа, опаздывающая по обычным дедлайнам. Согласно  
утверждению 1, в этом расписании также существует работа, опаздывающая по "вынужденным" дедлайнам. Пусть <tex>i</tex> работа с  
+
утверждению 1, в этом расписании также существует работа, опаздывающая по "вынужденным" дедлайнам. Пусть <tex>i</tex> {{---}} такая работа с  
минимальным временем начала, удолетворяющая следующему условию: <tex>d'_i < x(i) + 1</tex>. Следуя алгоритму, в каждый момент времени  
+
минимальным временем начала, то есть, удовлетворяющая следующему условию: <tex>d'_i < x(i) + 1</tex>.  
<tex>t</tex>, такой что <tex>t < x(i)</tex>, хотя бы одна работа с номером <tex>j</tex>, такая что <tex>d'_j \le d'_i</tex> должна  
+
Следуя алгоритму, в каждый момент времени  
быть выполнена.
+
<tex>t</tex>, такой что <tex>t < x(i)</tex>, хотя бы одна работа с номером <tex>j</tex>, такая что <tex>d'_j \leqslant d'_i</tex> должна  
 +
быть выполнена, так как, иначе, по алгоритму, вместо <tex>i</tex>-й на этом шаге была бы выбрана работа <tex>j</tex>, имеющая меньшее
 +
<tex>d'</tex> и, по построению модифицированных дедлайнов, независимая от <tex>i</tex>.
 
Рассмотрим два случая.
 
Рассмотрим два случая.
Первый случай: в какой-то момент времени только одна работа с номером <tex>k</tex>, такая что <tex>d'_k \le d'_i</tex> выполнена.
+
 
 +
'''Первый случай''': в какой-то момент времени только одна работа с номером <tex>k</tex>, такая что <tex>d'_k \leqslant d'_i</tex> выполнена.
 
Выберем максимальное время <tex>t</tex>, такое что <tex>t < x(i)</tex>, обладающее таким свойством. Тогда для всех работ c номером
 
Выберем максимальное время <tex>t</tex>, такое что <tex>t < x(i)</tex>, обладающее таким свойством. Тогда для всех работ c номером
<tex>j</tex>, которые выполнялись в момент времени с <tex>t+1</tex> до <tex>x(i)</tex> выполняется <tex>d'_j \le d'_i</tex>, кроме того
+
<tex>j</tex>, которые выполнялись в момент времени с <tex>t+1</tex> до <tex>x(i)</tex> выполняется <tex>d'_j \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> оно также будет оптимальным.
 +
 
 +
В силу того, что для любого сдвига будет построено оптимальное расписание, алгоритм находит оптимальное расписание.  
 
}}
 
}}
 +
 +
==Сложность алгоритма==
 +
В алгоритме требуется знать для двух произвольных работ, зависит ли, возможно, не непосредственно, одна от другой. Для этого нужно транзитивно замкнуть граф по отношению зависимости. Это можно сделать несколькими способами. Первый и самый простой {{---}} за <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.
 +
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Теория расписаний]]

Текущая версия на 19:35, 4 сентября 2022

[math]P2 \mid prec, p_i=1 \mid L_{max}[/math]


Задача:
Даны два одинаковых станка, на которых необходимо обработать [math]n[/math] деталей.

Каждую деталь можно обрабатывать на любом станке. Время, необходимое для обработки любой детали, одинаково и равно одному. Для каждой детали известны момент времени, до которого необходимо закончить работу над этой деталью — [math]d_i[/math], а также номера деталей, зависимых от нее. Необходимо минимизировать максимальное опоздание, где опоздание рассчитывается как разность между временем, когда была закончена обработка детали, и временем дедлайна для этой

детали.


Описание алгоритма

Полагаем, что ребра в графе ориентированы от работы, к работам, зависимым от нее. Введем понятие вынужденного дедлайна [math]d'_i[/math] — максимальное время, до которого необходимо выполнить [math]i[/math]-ю работу, чтобы успеть выполнить все работы из [math]S(i)[/math], где [math]S(i)[/math] — множество работ, зависящих (не обязательно непосредственно) от [math]i[/math]-й работы. Заметим, что эта величина может принимать отрицательные значения. Обозначим через [math]g(i, d)[/math] количество работ [math]k[/math] из [math]S(i)[/math], таких что [math]d'_k \leqslant d[/math].

Утверждение:
Пусть уже посчитаны работы для всех [math]j \in S(i)[/math]. Тогда, если [math]j \in S(i)[/math], то [math]i[/math]-я работа должна быть закончена до [math]d'_j - \left\lceil \dfrac{g(i, d'_j)}{2} \right\rceil[/math].
[math]\triangleright[/math]

Рассмотрим все работы [math]k \in S(i)[/math], для которых [math]d'_k \leqslant d'_j[/math]. Все эти работы будут выполнены после окончания обработки детали с номером [math]i[/math]. Для них [math]d'_k \leqslant d'_j[/math]. Пусть работу [math]i[/math] закончили выполнять в момент времени [math]d[/math]. Нужно до момента времени [math]d'_j[/math] выполнить ещё [math]g(i, d'_j)[/math] работ. Так как в нашем распоряжении находятся две машины, то время их выполнения будет не менее, чем [math]\left\lceil \dfrac{g(i, d'_j)}{2} \right\rceil[/math]. Поскольку необходимо выполнить все эти работы до [math]d'_j[/math], то [math]i[/math]-я работа должна быть закончена до момента времени

[math]d'_j - \left\lceil \dfrac{g(i, d'_j)}{2} \right\rceil[/math].
[math]\triangleleft[/math]

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

После подсчета вынужденных дедлайнов, оптимальное расписание считается жадным алгоритмом. На каждом шаге на для обработки на станках выбираются работы с минимальным вынужденным дедлайном, для которых все необходимые работы уже выполнены. Одновременно с этим считается максимальное опоздание.

Доказательство корректности

Утверждение (#1):
В расписании с обычными дедлайнами нет опозданий тогда и только тогда, когда нет опозданий в расписании с вынужденными дедлайнами.
[math]\triangleright[/math]

[math]\Leftarrow[/math] Поскольку вынужденный дедлайн не нарушен, то, больший его обычный дедлайн, также не будет нарушен.

[math]\Rightarrow[/math] По определению вынужденного дедлайна, [math]d'_i[/math] — максимальное время окончания работы [math]i[/math], при котором ещё можно успеть выполнить все работы из [math]S(i)[/math]. Значит, если для [math]i[/math] был нарушен вынужденный дедлайн, то не все работы из [math]S(i)[/math] выполнены вовремя, то есть был нарушен хотя бы один обычный дедлайн, что противоречит условию.

Более формально, пусть был нарушен вынужденный дедлайн. Найдём работу [math]i[/math] с нарушенным вынужденным дедлайном, такую, что [math]\forall k \in S(i) : d'_k [/math] — не нарушено. Это всегда можно сделать в силу ацикличности графа. Рассмотрим формулу для подсчёта вынужденного дедлайна: [math]d'_i = \min\{d_i, \min\{d'_j - \left\lceil \dfrac{g(i, d'_j)}{2} \right\rceil\}\}[/math], где [math]j \in S(i)[/math].

Минимум достигатся либо на [math]d_i[/math], что невозможно в силу того, что обычные дедлайны не нарушены, либо на каком-то [math]j \in S(i)[/math]. В этом случае, [math]d'_i = d'_j - \left\lceil\dfrac{g(i, d'_j)}{2}\right\rceil[/math]. Значит, если [math]d'_i[/math] нарушено, то будет также нарушен вынужденный дедлайн для какого-то [math]k \in S(i)[/math], так как осталось меньше, чем [math]d'_j - d'_i \gt \left\lceil \dfrac{g(i, d'_j)}{2} \right\rceil[/math] единиц времени. Это

противоречит условии выбора [math]i[/math].
[math]\triangleleft[/math]
Утверждение (#2):
Если существует расписание без опоздание, то приведенный выше алгоритм найдет такое расписание.
[math]\triangleright[/math]

Пусть [math]x(1), x(2),...,x(n)[/math] — расписание, построенное этим алгоритмом, где [math]x(i)[/math] — время начала обработки [math]i[/math]-й детали. Пусть в этом расписании существует работа, опаздывающая по обычным дедлайнам. Согласно утверждению 1, в этом расписании также существует работа, опаздывающая по "вынужденным" дедлайнам. Пусть [math]i[/math] — такая работа с минимальным временем начала, то есть, удовлетворяющая следующему условию: [math]d'_i \lt x(i) + 1[/math]. Следуя алгоритму, в каждый момент времени [math]t[/math], такой что [math]t \lt x(i)[/math], хотя бы одна работа с номером [math]j[/math], такая что [math]d'_j \leqslant d'_i[/math] должна быть выполнена, так как, иначе, по алгоритму, вместо [math]i[/math]-й на этом шаге была бы выбрана работа [math]j[/math], имеющая меньшее [math]d'[/math] и, по построению модифицированных дедлайнов, независимая от [math]i[/math]. Рассмотрим два случая.

Первый случай: в какой-то момент времени только одна работа с номером [math]k[/math], такая что [math]d'_k \leqslant d'_i[/math] выполнена. Выберем максимальное время [math]t[/math], такое что [math]t \lt x(i)[/math], обладающее таким свойством. Тогда для всех работ c номером [math]j[/math], которые выполнялись в момент времени с [math]t+1[/math] до [math]x(i)[/math] выполняется [math]d'_j \leqslant d'_i[/math], кроме того, ни один станок не простаивал в течении этого периода. Все работы [math]j[/math], выполненные в период [math][t+1; x(i)][/math], а также, работа [math]i[/math], должны быть зависимы от [math]k[/math], потому что, иначе, только [math]j[/math] должна быть выполнена до момента времени [math]t+1[/math]. Так как было опоздание,

[math]\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[/math]

Из определения вынужденных дедлайнов, [math]d'_k \leqslant d'_i - \left\lceil \dfrac{g(k, d'_i)}2 \right\rceil[/math] [math]\leqslant d'_i - x(i) + t \lt x(i) + 1 - x(i) + t = t + 1[/math]

Значит, работа [math]k[/math] тоже опоздала, что противоречит минимальности выбора [math]x(i)[/math].

Второй случай: в каждый момент времени такой, что [math]0 \leqslant t \lt x(i)[/math] выполняются две работы. По написанному выше, для всех этих работ [math]j[/math], выполняется [math]d'_j \leqslant d'_i[/math].

Тогда есть хотя бы [math]2x(i) + 1[/math] работ таких, что [math]d'_j \leqslant d'_i \lt x(i) + 1[/math].

Их невозможно сделать за [math]x(i)[/math] времени, а значит, в каждом таком расписании есть опоздание.
[math]\triangleleft[/math]
Утверждение (#3):
При сдвиге всех [math]d_i[/math] на [math]l[/math], [math]d'_i[/math] сдвинутся также на это число.
[math]\triangleright[/math]

Для работ, от которых ничего не зависит, по определению [math]d'_i = d_i[/math], а, значит, для них утверждение верно.

Рассмотрим остальные в порядке топологической сортировки. Тогда, по индукции, для всех потомков рассматриваемой вершины утверждение будет верно. Также, так как [math]d'_k + l \leqslant d'_j + l \iff d'_k \leqslant d'_j[/math],

[math](d_i + l)' = \min\{d_i + l, \min\{d'_j + l - \left\lceil\dfrac{g(i, d'_j)}{2}\right\rceil\}\}[/math] для [math]j \in S(i)[/math].

Вынеся за минимум общее слагаемое, по определению вынужденных дедлайнов, получим искомую формулу [math](d_i + l)' = d'_i + l[/math]
[math]\triangleleft[/math]
Теорема:
Алгоритм строит оптимальное расписание.
Доказательство:
[math]\triangleright[/math]

Пускай каким-то образом было вычислено оптимальное значение [math]l_{max}[/math]. Тогда, по второму утверждению, если сдвинуть все дедлайны на [math]l_{max}[/math], то алгоритм получит для них оптимальное расписание.

По третьему утверждению, для любого сдвига будет получено расписание с одним и тем же опозданием. Значит, для сдвига на [math]l_{max}[/math] оно также будет оптимальным.

В силу того, что для любого сдвига будет построено оптимальное расписание, алгоритм находит оптимальное расписание.
[math]\triangleleft[/math]

Сложность алгоритма

В алгоритме требуется знать для двух произвольных работ, зависит ли, возможно, не непосредственно, одна от другой. Для этого нужно транзитивно замкнуть граф по отношению зависимости. Это можно сделать несколькими способами. Первый и самый простой — за [math]\mathcal{O}(n^3)[/math] алгоритмом Флойда-Уоршелла. Второй — при помощи метода четырех русских за [math]\mathcal{O}(\dfrac{n^3}{\log n})[/math]. Третий — применить алгоритм Фишера-Мейера для построения замыкания графа за [math]\mathcal{O}(n^{\log_2 7})[/math].

При подсчете вынужденных дедлайнов, за [math]\mathcal{O}(n)[/math] считается вынужденный дедлайн одной работы. Так как всего работ [math]n[/math], суммарное время подсчета вынужденных дедлайнов — [math]\mathcal{O}(n^2)[/math].

При, непосредственно, составлении расписания, на каждом шаге за [math]\mathcal{O}(n)[/math] обрабатываются одна или две работы. Значит, все работы будут обработаны также за [math]\mathcal{O}(n^2)[/math].

Итоговая сложность — [math]\mathcal{O}(TrCl + n^2)[/math].

См. также

Источники информации