Изменения
корректность
'''heap''' M <font color=green>// куча, в которой будем хранить доступные на данный момент работы в порядке неубывания дедлайнов</font>
'''while''' j <= n
'''int''' time = jobs[j].first<font color=green>// время начала выполнения текущего блока работ</font>
'''while''' jobs[j].first <= time <font color=green>// добавляем в кучу все невыполненные работы, доступные на данный момент</font>
M.push(j)
M.push(j)
j++
Внутренний цикл '''while''' распределяет работы блоками, в которых они выполняются без простоя станков. После окончания такого блока, время начала выполнения следующего будет равно текущему значению <tex>r_j</tex>.
=== Асимптотика ===
Сначала мы сортируем работы, что занимает <tex> \mathcal{O}(n\log{n})</tex>. Далее идёт цикл, в котором мы <tex>n</tex> раз кладём элемент в кучу и <tex>n</tex> раз извлекаем, что также занимает <tex> \mathcal{O}(n\log{n})</tex> времени. В итоге всё вместе составляет асимптотику алгоритма <tex> \mathcal{O}(n\log{n})</tex>.
== Доказательство корректности алгоритма ==
{{Теорема
|statement=
Приведенный алгоритм строит оптимальное расписание для задачи <tex> P \mid p_i=1; r_i - integer \mid L_{max} </tex>.
|proof=
Пусть <tex>S</tex> {{---}} расписание построенное предложенным алгоритмом, а <tex>S^*</tex> оптимальное расписание со следующими свойствами:
* первые <tex>r-1</tex> работ из <tex>S</tex> в обоих расписаниях назначены на одно и тоже время и
* значение <tex>r-1</tex> {{---}} наибольшее.
Таким образом работа <tex>J_r</tex> в расписании <tex>S</tex> назначена на время <tex>t</tex>, а в расписании <tex>S^*</tex> на другой более поздний момент времени. Если в момент времени <tex>t</tex> в расписании <tex>S^*</tex> есть свободный станок, то работа <tex>J_r</tex> может быть назначена на этот станок и выполнена в момент <tex>t</tex>. Иначе существует работа <tex>J_k</tex> такая, что <tex>d_r \leqslant d_k</tex>, которая выполнится в расписании <tex>S^*</tex> в момент <tex>t</tex>, а в <tex>S</tex> в другое время. Тогда мы меняем местами работы <tex>J_k</tex> и <tex>J_r</tex> в расписании <tex>S^*</tex>, что не нарушает оптимальность <tex>S^*</tex>, но является противоречием максимальности значения <tex>r-1</tex>.
}}
== См. также ==
* [[Pintreepi1Lmax|<tex>P \mid intree, p_{i} = 1 \mid L_{max}</tex>]]
* [[PpmtnriLmax|<tex>P \mid pmtn, r_i \mid L_{max}</tex>]]
== Источники информации ==
* Peter Brucker «Scheduling Algorithms», fifth edition, Springer {{---}} с. 111-112 ISBN 978-3-540-69515-8
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Теория расписаний]]
