1sumwT

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

Определение:

Опоздание (англ. Tardiness, [math]T_{j}[/math]) [math]T_j = \max\{0, C_j - d_j\}[/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] I_1, I_2[/math] так, чтобы для любого [math]j \geqslant k[/math] работы из [math]I_1 = \{1,..., j\}\setminus\{k\}[/math] были расположены до [math]k[/math], а работы из [math]I_2 = \{j+1,..., n\}[/math] были расположены после [math]k[/math]. Оптимальное время начала выполнения всех работ из [math] I_1 \enskip t_1 = 0[/math], из [math] I_2 \enskip t_2 = p = \sum\limits_{i=1}^j p_i[/math].
Алгоритм вычисляет оптимальное расписание для всех работ рекурсивно.

Псевдокод

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

 function [math] \mathrm{Sequence}(t, I)[/math]:
   if [math]I = \varnothing[/math]
     [math]\pi = \varnothing[/math]
   else
     find [math]i_k : p_{i_k} = \max\{p_i \mid i \in I\}[/math]
     [math]f^* = \inf[/math]
     for [math]j = k[/math] to [math]r[/math]
       [math]I_1 := \{i_v \mid 1 \leqslant v  \leqslant j; 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 \circ i_k \circ \pi2;[/math]
       вычисляем значение [math]f(\pi, t)[/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, ... , 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′) + \lt tex\gt \sum\limits_{i=1}^n B_j[/math], где, если [math]C_j[/math] [math]\leqslant[/math] [math]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]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] C_j \leqslant d_j, 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 \geqslant d_j, 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] C_j \leqslant d_j[/math], тогда [math]C_j \leqslant d'_j \leqslant d_j [/math], и, учитывая [math]C'_j \leqslant d'_j, d'_j \leqslant C'_j \leqslant d_j и 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] d_j \leqslant C_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 \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 [/math]< [math]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, ..., j_n[/math] отстортированы в порядке неубывания дедлайнов, и веса согласованы. Обозначим за [math]k[/math] работу с наибольшим [math]p_i[/math]. Тогда существует работа [math]j^* \geqslant k[/math] такая, что в оптимальном расписании все работы [math]v = 1, ..., 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, ..., d_n[/math]. Обозначим за [math]\pi[/math] оптимальную последовательность, соответствующую [math]d_1, d_2, ..., d_k-1, d'_k = \max\{C'_k, d_k\}, d_k+1, ..., d_n[/math] и удовлетворяющую условиям Леммы 2. Обозначим за [math]C_k[/math] время завершения работы [math]k[/math] из [math]\pi[/math]. Согласно Лемме 1, последовательность [math]\pi[/math] оптимальна для исходных [math]d_1, d_2, ..., d_n[/math]. Тогда по определению [math]C'_k[/math]: [math]C_k \leqslant C'_k \leqslant \max\{C'_k, d_k\} = 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[/math] > [math]p_k[/math]. Если мы выберем в качеству работы [math]j^*[/math] самую большую работу такую, что [math]d_j ^* \leqslant 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]i, j, k := \{ v \mid i \leqslant v \leqslant j; p_v[/math] < [math]p_k\}[/math], то есть могут быть полностью заданы тройкой чисел [math]\langle i, j, k \rangle[/math].
У нас максимум [math] p = \sum\limits_{i=1}^n p_i[/math] различных значений [math]t[/math]. Значит, нам нужно вызвать [math]\mathrm{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,..., n,[/math] [math]i[/math] < [math]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