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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Описание алгоритма)
(Псевдокод)
Строка 17: Строка 17:
 
Приведенный ниже алгоритм вычисляет оптимальную последовательность работ <tex>\pi</tex> для множества работ <tex>I = \{i_1, i_2,\ldots, i_r\}</tex> в начальный момент времени <tex>t</tex>.
 
Приведенный ниже алгоритм вычисляет оптимальную последовательность работ <tex>\pi</tex> для множества работ <tex>I = \{i_1, i_2,\ldots, i_r\}</tex> в начальный момент времени <tex>t</tex>.
 
    
 
    
   '''function''' sequence(t: '''int''', I: '''int[]'''): '''int[]'''
+
   '''function''' <tex>\mathrm{sequence} </tex>(t: '''int''', I: '''int[]'''): '''int[]'''  
 
     '''if''' <tex>I = \varnothing</tex>
 
     '''if''' <tex>I = \varnothing</tex>
 
       '''return''' <tex>\varnothing</tex>
 
       '''return''' <tex>\varnothing</tex>
Строка 25: Строка 25:
 
       <tex>I_1 = \{i_v \mid 1 \leqslant v  \leqslant j \wedge  v \ne k\}</tex>
 
       <tex>I_1 = \{i_v \mid 1 \leqslant v  \leqslant j \wedge  v \ne k\}</tex>
 
       <tex>t_1 = t </tex>
 
       <tex>t_1 = t </tex>
       <tex>\pi_1 = sequence (t_1 , I_1 )</tex>
+
       <tex>\pi_1 = \mathrm{sequence} (t_1 , I_1 )</tex>
 
       <tex>I_2 = \{i_v \mid j <  v  \leqslant r\}</tex>
 
       <tex>I_2 = \{i_v \mid j <  v  \leqslant r\}</tex>
 
       <tex>t_2 = t + \sum\limits_{v=1}^j p_{i_v}</tex>  
 
       <tex>t_2 = t + \sum\limits_{v=1}^j p_{i_v}</tex>  
       <tex>\pi_2 = sequence(t_2 , I_2 )</tex>
+
       <tex>\pi_2 = \mathrm{sequence}(t_2 , I_2 )</tex>
       <tex>\pi = \pi_1  \cup  \{i_k\}  \cup \pi2</tex>
+
       <tex>\pi = \pi_1  \cup  \{i_k\}  \cup \pi_2</tex>
 
       '''if''' <tex>f(\pi, t) < f^*</tex>
 
       '''if''' <tex>f(\pi, t) < f^*</tex>
        <tex>\pi^* = \pi </tex>
 
 
         <tex>f^* = f(\pi, t)</tex>
 
         <tex>f^* = f(\pi, t)</tex>
     '''return''' <tex>\pi^*</tex>
+
     '''return''' <tex>\pi</tex>
  
 
===Доказательство корректности алгоритма===
 
===Доказательство корректности алгоритма===

Версия 20:39, 7 июня 2016

[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](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 = \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],
где,

  • если [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].

См. также

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

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