P2precpi1Lmax

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

Полагаем, что ребра в графе ориентированы от работы, к работам, зависимым от нее. Введем понятие вынужденного дедлайна [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 \le d[/math].

Утверждение:

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Тогда финально получаем формулу для вычисления «вынужденного» дедлайна для [math]i[/math]-ой работы: [math]d'_i = \min\{d_i, \min\{d'_j - \lceil \frac{g(i, d'_j)}{2} \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].

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

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

Утверждение:

В расписании с обычными дедлайнами нет опозданий тогда и только тогда, когда нет опозданий в расписании с вынужденными дедлайнами.

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

[math]\triangleleft[/math]

Утверждение:

Если существует расписание без опоздание, то приведенный выше алгоритм найдет такое расписание.

[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 \le d'_i[/math] должна быть выполнена, так как, иначе, по алгоритму, вместо [math]i[/math] на этом шаге была бы выбрана работа [math]j[/math], имеющая меньшее [math]d'[/math] и, по построению модифицированных дедлайнов, независимая от [math]i[/math]. Рассмотрим два случая. Первый случай: в какой-то момент времени только одна работа с номером [math]k[/math], такая что [math]d'_k \le 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 \le 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 \frac{g'(k, d'_i)}{2} \right\rceil \ge \left\lceil\frac{2(x(i) - t) - 1}{2} \right\rceil = x(i) - t[/math] Из определения вынужденных дедлайнов, [math]d'_k \le d'_i - \left\lceil \frac{g(k, d'_i)}2 \right\rceil[/math] [math]\le d'_i - x(i) + t \lt x(i) + 1 - x(i) + t = t + 1[/math] Значит, работа [math]k[/math] тоже опоздала, что противоречит минимальности выбора [math]x(i)[/math]. Второй случай: в каждый момент времени такой, что [math]0 \le t \lt x(i)[/math] выполняются две работы. По написанному выше, для всех этих работ [math]j[/math], выполняется [math]d'_j \le d'_i[/math]. Тогда есть хотя бы [math]2x(i) + 1[/math] работ таких, что [math]d'_j \le d'_i \lt x(i) + 1[/math]. Их невозможно сделать за [math]x(i)[/math] времени, а значит, в каждом таком расписании есть опоздание.

[math]\triangleleft[/math]