P2precpi1Lmax

[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].

См. также

• [math]P \mid pmtn, r_i \mid L_{max}[/math]

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

• M.J. Fischer and A.R. Meyer, «Boolean Matrix Multiplication and Transitive Closure».
• P. Brucker. «Scheduling Algorithms» (2006), 5th edition, стр. 145-149.