Изменения

Для решения этой задачи, мы должны найти множество <tex>S</tex> работ, которые успеваем выполнить до дедлайна. Значит нам надо минимизировать: <tex>\sum\limits_{i \notin S} {w_{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\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>. Для этого определим переменные:

h^S(d_i-m+j) & j \in \{1,\ldots ,m\} \\0 & j \notin \{1, \ldots , m\} \\

1 & j \in \{1, \ldots, m\}\text{; } k_j < m \\

Тогда можно заметить, что <tex>x(d_i)=\sum\limits_{j=1}^m {l_j}</tex>, так как <tex>l_j=1</tex> если <tex>1 \leqslant j \leqslant m</tex> и <tex>h^S(d_i-m+j) < m</tex> или <tex>d_i-m+1 \leqslant d_i-m+j \leqslant d_i</tex> и <tex>h^S(d_i-m+j) < m</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)</tex> {{---}} минимальное значение целевой функции для расписания работ <tex>i, i+1, \ldots , n</tex>, позволяющее выполнить работы из множества <tex>S</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)=\min\limits_{S: |S|=k, S \subseteq \{1, \ldots , i-1 \}}(\sum\limits_{j=i}^n {w_jU_j})</tex>.

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

<tex>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)} < m (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 (2)\\

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

Если выполняется неравенство <tex>(1)</tex>, то мы не можем добавить работу <tex>i</tex> в множество <tex>S</tex> и поэтому <tex>f_i(k,k_1 \ldots , k_m) = f_{i+1}(k,k_{1+p},k_{2+p}, \ldots, k_{m+p})+w_i</tex>.

Если выполняется неравенство <tex>(2)</tex>, тогда мы может добавить работу <tex>i</tex> в множество <tex>S</tex> или не добавлять. Если мы добавим работу <tex>i</tex>, то <tex>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}) (3)</tex>. Если мы не добавим работу <tex>i</tex>, то по аналогии с первым случаем <tex>f_i(k,k_1, \ldots , k_m) = f_{i+1}(k,k_{1+p},k_{2+p}, \ldots, k_{m+p})+w_i (4)</tex>. Так как <tex>f_i(k,k_1, \ldots , k_m) = \min(\sum\limits_{j=i}^n {w_jU_j})</tex>, то нам надо взять минимум из значений <tex>(3)</tex> и <tex>(4)</tex>. Ответ на задачу будет находиться в <tex>f_1(0, 0, \ldots , 0)</tex>.