Обсуждение участницы:Анна

[math] P \mid p_i=1 \mid \sum w_i U_i[/math]

Задача:

Дано [math]m[/math] одинаковых станков, на которых нужно выполнить [math]n[/math] работ. Любая работа на любом станке выполняется единицу времени. Для каждой работы есть время окончания [math]d_i[/math] — ожидается, что до этого времени она будет закончена, и штраф [math]w_i[/math], который нужно будет выплатить в случае, если работа была закончена после [math]d_i[/math]. Необходимо минимизировать суммарный штраф, который придется выплатить.

Описание алгоритма

Оптимальное расписание для этой задачи будем задавать множеством работ [math]S[/math], за которые штраф начислен не будет. Работы, которые завершатся с опозданием, могут быть выполнены в конце в любом порядке.
Чтобы построить множество [math]S[/math], будем добавлять работы в порядке неуменьшения их времен окончания, и как только некоторая работа [math]j[/math] опаздывает, удалим из [math]S[/math] работу с минимальным значением [math]w_i[/math] и поставим [math]j[/math] на ее место.
Пусть есть работы [math]1 \cdots n[/math] с временами окончания [math]d_1 \leq d_2 \leq \cdots \leq d_n[/math]. Тогда следующий алгоритм вычислит оптимальное множество [math]S[/math].