1precripi1Lmax

Постановка задачи

Рассмотрим задачу:

1. Дано [math]n[/math] работ и один станок.
2. Для каждой работы известно её время появления [math]r_{i}[/math]. Время выполнения всех работ [math]p_i[/math] равно [math]1[/math]. Работа может начаться только после выполнения некоторых других работ, эта зависимость дана в виде ациклического графа.

Необходимо составить такое расписание, чтобы значение [math]L_{max} = max_{i=1}^n (C_i - d_i)[/math] было минимальным.

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

Пусть [math]time[/math] — текущий момент времени.
Для каждого очередного значения [math]time[/math], которое изменяется от [math]0[/math] до времени окончания последней работы, будем:

1. Выполнять работу [math]k[/math] из множества невыполненных работ, у которой [math]d_{k}[/math] минимально.
2. Увеличиваем [math]time[/math] на один.

Доказательство

Пусть существует оптимальное расписание [math] S^* [/math]. В этом расписании работа выполняется тогда, когда она появилась, либо когда закончилась другая работа. Рассмотрим такое расписание [math]S^*[/math], которое как можно дольше совпадает с расписанием S, построенным алгоритмом. Пусть [math] t~-[/math] первый момент времени, когда в расписании [math]S[/math] начинает выполняться работа [math]i[/math], а в расписании [math]S^*[/math] работа [math]j[/math] (причем [math] i \ne j [/math]). Мы знаем, что [math] r_i, r_j \le t [/math], а значит [math] d_i \le d_j [/math] (поскольку при построении мы выбираем минимальное доступное [math] d_k [/math]). Пусть [math] i_1, i_2, ..., i_l~-[/math] все работы, которые находятся в расписании [math]S^*[/math] между работами [math]j[/math] и [math]i[/math] и являются наследниками работы [math]j[/math]. Кроме того, предположим, что эти работы упорядочены по времени начала выполнения. Теперь, если мы поставим работу [math]i_l[/math] вместо [math]i, i_{l-1}[/math] вместо [math]i_{l}, ..., j[/math] вместо [math]i_1, i[/math] вместо [math]j[/math], то мы снова получим возможное оптимальное расписание [math] S' [/math]. так как [math] d_i \le d_j \le d_v [/math], где [math] v \in {i_1, i_2, ... i_l} [/math]. Последнее неравенство имеет место быть, поскольку все работы [math]i_v[/math] являются наследниками работы [math]j[/math].