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

[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]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].

  [math]S \leftarrow  \varnothing[/math]
  for [math]j = 1[/math] to [math]n[/math]:
     if [math]j[/math] опаздывает, и все более ранние простои заполнены:
        найти [math]i: w[i] = \min\limits_{k \in S}(w[k])[/math]
        if [math]w[i] \lt  w[j][/math]:
           заменить [math]i[/math] на [math]j[/math] в [math]S[/math]
     else:
        добавить [math]i[/math] в [math]S[/math] и поставить [math]i[/math] на место самого раннего простоя

Таким образом, работы, не попавшие в [math]S[/math], будут иметь минимальное значение [math]w_i[/math].

Доказательство корректности

Теорема:

Вышеописанный алгоритм корректен и строит оптимальное множество работ [math]S[/math].

Доказательство:

[math]\triangleright[/math]

Пусть [math]S[/math] — множество работ, вычисленное с помощью алгоритма. Тогда все работы, находящиеся в этом множестве, будут выполнены в срок, то есть штраф за них налагаться не будет, так как если работа [math]j[/math] заменила работу [math]i[/math], которая успевала выполниться до истечения [math]d_i[/math], то [math]j[/math] так же успеет выполниться в срок, потому что [math]d_i \leq d_j[/math]. Пусть [math]S^*[/math] — множество работ без штрафов в оптимальном расписании.

[math]\triangleleft[/math]