Opij1sumwu — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Время работы)
(Описание алгоритма)
Строка 11: Строка 11:
 
Пусть <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>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}  
+
<tex>k_j= \begin{cases}  
 
h^S(d_i-m+j) & j \in \{1,\ldots ,m\} \\
 
h^S(d_i-m+j) & j \in \{1,\ldots ,m\} \\
 
0 & j \notin \{1, \ldots , m\} \\
 
0 & j \notin \{1, \ldots , m\} \\
\end{matrix} \right.</tex>  
+
\end{cases} .</tex>  
  
<tex>l_j=\left\{\begin{matrix}
+
<tex>l_j=\begin{cases}
1 & j \in \{1, \ldots, m\}; & k_j < m \\
+
1 & j \in \{1, \ldots, m\}; k_j < m \\
 
0 & otherwise \\
 
0 & otherwise \\
\end{matrix} \right.</tex>.  
+
\end{cases} .</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>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>.
Строка 27: Строка 27:
 
Пусть <tex>p=d_{i+1}-d_i</tex>, тогда определим рекуррентное выражение для <tex>f_i(k,k_1 \ldots , k_m)</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)=\left\{\begin{matrix}
+
<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)\\
 
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)\\
 
\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)\\
\end{matrix} \right.</tex>
+
\end{cases}.</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>.
 
и начальное условие: <tex>f_{n+1}(k,k_1,\ldots ,k_m)=0 </tex> для <tex>k,k_1,\ldots ,k_m = 0,1,\ldots ,m</tex>.

Версия 14:43, 22 мая 2016

[math] O \mid p_{i,j} = 1 \mid \sum w_{i} U_{i} [/math]

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

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

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

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

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

[math]k_j= \begin{cases} h^S(d_i-m+j) & j \in \{1,\ldots ,m\} \\ 0 & j \notin \{1, \ldots , m\} \\ \end{cases} .[/math]

[math]l_j=\begin{cases} 1 & j \in \{1, \ldots, m\}; k_j \lt m \\ 0 & otherwise \\ \end{cases} .[/math].

Тогда можно заметить, что [math]x(d_i)=\sum\limits_{j=1}^m {l_j}[/math]. Следовательно можно упростить исходное неравенство: [math]m\cdot (d_i-m)-(km-\sum\limits_{j=1}^m {k_j})+\sum\limits_{j=1}^m {l_j} \geqslant m[/math] или [math]m\cdot (d_i-m-k)+ \sum\limits_{j=1}^m {(k_j+l_j)} \geqslant m[/math].

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

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

[math]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)} \lt 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)\\ \end{cases}.[/math]

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

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

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

Ответ на задачу будет находиться в [math]f_1(0,0,\ldots,0)[/math].

Время работы

Для определения времени работы алгоритма надо заметить, что [math]i,k=0,\ldots n[/math], [math]k_j=0,\ldots m[/math] где [math]j=1,\ldots m[/math]. Из рекуррентной формулы очевидно, что для подсчета одного значения [math]f_i(k,k_1, \ldots ,k_m)[/math] нужно [math]O(m)[/math] времени. Значит алгоритм работает за [math]O(n^2m^{m+1})[/math] или [math]O(n^2)[/math] для фиксированного [math]m[/math].

См. также

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

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