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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 7 промежуточных версий 4 участников)
Строка 1: Строка 1:
==Описание задачи==
+
<tex dpi = "200" >P2 \mid prec, p_i=1 \mid L_{max}</tex>
 +
 
 +
{{Шаблон:Задача
 +
|definition =  
 
Даны два одинаковых станка, на которых необходимо обработать <tex>n</tex> деталей.  
 
Даны два одинаковых станка, на которых необходимо обработать <tex>n</tex> деталей.  
 
Каждую деталь можно обрабатывать на любом станке. Время, необходимое для обработки любой детали,  
 
Каждую деталь можно обрабатывать на любом станке. Время, необходимое для обработки любой детали,  
Строка 7: Строка 10:
 
разность между временем, когда была закончена обработка детали, и временем дедлайна для этой
 
разность между временем, когда была закончена обработка детали, и временем дедлайна для этой
 
детали.
 
детали.
 +
}}
 +
  
 
==Описание алгоритма==
 
==Описание алгоритма==
 
Полагаем, что ребра в графе ориентированы от работы, к работам, зависимым от нее.
 
Полагаем, что ребра в графе ориентированы от работы, к работам, зависимым от нее.
Введем понятие ''вынужденного'' дедлайна <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>-ой работы.
+
выполнить все работы из <tex>S(i)</tex>, где <tex>S(i)</tex> {{---}} множество работ, зависящих (не обязательно непосредственно) от <tex>i</tex>-й работы.
 
Заметим, что эта величина может принимать отрицательные значения.
 
Заметим, что эта величина может принимать отрицательные значения.
 
Обозначим через <tex>g(i, d)</tex> количество работ <tex>k</tex> из <tex>S(i)</tex>,
 
Обозначим через <tex>g(i, d)</tex> количество работ <tex>k</tex> из <tex>S(i)</tex>,
таких что <tex>d'_k \le d</tex>.
+
таких что <tex>d'_k \leqslant d</tex>.
  
 
{{Утверждение
 
{{Утверждение
|statement=Пусть уже посчитаны работы для всех <tex>j \in S(i)</tex>. Тогда, если <tex>j \in S(i)</tex>, то <tex>i</tex>-ая работа
+
|statement=Пусть уже посчитаны работы для всех <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>d'_j - \left\lceil \dfrac{g(i, d'_j)}{2} \right\rceil</tex>.  
|proof=Рассмотрим все работы <tex>k \in S(i)</tex>, для которых <tex>d'_k \le d'_j</tex>. Все эти работы будут выполнены после  
+
|proof=Рассмотрим все работы <tex>k \in S(i)</tex>, для которых <tex>d'_k \leqslant d'_j</tex>. Все эти работы будут выполнены после  
окончания обработки детали с номером <tex>i</tex>. Для них <tex>d'_k \le d'_j</tex>. Пусть работу <tex>i</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>d</tex>. Нужно до момента времени <tex>d'_j</tex> выполнить ещё <tex>g(i, d'_j)</tex> работ.  
Так как в нашем распоряжении находятся две машины, то время их выполнения будет не менее, чем <tex>\lceil \frac{g(i, d'_j)}{2} \rceil</tex>.  
+
Так как в нашем распоряжении находятся две машины, то время их выполнения будет не менее, чем <tex>\left\lceil \dfrac{g(i, d'_j)}{2} \right\rceil</tex>.  
Поскольку необходимо выполнить все эти работы до <tex>d'_j</tex>, то <tex>i</tex>-ая работа должна быть закончена до момента времени
+
Поскольку необходимо выполнить все эти работы до <tex>d'_j</tex>, то <tex>i</tex>-я работа должна быть закончена до момента времени
<tex>d'_j - \lceil \frac{g(i, d'_j)}{2} \rceil</tex>.
+
<tex>d'_j - \left\lceil \dfrac{g(i, d'_j)}{2} \right\rceil</tex>.
 
}}
 
}}
  
Тогда финально получаем формулу для вычисления «вынужденного» дедлайна для <tex>i</tex>-ой работы:  
+
Тогда финально получаем формулу для вычисления «вынужденного» дедлайна для <tex>i</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>.  
+
<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>L</tex>, содержащий вершины, отсортированные в порядке  
Строка 35: Строка 40:
 
Пусть на текущем шаге мы рассматриваем работу с  
 
Пусть на текущем шаге мы рассматриваем работу с  
 
номером <tex>i</tex>. Перебирая вершины из <tex>S(i)</tex> в порядке списка <tex>L</tex>, пересчитываем вынужденный дедлайн для
 
номером <tex>i</tex>. Перебирая вершины из <tex>S(i)</tex> в порядке списка <tex>L</tex>, пересчитываем вынужденный дедлайн для
<tex>i</tex>-ой вершины по формуле, указанной выше, после чего обновляем дедлайн этой вершины в списке <tex>L</tex>.  
+
<tex>i</tex>-й вершины по формуле, указанной выше, после чего обновляем дедлайн этой вершины в списке <tex>L</tex>.  
  
 
После подсчета вынужденных дедлайнов, оптимальное расписание считается жадным алгоритмом.
 
После подсчета вынужденных дедлайнов, оптимальное расписание считается жадным алгоритмом.
 
На каждом шаге на для обработки на станках выбираются работы с минимальным вынужденным дедлайном, для которых все необходимые  
 
На каждом шаге на для обработки на станках выбираются работы с минимальным вынужденным дедлайном, для которых все необходимые  
работы уже выполнены. Одновременно с этим считается максимальное опоздание.  
+
работы уже выполнены. Одновременно с этим считается максимальное опоздание.
  
 
==Доказательство корректности==
 
==Доказательство корректности==
Строка 58: Строка 63:
 
такую, что <tex>\forall k \in S(i) : d'_k </tex> {{---}} не нарушено. Это всегда можно сделать в силу ацикличности графа.
 
такую, что <tex>\forall k \in S(i) : d'_k </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>.
+
<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>d_i</tex>, что невозможно в силу того, что обычные дедлайны не нарушены, либо на каком-то
<tex>j \in S(i)</tex>. В этом случае, <tex>d'_i = d'_j - \lceil\frac{g(i, d'_j)}{2}\rceil</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'_i</tex> нарушено, то будет также нарушен вынужденный дедлайн для какого-то <tex>k \in S(i)</tex>,  
так как осталось меньше, чем <tex>d'_j - d'_i > \lceil \frac{g(i, d'_j)}{2} \rceil</tex> единиц времени. Это  
+
так как осталось меньше, чем <tex>d'_j - d'_i > \left\lceil \dfrac{g(i, d'_j)}{2} \right\rceil</tex> единиц времени. Это  
 
противоречит условии выбора <tex>i</tex>.
 
противоречит условии выбора <tex>i</tex>.
 
}}
 
}}
Строка 71: Строка 76:
 
|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>i</tex>на этом шаге была бы выбрана работа <tex>j</tex>, имеющая меньшее  
 
<tex>d'</tex> и, по построению модифицированных дедлайнов, независимая от <tex>i</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>j</tex>, выполненные в период <tex>[t+1; x(i)]</tex>, а также,  
 
работа <tex>i</tex>, должны быть зависимы от <tex>k</tex>, потому что, иначе, только <tex>j</tex> должна быть выполнена до  
 
работа <tex>i</tex>, должны быть зависимы от <tex>k</tex>, потому что, иначе, только <tex>j</tex> должна быть выполнена до  
 
момента времени <tex>t+1</tex>. Так как было опоздание,  
 
момента времени <tex>t+1</tex>. Так как было опоздание,  
  
<tex>\left\lceil \frac{g'(k, d'_i)}{2} \right\rceil \ge \left\lceil\frac{2(x(i) - t) - 1}{2} \right\rceil = x(i) - t</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 \le d'_i - \left\lceil \frac{g(k, d'_i)}2 \right\rceil</tex>
+
<tex>d'_k \leqslant d'_i - \left\lceil \dfrac{g(k, d'_i)}2 \right\rceil</tex>
<tex>\le d'_i - x(i) + t < x(i) + 1 - x(i) + t = t + 1</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>k</tex> тоже опоздала, что противоречит минимальности выбора <tex>x(i)</tex>.
  
'''Второй случай''': в каждый момент времени такой, что <tex>0 \le t < x(i)</tex> выполняются две работы. По написанному выше,
+
'''Второй случай''': в каждый момент времени такой, что <tex>0 \leqslant t < x(i)</tex> выполняются две работы. По написанному выше,
для всех этих работ <tex>j</tex>, выполняется <tex>d'_j \le d'_i</tex>.  
+
для всех этих работ <tex>j</tex>, выполняется <tex>d'_j \leqslant d'_i</tex>.  
  
Тогда есть хотя бы <tex>2x(i) + 1</tex> работ таких, что <tex>d'_j \le d'_i < x(i) + 1</tex>.  
+
Тогда есть хотя бы <tex>2x(i) + 1</tex> работ таких, что <tex>d'_j \leqslant d'_i < x(i) + 1</tex>.  
 
Их невозможно сделать за <tex>x(i)</tex> времени, а значит, в каждом таком расписании есть опоздание.
 
Их невозможно сделать за <tex>x(i)</tex> времени, а значит, в каждом таком расписании есть опоздание.
 
}}
 
}}
Строка 109: Строка 114:
  
 
Рассмотрим остальные в порядке топологической сортировки. Тогда, по индукции, для всех потомков рассматриваемой вершины
 
Рассмотрим остальные в порядке топологической сортировки. Тогда, по индукции, для всех потомков рассматриваемой вершины
утверждение будет верно. Также, так как <tex>d'_k + l \le d'_j + l \iff d'_k \le d'_j</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 - \lceil\frac{g(i, d'_j)}{2}\rceil\}\}</tex> для <tex>j \in S(i)</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>
 
Вынеся за минимум общее слагаемое, по определению вынужденных дедлайнов, получим искомую формулу <tex>(d_i + l)' = d'_i + l</tex>
Строка 117: Строка 122:
  
 
{{Теорема
 
{{Теорема
|statement=Алгоритм строит оптимальное расписание
+
|statement=Алгоритм строит оптимальное расписание.
 
|proof=
 
|proof=
 
Пускай каким-то образом было вычислено оптимальное значение <tex>l_{max}</tex>. Тогда, по второму утверждению, если сдвинуть все
 
Пускай каким-то образом было вычислено оптимальное значение <tex>l_{max}</tex>. Тогда, по второму утверждению, если сдвинуть все
Строка 129: Строка 134:
  
 
==Сложность алгоритма==
 
==Сложность алгоритма==
В алгоритме требуется знать для двух произвольных работ, зависит ли, возможно, не непосредственно, одна от другой. Для этого нужно транзитивно замкнуть граф по отношению зависимости. Это можно сделать несколькими способами. Первый и самый простой {{---}} за <tex>O(n^3)</tex> алгоритмом Флойда-Уоршалла. Второй {{---}} при помощи метода четырех русских за <tex>O(\frac{n^3}{\log n})</tex>. Третий {{---}} применить алгоритм Фишера-Мейера для построения замыкания графа за <tex>O(n^{\log_2 7})</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>O(n)</tex> считается вынужденный дедлайн одной работы. Так как всего работ <tex>n</tex>, суммарное время подсчета вынужденных дедлайнов {{---}} <tex>O(n^2)</tex>.
+
Итоговая сложность {{---}} <tex>\mathcal{O}(TrCl + n^2)</tex>.
  
При, непосредственно, составлении расписания, на каждом шаге за <tex>O(n)</tex> обрабатываются одна или две работы. Значит, все работы будут обработаны также за <tex>O(n^2)</tex>.
+
== См. также ==
 +
* [[PpmtnriLmax|<tex>P \mid pmtn, r_i \mid L_{max}</tex>]]
  
Итоговая сложность {{---}} <tex>O(TrCl + n^2)</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.
  
==Ссылки==
+
[[Категория: Алгоритмы и структуры данных]]
[http://rjlipton.files.wordpress.com/2009/10/matrix1971.pdf| Алгоритм Фишера-Мейера]
+
[[Категория: Теория расписаний]]

Текущая версия на 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].

См. также

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