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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Доказательство корректности)
м (rollbackEdits.php mass rollback)
 
(не показано 48 промежуточных версий 3 участников)
Строка 1: Строка 1:
<tex dpi = "200"> O \mid p_{i,j} = 1 \mid \sum w_{i} U_{i} </tex>
+
<tex dpi = "200"> O \mid p_{i, j} = 1 \mid \sum w_{i} U_{i} </tex>
 
{{Задача
 
{{Задача
 
|definition=
 
|definition=
Дано <tex>m</tex> одинаковых станков, которые работают параллельно, и <tex>n</tex> работ, которые необходимо выполнить в произвольном порядке на всех станках. Любая работа на любом станке выполняется за единицу времени. Для каждой работы есть время окончания <tex>d_i</tex> {{---}} время, до которого она должна быть выполнена. Требуется минимизировать <tex>\sum w_{i} U_{i}</tex>, то есть суммарный вес всех просроченных работ.
+
Дано <tex>m</tex> одинаковых станков, которые работают параллельно, и <tex>n</tex> работ, которые необходимо выполнить в произвольном порядке на всех станках. Любая работа на любом станке выполняется за единицу времени. Для каждой работы есть время окончания <tex>d_{i}</tex> {{---}} время, до которого она должна быть выполнена. Требуется минимизировать <tex>\sum w_{i} U_{i}</tex>, то есть суммарный вес всех просроченных работ.
 
}}
 
}}
==Алгоритм==
+
==Описание алгоритма==
Идея алгоритма состоит в том, что на шаге <tex>k</tex> строим оптимальное решение для первых <tex>k</tex> работ с наименьшими дедлайнами.
+
Для решения этой задачи, мы должны найти множество <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>k</tex> работ, тогда множество <tex>S_k</tex> содержит только те работы, которые мы успеваем выполнить в порядке не убывания дедлайнов при оптимальном расписании. Рассмотрим работу <tex>k+1</tex>. Если мы ее успеваем выполнить данную работу, до наступления дедлайна, то  добавим в множество <tex>S_{k}</tex> и получим множество <tex>S_{k+1}</tex>. Если же <tex>k+1</tex> работу мы не успеваем выполнить до дедлайна, то найдем в <tex>S_k</tex> работу <tex>l</tex> c наименьшим весом <tex>w_{l}</tex> и заменим ее на работу <tex>k+1</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>S_{n}</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) - ( k m - \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} = \begin{cases}
Предполагаем, что перед началом выполнения алгоритма выполняется, что <tex>m \leqslant d_{1} \leqslant d_{2} \leqslant \ldots \leqslant d_{n}</tex>. Все работы, дедлайн которых меньше <tex>m</tex>, мы в любом случае выполнить без штрафа не успеем, поэтому их изначально можно отнести к просроченным.
+
h^S(d_{i} - m + j) & j \in \{1 , \ldots , m\} \\
 +
0 & j \notin \{1 , \ldots , m\} \\
 +
\end{cases}</tex>,  
  
<tex>S</tex> {{---}} множество непросроченных работ, <tex>Check</tex> {{---}} функция, решающая задачу [[Opij1di|<tex> O \mid p_{i,j} = 1, d_i \mid - </tex>]].
+
<tex>l_j = \begin{cases}
 +
1 & j \in \{1 , \ldots , m\}\text{; } k_{j} < m \\
 +
0 & \text{otherwise} \\
 +
\end{cases} .</tex>  
  
S =  <tex>\varnothing</tex>
+
Тогда можно заметить, что <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) - (k m - \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>.
'''for''' i = 1 to n
 
    S = <tex> S \cup \{i\} </tex>
 
    '''if''' '''not''' Check(s) :
 
        найти такое <tex>k</tex>, что <tex>w_{k} = \min \{ w_{j} \mid j \in S\}</tex>
 
        S = <tex>S \setminus \{k\}</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_{j} U_{j}})</tex>.
  
{{Утверждение
+
Пусть <tex>p = d_{i + 1} - d_{i}</tex>, тогда определим рекуррентное выражение для <tex>f_{i} (k, k_{1}, \ldots , k_m)</tex>:
|statement=Алгоритм строит корректное расписание.
 
|proof=Если мы успеваем выполнить очередную работу, то, очевидно, от ее добавления, расписание не может стать некорректным. В противном случае мы пытаемся заменить одну работу из множества <tex> S </tex> на текущую. Но это так же не может сделать наше расписание некорректным. Это следует из того, что мы рассматриваем работы в порядке неуменьшениях их дедлайнов. Пусть мы заменяем работу <tex> k </tex> на работу <tex> i </tex>. Но <tex> d_{k} \leqslant d_{i} </tex>, следовательно, если мы успевали выполнить работу <tex> k </tex>, то успеем выполнить и работу <tex> i </tex>.
 
}}
 
  
{{Теорема
+
<tex>f_{i} (k, k_{1}, \ldots , k_{m}) = \begin{cases}
|statement=Построенное данным алгоритмом расписание оптимально.
+
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 \text{ } (1)\\
|proof=
+
\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 \text{ }(2)\\
Пусть <tex> S^* </tex> множество непросроченных работ в оптимальном расписании. Также пусть <tex> l </tex> {{---}} первая работа из множества <tex> S </tex>, которая не входит в <tex> S^* </tex>, а <tex> k </tex> {{---}} первая работа из <tex> S^* </tex>, не содержащаяся в <tex> S </tex>. Мы можем предполагать существование этих работ, потому что <tex> S^* </tex> не может содержать <tex> S </tex> как подмножество, иначе это противоречило бы построению <tex> S </tex>. С другой стороны, если <tex> S^* \subseteq S </tex>, то <tex> S </tex> должно быть тоже оптимальным, и правильность алгоритма доказана.
+
\end{cases}</tex>
  
Для доказательства покажем, что мы можем заменить работу <tex> k </tex> на работу <tex> l </tex> в оптимальном расписании, не увеличивая минимизируемую функцию.
+
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> l < k </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}) \text{ } (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} \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> k </tex> не содержится в <tex> S </tex>, то либо она не была добавлена при ее рассмотрении, либо была заменена работой, рассмотренной позднее. В любом случае это означает, что <tex> w_{k} \leqslant w_{l} </tex>. Так же по определению <tex> k </tex> все работы <tex> i \in S^* : i < k </tex> должны содержаться и в <tex> S </tex>. Но тогда заменив в оптимальном расписании <tex> k </tex> на <tex> l </tex>, мы сохраним корректность расписания и не увеличим минимизируемую функцию.
 
*<tex> k < l </tex>
 
Так как мы рассматриваем работы в порядке неубывания их дедлайнов, то, следовательно, <tex> d_{k} \leqslant d_{l} </tex>, и замена работы <tex> k </tex> на <tex> l </tex> в оптимальном расписании <tex> S^* </tex> не может сделать его некорректным. Тогда для доказательства нам осталось показать, что <tex> w_{k} \leqslant w_{l} </tex>.
 
  
Пусть <tex> k_{i_{0}} = k </tex> {{---}} работа, замененная работой <tex> i_{0} </tex> в процессе построения <tex> S </tex>, и пусть <tex> k_{i_{1}}, \ldots, k_{i_{r}} </tex> {{---}} последовательность работ, которые были исключены из <tex> S </tex> после замены <tex> k </tex>, причем работа <tex> k_{i_{v}} </tex> была заменена работой <tex> i_{v} </tex>. <tex> i_{0} < i_{1} < \ldots < i_{r} </tex>. Будем говорить, что "работа <tex> i_{v} </tex> подавляет <tex> i_{m} </tex>", где <tex> m < v </tex>, если <tex> k_{i_{v}} \leqslant i_{m} </tex>. В таком случае получаем, что <tex> w_{k_{i_{v}}} \geqslant w_{k_{i_{m}}}</tex>, потому что в противном случае работа <tex> k_{i_{v}} </tex> была бы исключена из <tex> S </tex> раньше чем <tex> k_{i_{m}} </tex>.  
+
Ответ на задачу будет находиться в <tex>f_{1} (0, 0, \ldots , 0)</tex>.
  
Если в последовательности <tex> i_{0} < i_{1} < \ldots < i_{r} </tex> существует подпоследовательность <tex> j_{0} = i_{0} < j_{1} < \ldots < j_{s} </tex> такая, что <tex> j_{v + 1} </tex> подавляет <tex> j_{v} </tex> для всех <tex> v = 0,1, \ldots, s - 1 </tex> и <tex> j_{s - 1} < l \leqslant j_{s} </tex>, то получаем, что <tex> w_{l} \geqslant w_{k_{j_{s}}} \geqslant \ldots \geqslant w_{k_{j_{0}}} = w_{k} </tex>, что доказывает оптимальность расписания <tex> S </tex>.
+
==Пример работы==
 
+
Пусть <tex>m = 2</tex> и <tex>n = 3</tex>.
Покажем, что отсутствие такой подпоследовательности приведет нас к противоречию, из чего будет следовать ее существование.
+
{| class="wikitable" style="width:5cm" border=1
 
+
|+
Предположим, что такой подпоследовательности не существует. Тогда найдем наименьшее <tex> t </tex> такое, что не существует работы <tex> i_{v} : v > t </tex>, которая бы подавляла работу <tex> i_{t} </tex>, и <tex> i_{t} </tex> было бы меньше <tex> l </tex>. По определению <tex> l </tex> и <tex> i_{t} </tex> и из факта, что <tex> i_{t} < l </tex>, получаем, что после добавления во множество <tex> S </tex> работы <tex> i_{t} </tex>, ни одна из работ, рассмотренных ранее, не будет удалена из <tex> S </tex>, а так же все эти работы содержатся и в оптимальном расписании <tex> S^* </tex>, поскольку <tex> i_t < l </tex>.
+
|-align="center" bgcolor=#EEEEFF
 
+
! номер работы || дедлайн || вес
Пусть <tex> S_t </tex> это множество <tex> S </tex> после замены работы <tex> k_{i_t} </tex> на <tex> i_t </tex>. Если <tex> k_{i_t} > k </tex>, то в оптимальном расписании <tex> S^* </tex> мы можем заменить работу <tex> k </tex> на <tex> k_{i_t} </tex>, поскольку <tex> d_{k_{i_t}} \geqslant d_k </tex>. Но так как <tex> S_t \subset S^* </tex>, то все работы из множества <tex> S_t \cup \{k_{i_t}\} </tex> могут быть выполнены до их дедлайнов, что противоречит построению <tex> S </tex>. Следовательно, <tex> k_{i_t} < k </tex>. Тогда аналогично предыдущему случаю получаем, что все работы из множества <tex> S_t \cup \{k\} </tex> могут быть выполнены вовремя. Кроме того, все работы из <tex> \{ j \in S_t | j < k \} \cup \{k_{i_t}\} </tex> так же могут быть выполнены вовремя, что следует из построения <tex> S_t </tex>. Но тогда получается, что все работы и из множества <tex> S_t \cup \{k_{i_t}\} </tex> так же могут быть выполнены вовремя, что опять приводит нас к противоречию с построением <tex> S </tex>.
+
|-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, 0)</tex> записано <tex>5</tex>, что является минимальным значением целевой функции.
  
 
==Время работы==
 
==Время работы==
Время работы зависит от того, на сколько быстро мы будем добавлять, находить и удалять работы из множества <tex>S</tex>. В качестве <tex>S</tex> можно использовать [[Двоичная куча | двоичную кучу]] или [[Красно-черное дерево | красно-черное дерево]] и тогда все нужные нам операции будут выполняться за <tex>O(\log n)</tex>. Тогда время алгоритма будет <tex>O(n \cdot (\log n + T(Check)))</tex>. Так как <tex>T(Check)=O(n \cdot m)</tex>, то время алгоритма <tex>O(n^2 \cdot m)</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_{i} (k, k_{1}, \ldots , k_{m})</tex> нужно <tex>O(m)</tex> времени. Значит, алгоритм работает за <tex>O(n^2 m^{m + 1})</tex>.
  
 
==См. также==
 
==См. также==
* [[Opij1di|<tex> O \mid p_{i,j} = 1, d_i \mid - </tex>]]
+
* [[Opij1di|<tex> O \mid p_{i, j} = 1, d_i \mid - </tex>]]
* [[Opi1sumu|<tex>O \mid p_{ij} = 1 \mid \sum U_i</tex>]]
+
* [[Opi1sumu|<tex>O \mid p_{i, j} = 1 \mid \sum U_i</tex>]]
 +
* [[1pi1sumwu|<tex>1 \mid p_{i} = 1 \mid \sum w_{i}U_{i}</tex>]]
  
 
==Источники информации==
 
==Источники информации==
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 168. стр.
+
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} c. 168 - 170. ISBN 978-3-540-69515-8
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Теория расписаний]]
 
[[Категория: Теория расписаний]]

Текущая версия на 19:29, 4 сентября 2022

[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}}[/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) - ( k m - \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\}\text{; } k_{j} \lt m \\ 0 & \text{otherwise} \\ \end{cases} .[/math]

Тогда можно заметить, что [math]x(d_{i}) = \sum\limits_{j = 1}^m {l_{j}}[/math], так как [math]l_{j} = 1[/math] если [math]1 \leqslant j \leqslant m[/math] и [math]h^S(d_{i} - m + j) \lt m[/math] или [math]d_{i} - m + 1 \leqslant d_{i} - m + j \leqslant d_{i}[/math] и [math]h^S(d_{i} - m + j) \lt m[/math]. Следовательно можно упростить исходное неравенство: [math]m \cdot (d_{i} - m) - (k m - \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})[/math] — минимальное значение целевой функции для расписания работ [math]i , i + 1 , \ldots , n[/math], позволяющее выполнить работы из множества [math]S[/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]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_{j} U_{j}})[/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 \text{ } (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 \text{ }(2)\\ \end{cases}[/math]

c начальным условием: [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}) \text{ } (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} \text{ } (4)[/math]. Так как [math]f_{i} (k, k_{1}, \ldots , k_{m}) = \min(\sum \limits_{j = i}^n {w_{j} U_{j}})[/math], то нам надо взять минимум из значений [math](3)[/math] и [math](4)[/math].

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

Пример работы

Пусть [math]m = 2[/math] и [math]n = 3[/math].

номер работы дедлайн вес
1 2 7
2 2 6
3 2 5

Для такой задачи получится таблица для функции [math]f[/math]:

[math]k[/math] [math]k_1[/math] [math]k_2[/math] [math]f_{4} (k, k_1, k_2)[/math] [math]f_{3} (k, k_1, k_2)[/math] [math]f_{2} (k, k_1, k_2)[/math] [math]f_{1} (k, k_1, k_2)[/math]
0 0 0 0 0 0 5
0 0 1 0 0 0 0
0 0 2 0 0 0 0
0 1 0 0 0 0 0
0 1 1 0 0 0 0
0 1 2 0 0 0 0
0 2 0 0 0 0 0
0 2 1 0 0 0 0
0 2 2 0 0 0 0
1 0 0 0 5 11 7
1 0 1 0 5 11 7
1 0 2 0 5 0 0
1 1 0 0 5 11 7
1 1 1 0 0 5 7
1 1 2 0 0 0 0
1 2 0 0 5 0 0
1 2 1 0 0 0 0
1 2 2 0 0 0 0
2 0 0 0 5 0 0
2 0 1 0 5 0 0
2 0 2 0 5 0 0
2 1 0 0 5 0 0
2 1 1 0 5 0 0
2 1 2 0 5 0 0
2 2 0 0 5 0 0
2 2 1 0 5 0 0
2 2 2 0 5 0 0

Действительно, в [math]f_1 (0, 0, 0)[/math] записано [math]5[/math], что является минимальным значением целевой функции.

Время работы

Для определения времени работы алгоритма надо заметить, что [math]i = 0, \ldots , n[/math], [math] 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^2 m^{m + 1})[/math].

См. также

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

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