[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]l[/math] и [math]k[/math] следующим образом:
- [math]l[/math] — первая работа в [math]S[/math]: [math]l \notin S^*[/math]
- [math]k[/math] — первая работа в [math]S^*[/math]: [math]k \notin S[/math]
Покажем, что в [math]S^*[/math] работа [math]k[/math] может быть заменена работой [math]l[/math] без увеличения значения целевой функции. Рассмотрим два случая:
1. Пусть [math]l \lt k[/math].
То, что [math]k[/math] не принадлежит множеству [math]S[/math], значит, что либо на некотором шаге появилась опаздывающая работа [math]j[/math], которая заменила [math]k[/math], либо работа [math]k[/math] опаздывала и [math]w_k[/math] было меньше [math]\min\limits_{i \in S}w_i[/math], и поэтому она не была добавлена. В любом случае в это время работа [math]l[/math] уже принадлежала [math]S[/math]. Из этого следует, что [math]w_k \leq w_l[/math], во втором случае очевидно, почему, а в первом — потому что на этапе замены мы выбрали [math]k[/math], а не [math]l[/math]. Следовательно, мы не ухудшим целевую функцию заменой [math]k[/math] на [math]l[/math].
2. Пусть [math]l \gt k[/math].
Замена работы [math]k[/math] в [math]S^*[/math] на работу [math]l[/math] не противоречит условию, что за все работы в этом множестве штраф налагаться не будет, так как [math]k[/math] выполнялась в срок, а [math]d_k \leq d_l[/math] и все работы выполняются одинаковое количество времени. Следовательно, [math]l[/math] так же будет выполнена в срок. Осталось доказать, что [math]w_k \leq w_l[/math].
Пусть работа [math]k_{i_0} = k[/math] была заменена работой [math]i_0[/math], а так же [math]k_{i_1} \cdots k_{i_r}[/math] — последовательность работ из [math]S[/math], каждая из которых была на некотором шаге заменена работой [math]i_1 \cdots i_r[/math] соответственно. Тогда [math]i_0 \lt i_1 \lt \cdots \lt i_r[/math].
 Рис. 1. [math]i_v[/math] превосходит [math]i_u[/math]. Будем говорить [math]i_v[/math] превосходит [math]i_u[/math], где [math]u \lt v[/math], если [math]k_{i_v} \leq i_u[/math]. Тогда [math]w_{k_{i_v}} \geq w_{k_{i_u}}[/math], так как когда мы вставляли работу [math]i_u[/math] мы выбрали для замены [math]k_{i_u}[/math], то есть ее вес был минимальным среди всех работ, находившихся на тот момент в [math]S[/math], включая [math]k_{i_v}[/math]. Для большей ясности на рисунке 1 показано, в каком порядке располагаются эти работы относительно друг друга согласно их номерам.
Если из последовательности [math]i_0 \lt i_1 \lt \cdots \lt i_r[/math] можно выделить подпоследовательность [math]j_0 = i_0 \lt j_1 \lt \cdots \lt j_s[/math] со свойствами:
- [math]j_{v + 1}[/math] превосходит [math]j_v[/math], где [math]v \in [0 \cdots s - 1][/math]
- [math]j_{s - 1} \lt l \leq j_s[/math] ,
то [math]w_l \geq w_{k_{j_s}} \geq \cdots \geq w_{k_{j_0}} = w_k[/math], что доказывает терему.
|
| [math]\triangleleft[/math] |
