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] задача разбивается на две подзадачи.

Алгоритм вычисляет оптимальное расписание для всех работ рекурсивно.

Псевдокод

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

 function [math]\mathrm{sequence}[/math] ([math]t[/math]: int, [math]I[/math]: 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 = \mathrm{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 = \mathrm{sequence}(t_2 , I_2 )[/math]
     [math]\pi = \pi_1  \cup  \{i_k\}  \cup \pi_2[/math]
     if [math]f(\pi, t) \lt  f^*[/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]\pi'[/math] оптимальную для [math]d'_j[/math]. Тогда [math]C'_j [/math] — время завершения работы [math]j[/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]. Рассмотрим 2 случая: [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, d'_j 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] и удовлетворяющую условиям леммы. Обозначим за [math]C_k[/math] время завершения работы [math]k[/math] из [math]\pi[/math]. Согласно лемме, последовательность [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\},[/math] [math] d'_k = \max\{C'_k, d_k\},[/math] [math]C_k \leqslant C'_k \leqslant d'_k[/math]. Таким образом, работе [math]k[/math] не может предшествовать работа [math]j[/math] такая, что [math]d_j[/math] > [math]d'_k[/math]. Иначе работа j тоже была бы выполнена вовремя, что противоречит условиям леммы. С другой стороны, работе [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,[/math] [math]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] i, j, k \in \{1, 2, \ldots, n\}[/math].

У нас максимум [math] p = \sum\limits_{i=1}^n p_i[/math] различных значений [math]t[/math]. Значит, мы вызовем [math] \mathrm{sequence(t,I)}[/math] в худшем случае [math]\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