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

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

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

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

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

Теорема:

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

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

[math]\triangleright[/math]

Пусть [math]S[/math] — множество работ, вычисленное с помощью алгоритма. Тогда все работы, находящиеся в этом множестве, будут выполнены в срок

[math]\triangleleft[/math]