748
правок
Изменения
→Алгоритм
Дано <tex>m</tex> одинаковых станков, которые работают параллельно, и <tex>n</tex> работ, которые необходимо выполнить в произвольном порядке на всех станках. Любая работа на любом станке выполняется за единицу времени. Для каждой работы есть время окончания <tex>d_i</tex> {{---}} время, до которого она должна быть выполнена. Требуется минимизировать <tex>\sum w_{i} U_{i}</tex>, то есть суммарный вес всех просроченных работ.
}}
==АлгоритмОписание алгоритма==Для решения этой задачи, мы должны найти множество <tex>S</tex>, что <tex>\sum\limits_{i \notin S} {w_{i} U_{i}}</tex> минимальна. Будем решать эту задачу с помощью динамического программирования с использованием утверждений из решении задачи [[Opij1di|<tex> O \mid p_{i,j} = 1, d_i \mid - </tex>]].
Рассмотрим работы в порядке не убывания дедлайнов: <tex>d_{1} \leqslant d_{2} \leqslant \ldots \leqslant d_{n}</tex>. Пусть мы нашли решение для работ <tex>1, 2, \ldots, i-1</tex>. Очевидно, что <tex>S \subseteq \{1, \ldots i-1\}</tex>.
Пусть <tex>h^S</tex> {{---}} вектор соответствующий множеству <tex>S</tex> из задачи [[Opij1di|<tex> O \mid p_{i,j} = 1, d_i \mid - </tex>]]. Тогда, для добавления работы <tex>i</tex> в множество <tex>S</tex> должно выполняться неравенство: <tex>m(d_i-m)-(km-\sum\limits_{j=1}^m {h^S(d_i-m+j)})+x(d_i) \geqslant m</tex>, где <tex>k=|S|</tex> и <tex>x(d_i)</tex> {{---}} номер периода времени <tex>t</tex>, чтобы <tex>d_i-m+1 \leqslant t \leqslant d_i</tex> и <tex>h^S(t) < m</tex>. Чтобы проверить это неравенство, нам нужно <tex>m</tex> чисел <tex>h^S(t), t=d_i-m+1, \ldots, d_i</tex>.
Определим переменные:
<tex>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.</tex>
<tex>l_j=\left\{\begin{matrix}
1 & j \in \{1, \ldots, m\}; & k_j < m \\
0 & otherwise \\
\end{matrix} \right.</tex>.
Тогда можно заметить, что <tex>x(d_i)=\sum\limits_{j=1}^m {l_j}</tex>.
Упростим исходное неравенство: <tex>m(d_i-m)-(km-\sum\limits_{j=1}^m {k_j})+\sum\limits_{j=1}^m {l_j} \geqslant m</tex> или <tex>m(d_i-m-k)+ \sum\limits_{j=1}^m {(k_j+l_j)} \geqslant m</tex>.
Для динамического программирования определим <tex>f_i(k,k_1 \ldots , k_m)</tex> для минимизации <tex>\sum\limits_{j=i}^n {w_jU_j}</tex>, где <tex>k=|S|, S \subseteq \{1, \ldots , i-1\}</tex> и <tex>k_j=h^S(d_i-m+j)</tex> где <tex>j=1, \ldots , m</tex>.
Пусть <tex>p=d_{i+1}-d_i</tex>, тогда определим рекуррентное выражение для <tex>f_i(k,k_1 \ldots , k_m)</tex>:
<tex>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)} < 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.</tex>
и начальное условие: <tex>f_{n+1}(k,k_1,\ldots ,k_m)=0 </tex> для <tex>k,k_1,\ldots ,k_m = 0,1,\ldots ,m</tex>.
==Доказательство корректности==
