748
правок
Изменения
→Описание алгоритма
Рассмотрим работы в порядке не убывания дедлайнов: <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\cdot (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)</tex>, <tex>t=d_i-m+1, \ldots, d_i</tex>. Для этого определим переменные:
<tex>k_j=\left\{ \begin{matrix}
\end{matrix} \right.</tex>.
Тогда можно заметить, что <tex>x(d_i)=\sum\limits_{j=1}^m {l_j}</tex>. Следовательно можно упростим исходное неравенство: <tex>m\cdot (d_i-m)-(km-\sum\limits_{j=1}^m {k_j})+\sum\limits_{j=1}^m {l_j} \geqslant m</tex> или <tex>m\cdot (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) = \min(\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>f_i(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\cdot (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\cdot (d_i-m-k)+ \sum\limits_{j=1}^m {(k_j+l_j)} \geqslant m\\
\end{matrix} \right.</tex>
