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

[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], за которые штраф начислен не будет. Работы, которые завершатся с опозданием, могут быть выполнены в конце в любом порядке.