1632
правки
Изменения
1p1sumu
,rollbackEdits.php mass rollback
<tex dpi = "200" >1 \mid p_i=1\mid \sum U_i</tex>
{{Шаблон:Задача
|definition =
==Алгоритм==
Во избежание лишнего копирования массивов, мы можем делать проход по массиву блоков (bucket'ов) и для каждого блока проходить по спискам работ внутри него. Начальное значение <tex> time = 0</tex>. После рассмотрения очередной работы мы будем добавлять ее в расписание и увеличивать <tex> time</tex> на <tex>1</tex>. Тогда, если значение <tex> time</tex> становится равным номеру блока, то мы переходим к следующему блоку, а нерассмотренные задачи помечаем как просроченные и выполняем в конце. Работы с <tex>d_i = 0</tex> заранее отметим как просроченные. ===Время работы===Cортировку работ по неубыванию дедлайнов осуществляем с помощью карманной сортировки за <tex>O(n)</tex>, а значит и весь алгоритм будет работать за <tex>O(n)</tex>. ===Корректность и оптимальность=Источники информации==* Peter BruckerВ результате выполнения данного алгоритма будет получено корректное расписание, в котором каждая работа встречается не более одного раза. «Scheduling Algorithms» {{---}} «Springer»Вначале расписания будут стоять все работы, 2006 гкоторые мы успеваем выполнить до дедлайна. Остальные работы дописываются в конец в произвольном порядке. Оптимальность полученного расписания доказывается аналогично [[1sumwu|<tex>1 \mid \mid \sum w_{i}U_{---}i} 86 стр</tex>]]. {{---}} ISBN 978-3-540-69515-8
== См. также ==
* [[1sumwu|<tex>1 \mid \mid \sum w_{i}U_{i}</tex>]]
==Источники информации==* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 86 стр. {{---}} ISBN 978-3-540-69515-8 [[Категория: Дискретная математика Алгоритмы и алгоритмыструктуры данных]]
[[Категория: Теория расписаний]]