Возьмем оптимальное расписание для соответствующей задачи с одним станком, выполним работы в этом порядке на первой машине, затем на второй машине, начиная с момента времени <tex> 1 </tex>, и так далее, до выполнения на последней машине, начиная с <tex> m - 1 </tex>. Это расписание корректно и соблюдает все дедлайны. Поскольку целевая функция совпадает с соответствующей функцией для задачи на одном станке, оно оптимально и для данной задачи.
}}
Примером применения этого утверждения может служить задача [http://neerc.ifmo.ru/wiki/index.php?title=Fpij1sumwu]
Задачи с произвольными временами выполнения работ почти все являются NP-трудными.
Таким образом, мы получили корректное расписание без прерываний, не изменив при этом значение <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>
== См. также ==
