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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 9 промежуточных версий 3 участников)
Строка 9: Строка 9:
  
 
===Описание алгоритма===
 
===Описание алгоритма===
Упорядочим работы в порядке неубывания дедлайнов. Обозначим за <tex>k</tex> работу с максимальным <tex>p_i</tex>. <br>
+
Упорядочим работы в порядке неубывания дедлайнов. Обозначим за <tex>k</tex> работу с максимальным <tex>p_i</tex>.  
Будем делить имеющиеся у нас работы на множества <tex> I_1, I_2</tex> так, чтобы для любого <tex>j \geqslant k</tex> <tex>I_1 = \{1,\ldots, j\}\setminus\{k\}</tex>, <tex>I_2 = \{j+1,\ldots, n\}</tex>. Тогда в оптимальном расписании все работы из <tex>I_1</tex> окажутся до <tex>k</tex>, а работы из <tex>I_2</tex> будут расположены после <tex>k</tex>. Для работ из <tex> I_1</tex> оптимальное время начала выполнения <tex>t_1 = 0</tex>, для работ из <tex>I_2</tex> оптимальное начало <tex>t_2 = p = \sum\limits_{i=1}^j p_i</tex>. Таким образом, для любой <tex>j</tex> задача разбивается на 2 подзадачи. <br>
+
 
 +
Будем делить имеющиеся у нас работы на множества <tex> I_1, I_2</tex> так, чтобы для любого <tex>j \geqslant k</tex> <tex>I_1 = \{1,\ldots, j\}\setminus\{k\}</tex>, <tex>I_2 = \{j+1,\ldots, n\}</tex>. Тогда в оптимальном расписании все работы из <tex>I_1</tex> окажутся до <tex>k</tex>, а работы из <tex>I_2</tex> будут расположены после <tex>k</tex>. Для работ из <tex> I_1</tex> оптимальное время начала выполнения <tex>t_1 = 0</tex>, для работ из <tex>I_2</tex> оптимальное начало <tex>t_2 = p = \sum\limits_{i=1}^j p_i</tex>. Таким образом, для любой <tex>j</tex> задача разбивается на две подзадачи.  
 +
 
 
Алгоритм вычисляет оптимальное расписание для всех работ рекурсивно.
 
Алгоритм вычисляет оптимальное расписание для всех работ рекурсивно.
  
Строка 17: Строка 19:
 
Приведенный ниже алгоритм вычисляет оптимальную последовательность работ <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>(<tex>t</tex>: '''int''', <tex>I</tex>: '''int[]'''): '''int[]'''  
 
     '''if''' <tex>I = \varnothing</tex>
 
     '''if''' <tex>I = \varnothing</tex>
 
       '''return''' <tex>\varnothing</tex>
 
       '''return''' <tex>\varnothing</tex>
Строка 25: Строка 27:
 
       <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>
  
 
===Доказательство корректности алгоритма===
 
===Доказательство корректности алгоритма===
  
{{Лемма
+
{{Лемма|id=l1
 
|statement=
 
|statement=
Пусть <tex> \pi -</tex> любая оптимальная последовательность работ для данных дедлайнов <tex>d_1, d_2,\ldots, d_n</tex>, <tex>C_j -</tex>  время завершения выполнения <tex>j</tex>-ой работы.  
+
Пусть <tex> \pi</tex> {{---}} любая оптимальная последовательность работ для данных дедлайнов <tex>d_1, d_2,\ldots, d_n</tex>, <tex>C_j</tex> {{---}} время завершения выполнения <tex>j</tex>-ой работы.  
Рассмотрим <tex>d'_j</tex> такие, что <tex>\min\{d_j, C_j\}  \leqslant d'_j  \leqslant \max\{d_j, C_j\}. </tex>Тогда любая оптимальная последовательность работ для <tex> d_j</tex> будет оптимальна и для <tex>d'_j</tex>
+
 
 +
Рассмотрим <tex>d'_j</tex> такие, что <tex>\min\{d_j, C_j\}  \leqslant d'_j  \leqslant \max\{d_j, C_j\}. </tex>Тогда любая оптимальная последовательность работ для <tex> d_j</tex> будет оптимальна и для <tex>d'_j</tex>.
  
 
|proof=
 
|proof=
<tex>T( \pi) = T′(\pi) + \sum\limits_{i=1}^n A_j</tex>, <br>
+
Рассмотрим последовательность <tex>\pi'</tex> оптимальную для <tex>d'_j</tex>. Тогда <tex>C'_j </tex> {{---}} время завершения работы <tex>j</tex> в данной последовательности.
<tex>T( \pi′) = T ′(\pi′) + \sum\limits_{i=1}^n B_j</tex>, <br>
 
где, <br>
 
  
* если <tex>C_j</tex> <tex>\leqslant d_j</tex>, то <br>
+
<tex>T( \pi) = T′(\pi) + \sum\limits_{i=1}^n A_j </tex>,  
<tex>C_j = \min\{d_j, C_j\}  \leqslant d'_j  \leqslant \max\{d_j, C_j\} = d_j </tex>, из чего следует <tex> w_j\max\{0, C_j ~$-$~ d_j\} = w_j\max\{0, C_j ~$-$~ d'_j\} = 0. </tex>  <br>
 
<tex>C_j  \leqslant d'_j  \leqslant d_j  </tex>, и, учитывая <tex>C'_j \leqslant d'_j, \enskip d'_j \leqslant C'_j \leqslant d_j</tex> и <tex>d_j \leqslant C'_j,</tex> получаем, что <tex>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\} </tex>. <br>
 
<tex>A_j = 0</tex>, <br>
 
<tex>B_j = w_j \max\{0, \min\{C'_j, d_j \} ~$-$~d'_j\} </tex>, <br>
 
  
* если <tex>C_j \geqslant d_j</tex>, то <br>
+
<tex>T( \pi′) = T ′(\pi′) + \sum\limits_{i=1}^n B_j </tex>.
<tex>d_j = \min\{d_j, C_j\}  \leqslant d'_j  \leqslant \max\{d_j, C_j\} = C_j </tex>, из чего следует <tex> w_j\max\{0, C_j ~$-$~ d_j\} = w_j\max\{0, C_j ~$-$~ d'_j\} + w_j(d'_j ~$-$~ d_j). </tex>  <br>
+
 
<tex>d_j  \leqslant d'_j  \leqslant C_j</tex> , получаем, что <tex>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\} </tex>. <br>
+
Рассмотрим 2 случая:
<tex>A_j = w_j(d'_j, d_j), </tex><br>
+
 
<tex>B_j = -w_j \max\{0, \min\{C'_j, d'_j\}~$-$~d'_j\}</tex>. <br>
+
# <tex>C_j</tex> <tex>\leqslant d_j</tex>.
 +
#:Тогда <tex>C_j = \min\{d_j, C_j\}  \leqslant d'_j  \leqslant \max\{d_j, C_j\} = d_j </tex>, из чего следует <tex> w_j\max\{0, C_j ~$-$~ d_j\} = w_j\max\{0, C_j ~$-$~ d'_j\} = 0.</tex>
 +
#:<tex>C_j \leqslant d'_j  \leqslant d_j  </tex>, и, учитывая <tex>C'_j \leqslant d'_j,  d'_j  C'_j \leqslant d_j</tex> и <tex>d_j \leqslant C'_j,</tex> получаем, что <tex>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\}  </tex>.
 +
#:<tex>A_j = 0  </tex>,  
 +
#:<tex>B_j = w_j \max\{0, \min\{C'_j, d_j \} ~$-$~d'_j\} </tex>;
 +
# <tex>C_j \geqslant d_j</tex>
 +
#:Тогда <tex>d_j = \min\{d_j, C_j\}  \leqslant d'_j  \leqslant \max\{d_j, C_j\} = C_j </tex>, из чего следует <tex> w_j\max\{0, C_j ~$-$~ d_j\} = w_j\max\{0, C_j ~$-$~ d'_j\} + w_j(d'_j ~$-$~ d_j). </tex>   
 +
#:<tex>d_j  \leqslant d'_j  \leqslant C_j</tex> , получаем, что <tex>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\} </tex>.  
 +
#:<tex>A_j = w_j(d'_j, d_j), </tex>
 +
#:<tex>B_j = -w_j \max\{0, \min\{C'_j, d'_j\}~$-$~d'_j\}</tex>.  
  
 
<tex>A_j \geqslant B_j</tex> при любом j, значит <tex>\sum\limits_{i=1}^n A_j  \geqslant \sum\limits_{i=1}^n B_j</tex>. Кроме того, <tex>T(\pi) \geqslant T(\pi')</tex>, так как <tex>\pi'</tex> минимизирует <tex>T'</tex>. <tex>T(\pi) \geqslant T(\pi')</tex> и <tex>\pi'</tex> оптимально для <tex>d_i</tex>.
 
<tex>A_j \geqslant B_j</tex> при любом j, значит <tex>\sum\limits_{i=1}^n A_j  \geqslant \sum\limits_{i=1}^n B_j</tex>. Кроме того, <tex>T(\pi) \geqslant T(\pi')</tex>, так как <tex>\pi'</tex> минимизирует <tex>T'</tex>. <tex>T(\pi) \geqslant T(\pi')</tex> и <tex>\pi'</tex> оптимально для <tex>d_i</tex>.
Строка 64: Строка 69:
  
  
{{Лемма
+
{{Лемма|id=l2
 
|statement=
 
|statement=
 
Пусть веса работ  согласованы (из <tex>p_i < p_j</tex> следует <tex>w_i  \geqslant w_j</tex>). Тогда существует оптимальная последовательность <tex> \pi </tex>, в которой работа <tex>i</tex> предшествует работе <tex>j</tex>, если <tex> d_i  \leqslant  d_j</tex> и <tex> p_i  < p_j</tex>, и все работы, выполненные до дедлайна, упорядочены в неубывающем порядке <tex>d_i</tex>.
 
Пусть веса работ  согласованы (из <tex>p_i < p_j</tex> следует <tex>w_i  \geqslant w_j</tex>). Тогда существует оптимальная последовательность <tex> \pi </tex>, в которой работа <tex>i</tex> предшествует работе <tex>j</tex>, если <tex> d_i  \leqslant  d_j</tex> и <tex> p_i  < p_j</tex>, и все работы, выполненные до дедлайна, упорядочены в неубывающем порядке <tex>d_i</tex>.
Строка 70: Строка 75:
  
 
|proof=
 
|proof=
Пусть <tex>\pi -</tex> оптимальная последовательность.  Если работа <tex>i</tex> идет после работы <tex>j</tex> в <tex> \pi</tex>, то <tex>d_i  \leqslant d_j, p_i < p_j</tex>. Веса работ согласованы, поэтому <tex>w_j \leqslant w_i </tex>, и <tex>w_j\max\{0,T ~$-$~ d_j\} \leqslant w_i\max\{0,T ~$-$~ d_i\}</tex> выполняется для всех Т. Таким образом, если поместить работу <tex>j</tex> сразу после <tex>i</tex>, расписание останется оптимальным. <br>
+
Пусть <tex>\pi </tex> {{---}} оптимальная последовательность.  Если работа <tex>i</tex> идет после работы <tex>j</tex> в <tex> \pi</tex>, то <tex>d_i  \leqslant d_j, p_i < p_j</tex>. Веса работ согласованы, поэтому <tex>w_j \leqslant w_i </tex>, и <tex>w_j\max\{0,T ~$-$~ d_j\} \leqslant w_i\max\{0,T ~$-$~ d_i\}</tex> выполняется для всех Т. Таким образом, если поместить работу <tex>j</tex> сразу после <tex>i</tex>, расписание останется оптимальным.  
 +
 
 
Кроме того, если работа <tex>i</tex> следует за работой <tex>j</tex>, где  <tex> d_i  \leqslant d_j </tex> и <tex>i, j</tex> выполнены до дедлайна, тогда, после перемещения <tex>j</tex> на позицию сразу после <tex>i</tex>, работа  <tex>j</tex> все еще будет выполнена до дедлайна. Таким образом, общее значение минимизируемой функции не возрастет.
 
Кроме того, если работа <tex>i</tex> следует за работой <tex>j</tex>, где  <tex> d_i  \leqslant d_j </tex> и <tex>i, j</tex> выполнены до дедлайна, тогда, после перемещения <tex>j</tex> на позицию сразу после <tex>i</tex>, работа  <tex>j</tex> все еще будет выполнена до дедлайна. Таким образом, общее значение минимизируемой функции не возрастет.
 
Будем повторять перестановки, пока оптимальное расписание не будет удовлетворять условиям леммы.
 
Будем повторять перестановки, пока оптимальное расписание не будет удовлетворять условиям леммы.
Строка 81: Строка 87:
  
 
|proof=
 
|proof=
Обозначим за <tex>C'_k</tex> максимально возможное время завершения работы <tex>k</tex> в любой последовательности, которая оптимальна в соответствии с <tex>d_1, d_2,\ldots, d_n</tex>. Обозначим за <tex>\pi</tex> оптимальную последовательность, соответствующую <tex>d_1, d_2,\ldots, d_k ~$-$~ 1, d'_k = \max\{C'_k, d_k\}, d_k+1,\ldots, d_n</tex> и удовлетворяющую условиям Леммы 2. Обозначим за <tex>C_k</tex> время завершения работы <tex>k</tex> из <tex>\pi</tex>. <br>
+
Обозначим за <tex>C'_k</tex> максимально возможное время завершения работы <tex>k</tex> в любой последовательности, которая оптимальна в соответствии с <tex>d_1, d_2,\ldots, d_n</tex>. Обозначим за <tex>\pi</tex> оптимальную последовательность, соответствующую <tex>d_1, d_2,\ldots, d_k ~$-$~ 1, d'_k = \max\{C'_k, d_k\}, d_k+1,\ldots, d_n</tex> и удовлетворяющую условиям [[#l1 | леммы]]. Обозначим за <tex>C_k</tex> время завершения работы <tex>k</tex> из <tex>\pi</tex>.  
Согласно Лемме 1, последовательность <tex>\pi</tex> оптимальна для исходных <tex>d_1, d_2,\ldots, d_n</tex>. Тогда по определению <tex>C'_k</tex>: <tex>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</tex>. Таким образом, работе  <tex>k</tex> не может предшествовать работа <tex>j</tex> такая, что <tex>d_j</tex> > <tex>d'_k</tex>. Иначе работа j тоже была бы выполнена вовремя, что противоречит условиям Леммы 2. С другой стороны, работе <tex>k</tex> должны предшествовать все работы <tex>j \ne k</tex> такие, что <tex>d_j \leqslant d'_k</tex>, так как <tex>p_j > p_k</tex>. Если мы выберем в качеству работы <tex>j^*</tex> самую большую работу такую, что <tex>d_j ^* \leqslant d'_k,\enskip d'_k = \max\{C'_k, d_k\}</tex>, тогда <tex>j ^* \geqslant k</tex>, так как <tex>d_j ^* \leqslant d'_k</tex> и <tex>j^*</tex> обладает необходимыми свойствами.
+
 
 +
Согласно [[#l1 | лемме]], последовательность <tex>\pi</tex> оптимальна для исходных <tex>d_1, d_2,\ldots, d_n</tex>. Тогда по определению <tex>C'_k</tex>: <tex>C_k \leqslant  C'_k \leqslant \max\{C'_k, d_k\},</tex>  <tex> d'_k = \max\{C'_k, d_k\},</tex> <tex>C_k \leqslant  C'_k \leqslant d'_k</tex>. Таким образом, работе  <tex>k</tex> не может предшествовать работа <tex>j</tex> такая, что <tex>d_j</tex> > <tex>d'_k</tex>. Иначе работа j тоже была бы выполнена вовремя, что противоречит условиям [[#l2 | леммы]]. С другой стороны, работе <tex>k</tex> должны предшествовать все работы <tex>j \ne k</tex> такие, что <tex>d_j \leqslant d'_k</tex>, так как <tex>p_j > p_k</tex>. Если мы выберем в качеству работы <tex>j^*</tex> самую большую работу такую, что <tex>d_j ^* \leqslant d'_k,</tex> <tex>d'_k = \max\{C'_k, d_k\}</tex>, тогда <tex>j ^* \geqslant k</tex>, так как <tex>d_j ^* \leqslant d'_k</tex> и <tex>j^*</tex> обладает необходимыми свойствами.
  
 
}}
 
}}
  
 
===Время работы===
 
===Время работы===
Пускай все времена выполнения работ различны. Тогда все множества работ, используемые в качестве аргументов рекурсивного вызова функции можно представить в виде <tex>\langle i, j, k \rangle : \{ v \mid i \leqslant v \leqslant j \wedge  p_v < p_k\}</tex>. <br>
+
Пускай все времена выполнения работ различны. Тогда все множества работ, используемые в качестве аргументов рекурсивного вызова функции можно представить в виде <tex>\langle i, j, k \rangle : \{ v \mid i \leqslant v \leqslant j \wedge  p_v < p_k\}</tex>, <tex> i, j, k \in \{1, 2, \ldots, n\}</tex>.
У нас максимум <tex> p = \sum\limits_{i=1}^n p_i</tex> различных значений <tex>t</tex>. Значит, нам нужно вызвать <tex>sequence(t,I) \enskip \mathcal{O}(n^3p)</tex> раз. Более того, для фиксированного <tex>k</tex> все значения <tex>\max\{p_v \mid v \in I_{ijk}\}</tex> для  <tex>i, j = 1,\ldots, n,</tex>  <tex>i < j</tex> могут быть сосчитаны за <tex>\mathcal{O}(n^2)</tex>. <br>
+
 
 +
У нас максимум <tex> p = \sum\limits_{i=1}^n p_i</tex> различных значений <tex>t</tex>. Значит, мы вызовем <tex> \mathrm{sequence}(t,I)</tex> в худшем случае  <tex>\mathcal{O}(n^3p)</tex> раз. Более того, для фиксированного <tex>k</tex> все значения <tex>\max\{p_v \mid v \in I_{ijk}\}</tex> для  <tex>i, j = 1,\ldots, n,</tex>  <tex>i < j</tex> могут быть сосчитаны за <tex>\mathcal{O}(n^2)</tex>.  
 +
 
 
Таким образом, мы получаем алгоритм, работающий за <tex>\mathcal{O}(n^3p)</tex> или <tex>\mathcal{O}(n^4p_{max})</tex>, где <tex>p_{max} = \max\limits_{i=1}^n p_i</tex>.
 
Таким образом, мы получаем алгоритм, работающий за <tex>\mathcal{O}(n^3p)</tex> или <tex>\mathcal{O}(n^4p_{max})</tex>, где <tex>p_{max} = \max\limits_{i=1}^n p_i</tex>.
  

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

[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 случая:

  1. [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];
  2. [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].

См. также

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

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