Изменения

<tex dpi=200>1 \mid prec; r_i; p_i = 1 \mid L_{max}</tex> {{Задача|definition = Дано <tex>n</tex> работ и один станок. Для каждой работы известно её время появления <tex>r_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>. Работа может начаться только после выполнения некоторых других работ, эта зависимость дана в виде ациклического графа. Необходимо составить такое расписание, чтобы значение <tex>L_{max} = \max\limits_{i=1..n} (C_i - d_i)</tex> было минимальным.}} =Постановка задачи=Описание алгоритма==Пусть <tex>time</tex> {{---}} текущий момент времени.<br/>Рассмотрим задачуДля каждого очередного значения <tex>time</tex>, которое изменяется от <tex>0</tex> до времени окончания последней работы, будем:

<li>Дано Выполнять работу <tex>nk</tex> из множества невыполненных работ и один станок.</li><li>Для каждой работы известно её время появления , у которой <tex>r_d_{ik}</tex>минимально. Время выполнения всех работ <tex/li>p_i</texli> равно Увеличивать <tex>1time</tex>. Работу можно прерывать в процессе выполнения, а потом снова возобновлятьна один.</li>

==Доказательство==Пусть существует оптимальное расписание <tex> S^* </tex>. В этом расписании работа выполняется тогда, когда она появилась, либо когда закончилась другая работа.Рассмотрим такое расписание <tex>S^*</tex>, которое как можно дольше совпадает с расписанием S, построенным алгоритмом. Пусть <tex> t~-</tex> первый момент времени, когда в расписании <tex>S</tex> начинает выполняться работа <tex>i</tex>, а в расписании <tex>S^*</tex> работа <tex>j</tex> (причем <tex> i \ne j </tex>). Мы знаем, что <tex> r_i, r_j \leqslant t </tex>, а значит <tex> d_i \leqslant d_j </tex> (поскольку при построении мы выбираем минимальное доступное <tex> d_k </tex>). Пусть <tex> i_1, i_2, \ldots, i_l~-</tex> все работы, которые находятся в расписании <tex>S^*</tex> между работами <tex>j</tex> и <tex>i</tex> и являются наследниками работы <tex>j</tex>. Кроме того, предположим, что эти работы упорядочены по времени начала выполнения. Теперь, если мы поставим работу <tex>i_l</tex> вместо <tex>i, i_{l-1}</tex> вместо <tex>i_{l}, \ldots, j</tex> вместо <tex>i_1, i</tex> вместо <tex>j</tex>, то мы снова получим возможное оптимальное расписание <tex> S' </tex>. так как <tex> d_i \leqslant d_j \leqslant d_v </tex>, где <tex> v \in {i_1, i_2, \ldots, i_l} </tex>. Последнее неравенство имеет место быть, поскольку все работы <tex>i_v</tex> являются наследниками работы <tex>j</tex>. [[Файл:1precripi1Lmax.png|400px|thumb|center|Составление оптимального расписания <tex> S^* </tex>]]  ==Источники информации==* [http://math.mit.edu/~goemans/18438/lec13.pdf Minmax criteria. A polynomial-time algorithm for jobs of equal length. 13 стр.]* [http://community.stern.nyu.edu/om/faculty/pinedo/scheduling/shakhlevich/handout04.pdf Basic Scheduling Algorithms for Single Machine Problems: Due-Date Scheduling] [[Категория: Дискретная математика Алгоритмы и алгоритмыструктуры данных]]