37
правок
Изменения
Нет описания правки
Таким образом, мы получили корректное расписание без прерываний, не изменив при этом значение <tex>C_{max}</tex>, что и требовалось доказать.
== Пример: задача <tex>F \mid p_{ij} = 1 \mid \sum w_iu_i</tex> ==
{{Задача
|definition=
Дано <tex>m</tex> станков, на которых нужно обработать <tex>n</tex> деталей. Каждую деталь нужно обработать по очереди на всех станках. Любая работа на любом станке выполняется единицу времени. Для каждой работы есть дедлайн <tex>d_i</tex> {{---}} время, до которого она должна быть закончена, и штраф <tex>w_i</tex>, который нужно будет выплатить в случае, если работа была закончена после <tex>d_i</tex>. Необходимо минимизировать суммарный штраф, который придется выплатить.
}}
Задача <tex>F \mid p_{ij} = 1 \mid \sum w_iu_i</tex> за <tex>O(n)</tex> сводится к задаче <tex>1 \mid p_i = 1 \mid \sum w_iu_i</tex>. Задача <tex>1 \mid p_i = 1 \mid \sum u_iw_i</tex> решается за <tex>O(n \log n)</tex>. После решения этой задачи, нужно вывести ответ, имеющий размер <tex>O(nm)</tex>. Итоговая сложность алгоритма {{---}} <tex>O(n \log n + nm)</tex>
== См. также ==
