[math] O \mid p_{i, j} = 1 \mid \sum w_{i} U_{i} [/math]
| Задача: |
| Дано [math]m[/math] одинаковых станков, которые работают параллельно, и [math]n[/math] работ, которые необходимо выполнить в произвольном порядке на всех станках. Любая работа на любом станке выполняется за единицу времени. Для каждой работы есть время окончания [math]d_{i}[/math] — время, до которого она должна быть выполнена. Требуется минимизировать [math]\sum w_{i} U_{i}[/math], то есть суммарный вес всех просроченных работ. |
Описание алгоритма
Для решения этой задачи, мы должны найти множество [math]S[/math] работ, которые успеваем выполнить до дедлайна. Значит нам надо минимизировать: [math]\sum\limits_{ i \notin S } {w_{i}}[/math]. Будем решать эту задачу с помощью динамического программирования с использованием утверждений из решения задачи [math] O \mid p_{i, j} = 1, d_{i} \mid - [/math].
Рассмотрим работы в порядке неубывания дедлайнов: [math]d_{1} \leqslant d_{2} \leqslant \ldots \leqslant d_{n}[/math]. Пусть мы нашли решение для работ [math]1, 2, \ldots, i - 1[/math]. Очевидно, что [math]S \subseteq \{1, \ldots , i - 1\}[/math].
Пусть [math]h^S[/math] — вектор соответствующий множеству [math]S[/math] из задачи [math] O \mid p_{i, j} = 1, d_i \mid - [/math]. Тогда, для добавления работы [math]i[/math] в множество [math]S[/math] должно выполняться неравенство: [math]m \cdot (d_{i} - m) - ( k m - \sum \limits_{j = 1}^m {h^S(d_{i} - m + j)})+x(d_{i}) \geqslant m[/math], где [math]k = |S|[/math] и [math]x(d_{i})[/math] — количество периодов времени [math]t[/math] со свойствами: [math]d_{i} - m + 1 \leqslant t \leqslant d_{i}[/math] и [math]h^S(t) \lt m[/math]. Чтобы проверить это неравенство, нам нужно посчитать [math]m[/math] чисел [math]h^S(t)[/math], [math]t=d_{i} - m + 1, \ldots, d_{i}[/math]. Для этого определим переменные:
[math]k_{j} = \begin{cases}
h^S(d_{i} - m + j) & j \in \{1 , \ldots , m\} \\
0 & j \notin \{1 , \ldots , m\} \\
\end{cases}[/math],
[math]l_j = \begin{cases}
1 & j \in \{1 , \ldots , m\}\text{; } k_{j} \lt m \\
0 & \text{otherwise} \\
\end{cases} .[/math]
Тогда можно заметить, что [math]x(d_{i}) = \sum\limits_{j = 1}^m {l_{j}}[/math], так как [math]l_{j} = 1[/math] если [math]1 \leqslant j \leqslant m[/math] и [math]h^S(d_{i} - m + j) \lt m[/math] или [math]d_{i} - m + 1 \leqslant d_{i} - m + j \leqslant d_{i}[/math] и [math]h^S(d_{i} - m + j) \lt m[/math]. Следовательно можно упростить исходное неравенство: [math]m \cdot (d_{i} - m) - (k m - \sum \limits_{j = 1}^m {k_{j}}) + \sum \limits_{j = 1}^m {l_{j}} \geqslant m[/math] или [math]m \cdot (d_{i} - m - k)+ \sum\limits_{j = 1}^m {(k_{j} + l_{j})} \geqslant m[/math].
Для динамического программирования определим [math]f_{i} (k , k_{1} , \ldots , k_{m})[/math] — минимальное значение целевой функции для расписания работ [math]i , i + 1 , \ldots , n[/math], позволяющее выполнить работы из множества [math]S[/math] без опоздания, где [math]k = |S|, S \subseteq \{1, \ldots , i - 1\}[/math] и [math]k_{j}=h^S(d_{i} - m + j)[/math], где [math]j = 1, \ldots , m[/math], то есть [math]f_{i} (k, k_{1}, \ldots , k_{m}) = \min \limits_{S: |S| = k, S \subseteq \{1, \ldots , i - 1 \}} (\sum \limits_{j = i}^n {w_{j} U_{j}})[/math].
Пусть [math]p = d_{i + 1} - d_{i}[/math], тогда определим рекуррентное выражение для [math]f_{i} (k, k_{1}, \ldots , k_m)[/math]:
[math]f_{i} (k, k_{1}, \ldots , k_{m}) = \begin{cases}
f_{i + 1} (k, k_{1 + p},k_{2 + p}, \ldots, k_{m + p}) + w_{i}, & m \cdot (d_{i} - m - k)+ \sum \limits_{j = 1}^m {(k_{j} + l_{j})} \lt m \text{ } (1)\\
\min(f_{i + 1} (k, k_{1 + p}, k_{2 + p}, \ldots , k_{m + p}) + w_{i} ; f_{i + 1} (k + 1, k_{1 + p} + l_{1 + p}, k_{2 + p} + l_{2 + p}, \ldots , k_{m + p} + l_{m + p})), & m \cdot (d_i - m - k) + \sum \limits_{j = 1}^m {(k_{j} + l_{j})} \geqslant m \text{ }(2)\\
\end{cases}[/math]
c начальным условием: [math]f_{n + 1} (k, k_{1}, \ldots , k_{m}) = 0 [/math] для [math]k, k_{1}, \ldots , k_{m} = 0, 1, \ldots , m[/math].
Если выполняется неравенство [math](1)[/math], то мы не можем добавить работу [math]i[/math] в множество [math]S[/math] и поэтому [math]f_{i} (k, k_{1} \ldots , k_{m}) = f_{i + 1} (k, k_{1 + p}, k_{2 + p}, \ldots, k_{m + p}) + w_{i}[/math].
Если выполняется неравенство [math](2)[/math], тогда мы может добавить работу [math]i[/math] в множество [math]S[/math] или не добавлять. Если мы добавим работу [math]i[/math], то [math]f_{i} (k, k_{1}, \ldots , k_{m}) = f_{i + 1}(k + 1, k_{1 + p} + l_{1 + p}, k_{2 + p}+l_{2 + p}, \ldots , k_{m + p}+l_{m + p}) \text{ } (3)[/math]. Если мы не добавим работу [math]i[/math], то по аналогии с первым случаем [math]f_{i} (k, k_{1}, \ldots , k_{m}) = f_{i + 1} (k, k_{1 + p},k_{2 + p}, \ldots, k_{m + p}) +w_{i} \text{ } (4)[/math]. Так как [math]f_{i} (k, k_{1}, \ldots , k_{m}) = \min(\sum \limits_{j = i}^n {w_{j} U_{j}})[/math], то нам надо взять минимум из значений [math](3)[/math] и [math](4)[/math].
Ответ на задачу будет находиться в [math]f_{1} (0, 0, \ldots , 0)[/math].
Пример работы
Пусть [math]m = 2[/math] и [math]n = 3[/math].
| номер работы |
дедлайн |
вес
|
| 1 |
2 |
7
|
| 2 |
2 |
6
|
| 3 |
2 |
5
|
Для такой задачи получится таблица для функции [math]f[/math]:
| [math]k[/math] |
[math]k_1[/math] |
[math]k_2[/math] |
[math]f_{4} (k, k_1, k_2)[/math] |
[math]f_{3} (k, k_1, k_2)[/math] |
[math]f_{2} (k, k_1, k_2)[/math] |
[math]f_{1} (k, k_1, k_2)[/math]
|
| 0 |
0 |
0 |
0
|
| 0 |
0 |
1 |
0
|
| 0 |
0 |
2 |
0
|
| 0 |
1 |
0 |
0
|
| 0 |
1 |
1 |
0
|
| 0 |
1 |
2 |
0
|
| 0 |
2 |
0 |
0
|
| 0 |
2 |
1 |
0
|
| 0 |
2 |
2 |
0
|
| 1 |
0 |
0 |
0
|
| 1 |
0 |
1 |
0
|
| 1 |
0 |
2 |
0
|
| 1 |
1 |
0 |
0
|
| 1 |
1 |
1 |
0
|
| 1 |
1 |
2 |
0
|
| 1 |
2 |
0 |
0
|
| 1 |
2 |
1 |
0
|
| 1 |
2 |
2 |
0
|
| 2 |
0 |
0 |
0
|
| 2 |
0 |
1 |
0
|
| 2 |
0 |
2 |
0
|
| 2 |
1 |
0 |
0
|
| 2 |
1 |
1 |
0
|
| 2 |
1 |
2 |
0
|
| 2 |
2 |
0 |
0
|
| 2 |
2 |
1 |
0
|
| 2 |
2 |
2 |
0
|
Время работы
Для определения времени работы алгоритма надо заметить, что [math]i = 0, \ldots , n[/math], [math] k = 0, \ldots , n[/math] и [math]k_j = 0, \ldots m[/math] где [math]j = 1, \ldots , m[/math]. Из рекуррентной формулы очевидно, что для подсчета одного значения [math]f_{i} (k, k_{1}, \ldots , k_{m})[/math] нужно [math]O(m)[/math] времени. Значит алгоритм работает за [math]O(n^2 m^{m + 1})[/math].
См. также
Источники информации
- Peter Brucker. «Scheduling Algorithms» — «Springer», 2006 г. — c. 168 - 170. ISBN 978-3-540-69515-8
