577
правок
Изменения
→P \mid p_i=1 \mid \sum w_i U_i
Дано <tex>m</tex> одинаковых станков, на которых нужно выполнить <tex>n</tex> работ. Любая работа на любом станке выполняется единицу времени. Для каждой работы есть время окончания <tex>d_i</tex> {{---}} ожидается, что до этого времени она будет закончена, и штраф <tex>w_i</tex>, который нужно будет выплатить в случае, если работа была закончена после <tex>d_i</tex>. Необходимо минимизировать суммарный штраф, который придется выплатить.
}}
== Описание алгоритма ==Оптимальное расписание для этой задачи будем задавать множеством работ <tex>S</tex>, за которые штраф начислен не будет. Работы, которые завершатся с опозданием, могут быть выполнены в конце в любом порядке.<br>Чтобы построить множество <tex>S</tex>, будем добавлять работы в порядке неуменьшения их времен окончания, и как только некоторая работа <tex>j</tex> опаздывает, удалим из <tex>S</tex> работу с минимальным значением <tex>w_i</tex> и поставим <tex>j</tex> на ее место.<br>Пусть есть работы <tex>1 \cdots n</tex> с временами окончания <tex>d_1 \leq d_2 \leq \cdots \leq d_n</tex>. Тогда следующий алгоритм вычислит оптимальное множество <tex>S</tex>.
