577
правок
Изменения
Нет описания правки
== Описание алгоритма ==
=== Идея ===
Будем полагать, что работы заданы в порядке неубывания их дедлайнов, то есть <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>. {{Лемма|statement=Пусть есть работы <tex>1 \ldots n</tex> с дедлайнами <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>. Тогда существует оптимальное расписание, в котором времена завершения работ идут в том же порядке, то есть <tex>C_1 \leqslant C_2 \leqslant \ldots \leqslant C_n</tex>.|proof=.}}
=== Псевдокод ===
== Доказательство корректности ==
== См. также ==
* [[O2Cmax|<tex>O2 \mid \mid C_{max}</tex>]]
* [[Opi1sumu|<tex>O \mid p_{ij} = 1 \mid \sum U_i</tex>]]
* [[Opij1di|<tex> O \mid p_{i, j} = 1, d_i \mid - </tex>]]
* [[Opij1sumwu|<tex> O \mid p_{i, j} = 1 \mid - \sum w_{i} U_{i}</tex>]]
== Источники информации ==
* Peter Brucker «Scheduling Algorithms», fifth edition, Springer {{---}} с. 171-174 ISBN 978-3-540-69515-8
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Теория расписаний]]
