1sumwT

[math]1 \mid\mid \sum w_i T_i[/math]

Задача:

Есть один станок и [math]n[/math] работ. Для каждой работы заданы время выполнения [math] p_i,[/math] дедлайн [math]d_i[/math] и стоимость выполнения этой работы [math]w_i \geqslant 0[/math]. Необходимо минимизировать [math]\sum w_i T_i[/math].

Псевдополиномиальное решение

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

Упорядочим работы в порядке неубывания дедлайнов. Обозначим за [math]k[/math] работу с максимальным [math]p_i[/math].
Будем делить имеющиеся у нас работы на множества [math] I_1, I_2[/math] так, чтобы для любого [math]j \geqslant k[/math] [math]I_1 = \{1,\ldots, j\}\setminus\{k\}[/math], [math]I_2 = \{j+1,\ldots, n\}[/math]. Тогда в оптимальном расписании все работы из [math]I_1[/math] окажутся до [math]k[/math], а работы из [math]I_2[/math] будут расположены после [math]k[/math]. Для работ из [math] I_1[/math] оптимальное время начала выполнения [math]t_1 = 0[/math], для работ из [math]I_2[/math] оптимальное начало [math]t_2 = p = \sum\limits_{i=1}^j p_i[/math]. Таким образом, для любой [math]j[/math] задача разбивается на 2 подзадачи.
Алгоритм вычисляет оптимальное расписание для всех работ рекурсивно.

Псевдокод

Приведенный ниже алгоритм вычисляет оптимальную последовательность работ [math]\pi[/math] для множества работ [math]I = \{i_1, i_2,\ldots, i_r\}[/math] в начальный момент времени [math]t[/math].

 function sequence(t: int, I: int[]): int[]
   if [math]I = \varnothing[/math]
     return [math]\varnothing[/math]
   find [math]i_k : p_{i_k} = \max\{p_i \mid i \in I\}[/math]
   [math]f^* = \infty[/math]
   for [math]j = k[/math] to [math]r[/math]
     [math]I_1 = \{i_v \mid 1 \leqslant v  \leqslant j \wedge  v \ne k\}[/math]
     [math]t_1 = t [/math]
     [math]\pi_1 = sequence (t_1 , I_1 )[/math]
     [math]I_2 = \{i_v \mid j \lt   v  \leqslant r\}[/math]
     [math]t_2 = t + \sum\limits_{v=1}^j p_{i_v}[/math] 
     [math]\pi_2 = sequence(t_2 , I_2 )[/math]
     [math]\pi = \pi_1  \cup  \{i_k\}  \cup \pi2[/math]
     if [math]f(\pi, t) \lt  f^*[/math]
       [math]\pi^* = \pi [/math]
       [math]f^* = f(\pi, t)[/math]
   return [math]\pi^*[/math]

Доказательство корректности алгоритма

Лемма:

Пусть [math] \pi -[/math] любая оптимальная последовательность работ для данных дедлайнов [math]d_1, d_2,\ldots, d_n[/math], [math]C_j -[/math] время завершения выполнения [math]j[/math]-ой работы. Рассмотрим [math]d'_j[/math] такие, что [math]\min\{d_j, C_j\} \leqslant d'_j \leqslant \max\{d_j, C_j\}. [/math]Тогда любая оптимальная последовательность работ для [math] d_j[/math] будет оптимальна и для [math]d'_j[/math]

Доказательство:

[math]\triangleright[/math]

[math]T( \pi) = T′(\pi) + \sum\limits_{i=1}^n A_j[/math], [math]T( \pi′) = T ′(\pi′) + \sum\limits_{i=1}^n B_j[/math], где, если [math]C_j[/math] [math]\leqslant d_j[/math], то [math]C_j = \min\{d_j, C_j\} \leqslant d'_j \leqslant \max\{d_j, C_j\} = d_j [/math], из чего следует [math] w_j\max\{0, C_j ~$-$~ d_j\} = w_j\max\{0, C_j ~$-$~ d'_j\} = 0. [/math] [math]C_j \leqslant d'_j \leqslant d_j [/math], и, учитывая [math]C'_j \leqslant d'_j, \enskip d'_j \leqslant C'_j \leqslant d_j[/math] и [math]d_j \leqslant C'_j,[/math] получаем, что [math]w_j \max\{0, C'_j ~$-$~ d_j\} = w_j\max\{0, C'_j ~$-$~ d'_j\} - w_j \max\{0, \min\{C'_j, d'_j\} ~$-$~ d_j\} [/math]. [math]A_j = 0[/math], [math]B_j = w_j \max\{0, \min\{C'_j, d_j \} ~$-$~d'_j\} [/math], если [math]C_j \geqslant d_j[/math], то [math]d_j = \min\{d_j, C_j\} \leqslant d'_j \leqslant \max\{d_j, C_j\} = C_j [/math], из чего следует [math] w_j\max\{0, C_j ~$-$~ d_j\} = w_j\max\{0, C_j ~$-$~ d'_j\} + w_j(d'_j ~$-$~ d_j). [/math] [math]d_j \leqslant d'_j \leqslant C_j[/math] , получаем, что [math]w_j \max\{0, C'_j ~$-$~ d_j\} = w_j\max\{0, C'_j ~$-$~ d'_j\} + w_j \max\{0, \min\{C'_j, d'_j\} ~$-$~ d_j\} [/math]. [math]A_j = w_j(d'_j, d_j), [/math] [math]B_j = -w_j \max\{0, \min\{C'_j, d'_j\}~$-$~d'_j\}[/math]. [math]A_j \geqslant B_j[/math] при любом j, значит [math]\sum\limits_{i=1}^n A_j \geqslant \sum\limits_{i=1}^n B_j[/math]. Кроме того, [math]T(\pi) \geqslant T(\pi')[/math], так как [math]\pi'[/math] минимизирует [math]T'[/math]. [math]T(\pi) \geqslant T(\pi')[/math] и [math]\pi'[/math] оптимально для [math]d_i[/math].

[math]\triangleleft[/math]

Лемма:

Пусть веса работ согласованы (из [math]p_i \lt p_j[/math] следует [math]w_i \geqslant w_j[/math]). Тогда существует оптимальная последовательность [math] \pi [/math], в которой работа [math]i[/math] предшествует работе [math]j[/math], если [math] d_i \leqslant d_j[/math] и [math] p_i \lt p_j[/math], и все работы, выполненные до дедлайна, упорядочены в неубывающем порядке [math]d_i[/math].

Доказательство:

[math]\triangleright[/math]

Пусть [math]\pi -[/math] оптимальная последовательность. Если работа [math]i[/math] идет после работы [math]j[/math] в [math] \pi[/math], то [math]d_i \leqslant d_j, p_i \lt p_j[/math]. Веса работ согласованы, поэтому [math]w_j \leqslant w_i [/math], и [math]w_j\max\{0,T ~$-$~ d_j\} \leqslant w_i\max\{0,T ~$-$~ d_i\}[/math] выполняется для всех Т. Таким образом, если поместить работу [math]j[/math] сразу после [math]i[/math], расписание останется оптимальным. Кроме того, если работа [math]i[/math] следует за работой [math]j[/math], где [math] d_i \leqslant d_j [/math] и [math]i, j[/math] выполнены до дедлайна, тогда, после перемещения [math]j[/math] на позицию сразу после [math]i[/math], работа [math]j[/math] все еще будет выполнена до дедлайна. Таким образом, общее значение минимизируемой функции не возрастет. Будем повторять перестановки, пока оптимальное расписание не будет удовлетворять условиям леммы.

[math]\triangleleft[/math]

Теорема:

Пусть работы [math]j_1, j_2,\ldots, j_n[/math] отстортированы в порядке неубывания дедлайнов, и веса согласованы. Обозначим за [math]k[/math] работу с наибольшим [math]p_i[/math]. Тогда существует работа [math]j^* \geqslant k[/math] такая, что в оптимальном расписании все работы [math]v = 1,\ldots, j^*, v \ne k[/math] размещены до [math]k[/math], а оставшиеся работы размещены после [math]k[/math].

Доказательство:

[math]\triangleright[/math]

Обозначим за [math]C'_k[/math] максимально возможное время завершения работы [math]k[/math] в любой последовательности, которая оптимальна в соответствии с [math]d_1, d_2,\ldots, d_n[/math]. Обозначим за [math]\pi[/math] оптимальную последовательность, соответствующую [math]d_1, d_2,\ldots, d_k ~$-$~ 1, d'_k = \max\{C'_k, d_k\}, d_k+1,\ldots, d_n[/math] и удовлетворяющую условиям Леммы 2. Обозначим за [math]C_k[/math] время завершения работы [math]k[/math] из [math]\pi[/math]. Согласно Лемме 1, последовательность [math]\pi[/math] оптимальна для исходных [math]d_1, d_2,\ldots, d_n[/math]. Тогда по определению [math]C'_k[/math]: [math]C_k \leqslant C'_k \leqslant \max\{C'_k, d_k\}, \enskip d'_k = \max\{C'_k, d_k\}, \enskip C_k \leqslant C'_k \leqslant d'_k[/math]. Таким образом, работе [math]k[/math] не может предшествовать работа [math]j[/math] такая, что [math]d_j[/math] > [math]d'_k[/math]. Иначе работа j тоже была бы выполнена вовремя, что противоречит условиям Леммы 2. С другой стороны, работе [math]k[/math] должны предшествовать все работы [math]j \ne k[/math] такие, что [math]d_j \leqslant d'_k[/math], так как [math]p_j \gt p_k[/math]. Если мы выберем в качеству работы [math]j^*[/math] самую большую работу такую, что [math]d_j ^* \leqslant d'_k,\enskip d'_k = \max\{C'_k, d_k\}[/math], тогда [math]j ^* \geqslant k[/math], так как [math]d_j ^* \leqslant d'_k[/math] и [math]j^*[/math] обладает необходимыми свойствами.

[math]\triangleleft[/math]

Время работы

Пускай все времена выполнения работ различны. Тогда все множества работ, используемые в качестве аргументов рекурсивного вызова функции можно представить в виде [math]\langle i, j, k \rangle : \{ v \mid i \leqslant v \leqslant j \wedge p_v \lt p_k\}[/math].
У нас максимум [math] p = \sum\limits_{i=1}^n p_i[/math] различных значений [math]t[/math]. Значит, нам нужно вызвать [math]sequence(t,I) \enskip \mathcal{O}(n^3p)[/math] раз. Более того, для фиксированного [math]k[/math] все значения [math]\max\{p_v \mid v \in I_{ijk}\}[/math] для [math]i, j = 1,\ldots, n,[/math] [math]i \lt j[/math] могут быть сосчитаны за [math]\mathcal{O}(n^2)[/math].
Таким образом, мы получаем алгоритм, работающий за [math]\mathcal{O}(n^3p)[/math] или [math]\mathcal{O}(n^4p_{max})[/math], где [math]p_{max} = \max\limits_{i=1}^n p_i[/math].

См. также

• Классификация задач
• [math]1 \mid\mid \sum w_i U_i[/math]

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

• P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 95 - 98