577
правок
Изменения
Нет описания правки
Оптимальное расписание для этой задачи будем задавать множеством работ <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>. S = <tex>\varnothing</tex> '''for''' j = 1 '''to''' n: '''if''' j опаздывает, и все более ранние простои заполнены: найти i: w[i] = <tex>\min\limits_{k \in S}</tex>(w[k]) '''if''' w[i] < w[j]: заменить i на j в S '''else''': добавить i в S и поставить i на место самого раннего простояТаким образом, работы, не попавшие в <tex>S</tex>, будут иметь минимальное значение <tex>w_i</tex>.== Доказательство корректности ==
