Opij1sumwu

$O \mid p_{i,j} = 1 \mid \sum w_{i} U_{i}$

Задача:

Дано $m$ одинаковых станков, которые работают параллельно, и $n$ работ, которые необходимо выполнить в произвольном порядке на всех станках. Любая работа на любом станке выполняется за единицу времени. Для каждой работы есть время окончания $d_i$ — время, до которого она должна быть выполнена. Требуется минимизировать $\sum w_{i} U_{i}$, то есть суммарный вес всех просроченных работ.

Описание алгоритма

Для решения этой задачи, мы должны найти множество $S$, что $\sum\limits_{i \notin S} {w_{i} U_{i}}$ минимальна. Будем решать эту задачу с помощью динамического программирования с использованием утверждений из решении задачи $O \mid p_{i,j} = 1, d_i \mid -$.

Рассмотрим работы в порядке не убывания дедлайнов: $d_{1} \leqslant d_{2} \leqslant \ldots \leqslant d_{n}$. Пусть мы нашли решение для работ $1, 2, \ldots, i-1$. Очевидно, что $S \subseteq \{1, \ldots i-1\}$.

Пусть $h^S$ — вектор соответствующий множеству $S$ из задачи $O \mid p_{i,j} = 1, d_i \mid -$. Тогда, для добавления работы $i$ в множество $S$ должно выполняться неравенство: $m(d_i-m)-(km-\sum\limits_{j=1}^m {h^S(d_i-m+j)})+x(d_i) \geqslant m$, где $k=|S|$ и $x(d_i)$ — номер периода времени $t$, чтобы $d_i-m+1 \leqslant t \leqslant d_i$ и $h^S(t) \lt m$. Чтобы проверить это неравенство, нам нужно $m$ чисел $h^S(t), t=d_i-m+1, \ldots, d_i$.

Определим переменные:

$k_j=\left\{ \begin{matrix} h^S(d_i-m+j) & j \in \{1,\ldots ,m\} \\ 0 & j \notin \{1, \ldots , m\} \\ \end{matrix} \right.$

$l_j=\left\{\begin{matrix} 1 & j \in \{1, \ldots, m\}; & k_j \lt m \\ 0 & otherwise \\ \end{matrix} \right.$.

Тогда можно заметить, что $x(d_i)=\sum\limits_{j=1}^m {l_j}$.

Упростим исходное неравенство: $m(d_i-m)-(km-\sum\limits_{j=1}^m {k_j})+\sum\limits_{j=1}^m {l_j} \geqslant m$ или $m(d_i-m-k)+ \sum\limits_{j=1}^m {(k_j+l_j)} \geqslant m$.

Для динамического программирования определим $f_i(k,k_1 \ldots , k_m)$ для минимизации $\sum\limits_{j=i}^n {w_jU_j}$, где $k=|S|, S \subseteq \{1, \ldots , i-1\}$ и $k_j=h^S(d_i-m+j)$ где $j=1, \ldots , m$.

Пусть $p=d_{i+1}-d_i$, тогда определим рекуррентное выражение для $f_i(k,k_1 \ldots , k_m)$:

$f(k,k_1 \ldots , k_m)=\left\{\begin{matrix} f_{i+1}(k,k_{1+p},k_{2+p}, \ldots, k_{m+p})+w_i, & m(d_i-m-k)+ \sum\limits_{j=1}^m {(k_j+l_j)} \lt m \\ \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(d_i-m-k)+ \sum\limits_{j=1}^m {(k_j+l_j)} \geqslant m\\ \end{matrix} \right.$

и начальное условие: $f_{n+1}(k,k_1,\ldots ,k_m)=0$ для $k,k_1,\ldots ,k_m = 0,1,\ldots ,m$.

См. также

• $O \mid p_{i,j} = 1, d_i \mid -$
• $O \mid p_{ij} = 1 \mid \sum U_i$

Источники информации

• Peter Brucker. «Scheduling Algorithms» — «Springer», 2006 г. — c. 168 - 171. ISBN 978-3-540-69515-8