Изменения

<tex dpi = "200"> O \mid p_{i,j} = 1 \mid \sum w_{i} U_{i} </tex>

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

Для решения этой задачи, мы должны найти множество <tex>S</tex> работ, которые успеваем выполнить до дедлайна. Значит нам надо минимизировать: <tex>\sum\limits_{i \notin S} {w_{i}}</tex>. Будем решать эту задачу с помощью [[Динамическое_программирование|динамического программирования]] с использованием утверждений из решения задачи [[Opij1di|<tex> O \mid p_{i,j} = 1, d_i 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_id_{i} -m)-(kmk m -\sum\limits_{j=1}^m {h^S(d_id_{i} -m+j)})+x(d_id_{i}) \geqslant m</tex>, где <tex>k=|S|</tex> и <tex>x(d_id_{i})</tex> {{---}} количество периодов времени <tex>t</tex> со свойствами: <tex>d_id_{i} -m+1 \leqslant t \leqslant d_id_{i}</tex> и <tex>h^S(t) < m</tex>. Чтобы проверить это неравенство, нам нужно посчитать <tex>m</tex> чисел <tex>h^S(t)</tex>, <tex>t=d_id_{i} -m+1, \ldots, d_id_{i}</tex>. Для этого определим переменные:

<tex>k_jk_{j} = \begin{cases} h^S(d_id_{i} -m+j) & j \in \{1,\ldots ,m\} \\0 & j \notin \{1, \ldots , m\} \\\end{cases}</tex>,  <tex>l_j = \begin{cases}1 & j \in \{1 , \ldots , m\}\text{; } k_{j} < m \\0 & \text{otherwise} \\

Тогда можно заметить, что <tex>l_jx(d_{i}) =\beginsum\limits_{casesj = 1}^m {l_{j}}</tex>, так как <tex>l_{j} = 1</tex> если <tex>1 & \leqslant j \in \leqslant m</tex> и <tex>h^S(d_{i} - m + j) < m</tex> или <tex>d_{i} - m + 1, \ldots, leqslant d_{i} - m+ j \leqslant d_{i}</tex> и <tex>h^S(d_{i}- m + j) < m</tex>. Следовательно можно упростить исходное неравенство: <tex>m \textcdot (d_{; i} k_j < - m) - (k m - \sum \0 & limits_{j = 1}^m {k_{j}}) + \sum \textlimits_{otherwisej = 1} ^m {l_{j}} \geqslant m</tex> или <tex>m \cdot (d_{i} - m - k)+ \sum\endlimits_{j = 1}^m {(k_{j} + l_{casesj})} .\geqslant m</tex>.

Тогда можно заметить, что Для динамического программирования определим <tex>xf_{i} (d_i)=\sum\limits_k , k_{j=1}^, \ldots , k_{m })</tex> {l_j{---}} минимальное значение целевой функции для расписания работ <tex>i , i + 1 , \ldots , n</tex>. Следовательно можно упростить исходное неравенство: , позволяющее выполнить работы из множества <tex>S</tex> без опоздания, где <tex>mk = |S|, S \subseteq \{1, \cdot (d_i-m)-(kmldots , i -1\sum\limits_}</tex> и <tex>k_{j}=1}h^m S(d_{k_ji}- m + j)+\sum\limits_{</tex>, где <tex>j=1}^m {l_j} , \geqslant ldots , m</tex> или , то есть <tex>f_{i} (k, k_{1}, \ldots , k_{m}) = \min \limits_{S: |S| = k, S \subseteq \{1, \ldots , i - 1 \cdot }} (d_i-m-k)+ \sum\limits_{j=1i}^m n {w_{j} U_{(k_j+l_jj}})} \geqslant m</tex>.

Для динамического программирования определим Пусть <tex>f_i(k,k_1 \ldots , k_m) p = \min(\sum\limits_d_{j=i+ 1}^n - d_{w_jU_ji})</tex>, где тогда определим рекуррентное выражение для <tex>f_{i} (k=|S|, S \subseteq \k_{1}, \ldots , i-1\}</tex> и <tex>k_j=h^S(d_i-m+jk_m)</tex> где <tex>j=1, \ldots , 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}-d_i^m {(k_{j} + l_{j})} </tex>m \text{ } (1)\\\min(f_{i + 1} (k, k_{1 + p}, k_{2 + p}, \ldots , тогда определим рекуррентное выражение для <tex>f_ik_{m + p}) + w_{i} ; f_{i + 1} (k+ 1, k_{1 + p} + l_{1 + p}, k_{2 + p} + l_{2 + p},k_1 \ldots , k_mk_{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}</tex>:

c начальным условием: <tex>f_i(k,k_1 \ldots , k_m)=\begin{cases}f_{in +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)} 0 </tex> для < m (1)\\\min(f_{i+1}(tex>k,k_{1+p},k_{2+p}, \ldots ,k_{m+p})+w_i ; f_{i+1}(k+1= 0,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)\\\end{cases}.</tex>.

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

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

Ответ на задачу будет находиться ==Пример работы==Пусть <tex>m = 2</tex> и <tex>n = 3</tex>. {| class="wikitable" style="width:5cm" border=1|+|-align="center" bgcolor=#EEEEFF! номер работы || дедлайн || вес|-align="center" bgcolor=#FFFFFF| 1 || 2 || 7 |-align="center" bgcolor=#FFFFFF| 2 || 2 || 6 |-align="center" bgcolor=#FFFFFF| 3 || 2 || 5 |}Для такой задачи получится таблица для функции <tex>f</tex>:{| class="wikitable" style="width:20cm" border=1|+|-aling="center" bgcolor=#EEEEFF! <tex>k</tex> || <tex>k_1</tex> || <tex>k_2</tex> || <tex>f_{4} (k, k_1, k_2)</tex> || <tex>f_{3} (k, k_1, k_2)</tex> || <tex>f_{2} (k, k_1, k_2)</tex> || <tex>f_{1} (k, k_1, k_2)</tex>|-align="center" bgcolor=#FFFFFF| 0 || 0 || 0 || 0 || 0 || 0 || 5|-align="center" bgcolor=#FFFFFF| 0 || 0 || 1 || 0 || 0 || 0 || 0|-align="center" bgcolor=#FFFFFF| 0 || 0 || 2 || 0 || 0 || 0 || 0|-align="center" bgcolor=#FFFFFF| 0 || 1 || 0 || 0 || 0 || 0 || 0|-align="center" bgcolor=#FFFFFF| 0 || 1 || 1 || 0 || 0 || 0 || 0|-align="center" bgcolor=#FFFFFF| 0 || 1 || 2 || 0 || 0 || 0 || 0|-align="center" bgcolor=#FFFFFF| 0 || 2 || 0 || 0 || 0 || 0 || 0|-align="center" bgcolor=#FFFFFF| 0 || 2 || 1 || 0 || 0 || 0 || 0|-align="center" bgcolor=#FFFFFF| 0 || 2 || 2 || 0 || 0 || 0 || 0|-align="center" bgcolor=#FFFFFF| 1 || 0 || 0 || 0 || 5 || 11 || 7|-align="center" bgcolor=#FFFFFF| 1 || 0 || 1 || 0 || 5 || 11 || 7|-align="center" bgcolor=#FFFFFF| 1 || 0 || 2 || 0 || 5 || 0 || 0|-align="center" bgcolor=#FFFFFF| 1 || 1 || 0 || 0 || 5 || 11 || 7|-align="center" bgcolor=#FFFFFF| 1 || 1 || 1 || 0 || 0 || 5 || 7|-align="center" bgcolor=#FFFFFF| 1 || 1 || 2 || 0 || 0 || 0 || 0|-align="center" bgcolor=#FFFFFF| 1 || 2 || 0 || 0 || 5 || 0 || 0|-align="center" bgcolor=#FFFFFF| 1 || 2 || 1 || 0 || 0 || 0 || 0|-align="center" bgcolor=#FFFFFF| 1 || 2 || 2 || 0 || 0 || 0 || 0|-align="center" bgcolor=#FFFFFF| 2 || 0 || 0 || 0 || 5 || 0 || 0|-align="center" bgcolor=#FFFFFF| 2 || 0 || 1 || 0 || 5 || 0 || 0|-align="center" bgcolor=#FFFFFF| 2 || 0 || 2 || 0 || 5 || 0 || 0|-align="center" bgcolor=#FFFFFF| 2 || 1 || 0 || 0 || 5 || 0 || 0|-align="center" bgcolor=#FFFFFF| 2 || 1 || 1 || 0 || 5 || 0 || 0|-align="center" bgcolor=#FFFFFF| 2 || 1 || 2 || 0 || 5 || 0 || 0|-align="center" bgcolor=#FFFFFF| 2 || 2 || 0 || 0 || 5 || 0 || 0|-align="center" bgcolor=#FFFFFF| 2 || 2 || 1 || 0 || 5 || 0 || 0|-align="center" bgcolor=#FFFFFF| 2 || 2 || 2 || 0 || 5 || 0 || 0|}Действительно, в <tex>f_1(0,0,\ldots,0)</tex>записано <tex>5</tex>, что является минимальным значением целевой функции.

Для определения времени работы алгоритма надо заметить, что <tex>i= 0,\ldots , n</tex>, <tex> k=0,\ldots , n</tex>, и <tex>k_j=0,\ldots m</tex> где <tex>j=1,\ldots , m</tex>. Из рекуррентной формулы очевидно, что для подсчета одного значения <tex>f_if_{i} (k,k_1k_{1}, \ldots ,k_mk_{m})</tex> нужно <tex>O(m)</tex> времени. Значит , алгоритм работает за <tex>O(n^2m2 m^{m+1})</tex> или <tex>O(n^2)</tex> для фиксированного <tex>m</tex>.

* [[Opij1di|<tex> O \mid p_{i,j} = 1, d_i \mid - </tex>]]* [[Opi1sumu|<tex>O \mid p_{iji, j} = 1 \mid \sum U_i</tex>]]* [[1pi1sumwu|<tex>1 \mid p_{i} = 1 \mid \sum w_{i}U_{i}</tex>]]