[math]1 \mid\mid \sum w_i U_i[/math]
| Задача: |
| Есть один станок и [math]n[/math] работ. Для каждой работы заданы время выполнения [math] p_i,[/math] дедлайн [math]d_i[/math] и стоимость выполнения этой работы [math]w_i \geqslant 0[/math].
Необходимо минимизировать [math]\sum w_i U_i[/math]. |
Наивное решение
В общем случае, когда времена выполнения работ [math]p_i[/math] могут быть сколь угодно большими или, например, дробными, данная задача может быть решена с помощью перебора.
Будем перебирать все перестановки чисел от [math]1[/math] до [math]n[/math], обозначающих номера заданий. При получении очередной перестановки просто будем пытаться выполнять задания в указанном порядке. Если значение [math]\sum w_i U_i[/math], полученное при данном расположении заданий, лучше, чем предыдущие результаты, то обновляем ответ.
Данное решение будет работать за [math]O(n \cdot n!)[/math].
Перебор с битовыми масками
Далее широко будет использоваться следующий факт:
| Лемма: |
Пусть все работы отсортированы в порядке неубывания дедлайнов [math]d_i[/math].
Тогда существует оптимальное расписание вида [math]i_1, i_2, \ldots, i_s, i_{s+1}, \ldots, i_n [/math], такое, что [math]i_1 \lt i_2 \lt \ldots \lt i_s [/math] — номера работ, которые успеют выполниться вовремя, а [math]i_{s+1}, \ldots, i_n [/math] — номера просроченных работ. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Пусть у нас есть некоторое оптимальное раписание [math]S[/math]. Получим необходимое нам расписание путем переставления некоторых работ.
- Если работа с номером [math] i[/math] выполнится в [math]S[/math] с опозданием, то переставим эту работу в конец. При этом, так как работа просрочна в оптимальном расписании [math]S[/math], при такой перестановке не произойдет увеличения целевой функции.
- Если работы с номерами [math]i[/math] и [math]j[/math] в расписании [math]S[/math] выполняются вовремя, но при этом [math]d_i \lt d_j [/math], и [math]j[/math] стоит в [math]S[/math] раньше [math]i[/math], то переставим работу с номером [math]j[/math] так, чтобы она выполнялась после работы [math]i[/math]. Таким образом, каждая из работ, находившихся в [math]S[/math] между [math]j[/math] и [math]i[/math], включая [math]i[/math], будет выполняться в новом расписании на [math]p_j[/math] единиц времени раньше. Эта перестановка не повлияет на оптимальнось расписания:
- Ни одна из работ, котарая успевала выполниться в расписании [math]S[/math], не попадет в список просроченных работ при переставлении её на более раннее время.
- Число работ, не успевающих выполниться вовремя, не может уменьшится, иначе бы возникло противоречие с исходным выбором [math]S[/math], как оптимального решения.
- Поскольку [math]d_i \lt d_j [/math] и работа [math]i[/math] будет заканчиваться на [math]p_j[/math] единиц времени раньше, то стоящая сразу после нее работа [math]j[/math] тоже будет успевать выполниться.
|
| [math]\triangleleft[/math] |
Наше решение будет построено на переборе всех битовых масок. При построении решения мы будем опираться на доказанную лемму.
Если бит, соответствующий заданию с номером [math]i[/math] равен [math]1[/math], то это задание должно быть записано в список заданий, которые, возможно, успеют выполниться.
Далее мы сортируем задания из этого списка по времени неубывания дедлайнов, а те задания, что не попали в этот список, должны быть отправлены в конец расписания в любом порядке.
Далее проверяем полученное возможное расписание на корректность, и, в случае успеха, обновляем ответ.
Перебор всех масок может быть произведен за [math]O(2 ^ n)[/math], и [math]O(n)[/math] на пересчет ответа. Таким образом, это решение будет работать за [math]O(n \cdot 2^n)[/math].
Псевдополиномиальное решение
В ситуации, когда времена выполнения работ [math]p_i[/math] целочисленные, а значение [math] \sum\limits_{i=1}^n p_i [/math] не очень большое, то для решения данной задачи можно применить динамическое программирование.
Идея алгоритма
Обозначим [math]T = \sum\limits_{i=1}^n p_i[/math].
Для всех [math]t = 0, 1, \ldots, T [/math] и [math]j = 1, \ldots, n[/math] будем рассчитывать [math]F_j(t)[/math] — значение целевой функции [math]\sum w_i U_i[/math], при условии, что были рассмотрены первые [math]j[/math] работ и общее время выполнения тех из них, что будут закончены вовремя, не превышает времени [math]t[/math].
- Если [math]0 \leqslant t \leqslant d_j [/math] и работа [math]j[/math] успевает выполниться вовремя в расписании, соответствующем [math]F_j(t)[/math], то [math]F_j(t) = F_{j- 1}(t - p_j)[/math], иначе [math]F_j(t) = F_{j- 1}(t) + w_i[/math].
- Если [math]t \gt d_j[/math], то [math]F_j(t) = F_{j}(d_j)[/math], поскольку все работы с номерами [math]j = 1, \ldots, j[/math], законченные позже, чем [math] d_j \geqslant \ldots \geqslant d_1 [/math], будут выполнены с опозданием.
Отсюда, получим соотношение:
[math]
F_j(t) =
\left \{\begin{array}{ll} \min(F_{j-1}(t-p_j), F_{j-1}(t) + w_j), & 0 \leqslant t \leqslant d_j \\
F_j(d_j), & d_j \lt t \lt T
\end{array} \right.
[/math]
В качестве начальных условий следует взять [math]F_j(t) = \infty [/math] при [math]t \lt 0, j = 0,\ldots, n [/math] и [math]F_0(t) = 0 [/math] при [math]t \geqslant 0 [/math].
Ответом на задачу будет [math]F_n(d_n)[/math].
Псевдокод
Приведенный ниже алгоритм вычисляет [math]F_j(t)[/math] для [math]j = 0,\ldots, n [/math] и [math]t = 0,\ldots, d_j [/math].
- За [math]p_{max}[/math] обозначим самое большое из времен выполнения заданий.
- Считаем, что [math]T = \sum\limits_{i=1}^n p_i[/math].
- Значения [math] F_j(t)[/math] будем хранить в массиве [math]F[j][t][/math].
сортируем работы по неубыванию времен дедлайнов [math]d_i[/math]
for [math]t = -p_{max}[/math] to [math]-1[/math]
for [math]j = 0[/math] to [math]n[/math]
[math]F[j][t] = \infty[/math]
for [math]t = 0[/math] to [math]T[/math]
[math]F[0][t] = 0[/math]
for [math]j = 1[/math] to [math]n[/math]
for [math]t = 0[/math] to [math]d_j[/math]
if [math] F[j-1][t] + w_j \lt F[j-1][t-p_j] [/math]
[math] F[j][t] = F[j-1][t] + w_j [/math]
else
[math] F[j][t] = F[j-1][t-p_j] [/math]
for [math]t = d_j + 1[/math] to [math]T[/math]
[math] F[j][t] = F[j][d_j] [/math]
Для того, чтобы найти само расписание, по доказанной выше лемме, нам достаточно найти множество работ, которые будут выполнены с опозданием. Это может быть сделано следующим способом:
[math]t = d_n[/math]
[math]L = \varnothing[/math]
for [math]j = n[/math] downto [math]1[/math]
[math]t = \min(t, d_j)[/math]
if [math] F[j][t] = F[j-1][t] + w_j [/math]
[math] L = L \cup \{j\} [/math] </tex>
else
[math] t = t - p_j [/math]
Время работы
Время работы приведенного выше алгоритма — [math]O\Big(n \sum\limits_{i=1}^n p_i\Big)[/math].
См. также
Источники информации
- P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 26 - 28
