P2precpi1Lmax

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

Полагаем, что ребра в графе ориентированы от работы, к работам, зависимым от нее. Введем понятие "вынужденного" дедлайна [math]d'_i[/math]~--- время, до которого необходимо выполнить [math]i[/math]-ую работу, чтобы успеть выполнить все работы, зависящие от нее (не обязательно непосредственно). Заметим, что эта величина может принимать отрицательные значения. Обозначим через $S(i)$~--- множество работ, зависящих от $i$-ой работы, а через [math]g(i, d)[/math]~--- количество работ из [math]S(i)[/math], таких что [math]d'_k \le d[/math], где [math]k \in S(i)[/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]k \in S(i)[/math], для которых [math]d'_k \le d'_j[/math] должны быть выполнены на двух машинах после окончания времени обработки [math]i[/math]-ой детали, но до времени [math]d'_j[/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]S(i)[/math] алгоритм Фишера-Мейерса, можно добиться лучшей асимптотики, чем наивным методом. Данный алгоритм будет описан ниже. После подсчета "вынужденных" дедлайнов, оптимальное расписание считается жадным алгоритмом. На каждом шаге на для обработки на станках выбираются работы с минимальным "вынужденным" дедлайном, для которых все необходимые работы уже выполнены. Одновременно с этим считается максимальное опоздание.

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

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

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

[math]\triangleright[/math]

[math]\Leftarrow[/math] Так как "вынужденные" дедлайны меньше обычных, то в эту сторону утверждение очевидно. [math]\Rightarrow[/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]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]\triangleleft[/math]