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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Несущественные изменения)
м (Описание алгоритма)
Строка 27: Строка 27:
 
окончания обработки детали с номером <tex>i</tex>. Для них <tex>d'_k \leqslant 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 \dfrac{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 \dfrac{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 \dfrac{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>, содержащий вершины, отсортированные в порядке  
Строка 44: Строка 44:
 
После подсчета вынужденных дедлайнов, оптимальное расписание считается жадным алгоритмом.
 
После подсчета вынужденных дедлайнов, оптимальное расписание считается жадным алгоритмом.
 
На каждом шаге на для обработки на станках выбираются работы с минимальным вынужденным дедлайном, для которых все необходимые  
 
На каждом шаге на для обработки на станках выбираются работы с минимальным вынужденным дедлайном, для которых все необходимые  
работы уже выполнены. Одновременно с этим считается максимальное опоздание.  
+
работы уже выполнены. Одновременно с этим считается максимальное опоздание.
  
 
==Доказательство корректности==
 
==Доказательство корректности==

Версия 02:00, 5 июня 2016

[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 - \lceil \dfrac{g(i, d'_j)}{2} \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 - \lceil \dfrac{g(i, d'_j)}{2} \rceil\}\}[/math], где [math]j \in S(i)[/math].

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

См. также

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