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

Материал из Викиконспекты
Перейти к: навигация, поиск
(*Новый конспект*)
 
м (rollbackEdits.php mass rollback)
 
(не показано 10 промежуточных версий 3 участников)
Строка 1: Строка 1:
 
<tex dpi = "200" >1 \mid\mid \sum w_i T_i</tex>
 
<tex dpi = "200" >1 \mid\mid \sum w_i T_i</tex>
 
{{Определение
 
|definition =
 
'''Опоздание''' (англ. ''Tardiness'', ''<tex>T_{j}</tex>'') <tex>T_j = \max\{0, C_j - d_j\}</tex>}}
 
  
 
{{Задача
 
{{Задача
Строка 12: Строка 8:
 
==Псевдополиномиальное решение==
 
==Псевдополиномиальное решение==
  
 +
===Описание алгоритма===
 +
Упорядочим работы в порядке неубывания дедлайнов. Обозначим за <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> задача разбивается на две подзадачи.
  
===Описание алгоритма===
 
Будем делить имеющиеся у нас работы на множества <tex> I_1, I_2</tex> так, чтобы для любого <tex>j \geqslant k</tex> работы из <tex>I_1 = \{1,..., j\}\setminus\{k\}</tex> были расположены до <tex>k</tex>, а работы из <tex>I_2 = \{j+1,..., n\}</tex> были расположены после <tex>k</tex>. Оптимальное время начала выполнения всех работ из <tex> I_1 \enskip t_1 = 0</tex>, из  <tex> I_2  \enskip t_2 = p = \sum\limits_{i=1}^j p_i</tex>. <br>
 
 
Алгоритм вычисляет оптимальное расписание для всех работ рекурсивно.
 
Алгоритм вычисляет оптимальное расписание для всех работ рекурсивно.
  
 
===Псевдокод===
 
===Псевдокод===
  
Приведенный ниже алгоритм вычисляет оптимальную последовательность работ <tex>\pi</tex>для множества работ <tex>I = \{i_1, i_2, ..., i_r\}</tex> в начальный момент времени <tex>t</tex>.
+
Приведенный ниже алгоритм вычисляет оптимальную последовательность работ <tex>\pi</tex> для множества работ <tex>I = \{i_1, i_2,\ldots, i_r\}</tex> в начальный момент времени <tex>t</tex>.
 
    
 
    
   '''function''' <tex> \mathrm{Sequence}(t, I)</tex>:
+
   '''function''' <tex>\mathrm{sequence}</tex>(<tex>t</tex>: '''int''', <tex>I</tex>: '''int[]'''): '''int[]'''
 
     '''if''' <tex>I = \varnothing</tex>
 
     '''if''' <tex>I = \varnothing</tex>
       <tex>\pi = \varnothing</tex>
+
       '''return''' <tex>\varnothing</tex>
     '''else'''
+
     find <tex>i_k : p_{i_k} = \max\{p_i \mid i \in I\}</tex>
      find <tex>i_k : p_{i_k} = \max\{p_i \mid i \in I\}</tex>
+
    <tex>f^* = \infty</tex>
      <tex>f^* = \inf</tex>
+
    '''for''' <tex>j = k</tex> '''to''' <tex>r</tex>
      '''for''' <tex>j = k</tex> '''to''' <tex>r</tex>
+
      <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; v \ne k\};</tex>
+
      <tex>t_1 = t </tex>
        <tex>t_1 := t; </tex>
+
      <tex>\pi_1 = \mathrm{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 = \mathrm{sequence}(t_2 , I_2 )</tex>
        <tex>\pi_2 := \mathrm{Sequence}(t_2 , I_2 );</tex>
+
      <tex>\pi = \pi_1 \cup  \{i_k\\cup \pi_2</tex>
        <tex>\pi:=\pi_1 \circ i_k \circ \pi2;</tex>
+
      '''if''' <tex>f(\pi, t) < f^*</tex>
        вычисляем значение <tex>f(\pi, t)</tex>
+
        <tex>f^* = f(\pi, t)</tex>
        '''if''' <tex>f(\pi, t) < f^*</tex>
+
     '''return''' <tex>\pi</tex>
          <tex>\pi^* := \pi; </tex>
 
          <tex>f^* := f(\pi, t)</tex>
 
     '''return''' <tex>\pi^*</tex>
 
  
 
===Доказательство корректности алгоритма===
 
===Доказательство корректности алгоритма===
  
{{Лемма
+
{{Лемма|id=l1
 
|statement=
 
|statement=
Пусть <tex> \pi </tex> - любая оптимальная последовательность работ для данных дедлайнов <tex>d_1, d_2, ... , 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′) + <tex> \sum\limits_{i=1}^n B_j</tex>, <br>
+
 
где, если <tex>C_j</tex> <tex>\leqslant</tex> <tex>d_j</tex>, то <br>
+
<tex>T( \pi) = T′(\pi) + \sum\limits_{i=1}^n A_j </tex>,  
<tex>A_j = 0</tex>, <br>
+
 
<tex>B_j = w_j \max\{0, \min\{C'_j, d_j \} - d'_j\} </tex>, <br>
+
<tex>T( \pi′) = T ′(\pi′) + \sum\limits_{i=1}^n B_j </tex>.
если <tex>C_j \geqslant d_j</tex>, то <br>
+
 
<tex>A_j = w_j(d'_j, d_j), </tex><br>
+
Рассмотрим 2 случая:
<tex>B_j = -w_j \max\{0, \min\{C'_j, d'_j\} - d'_j\}</tex>. <br>
+
 
Если <tex> C_j \leqslant d_j, 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</tex> <tex>\leqslant d_j</tex>.
Если <tex> C_j \geqslant d_j, 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>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</tex>, тогда <tex>C_j \leqslant d'_j  \leqslant d_j  </tex>, и, учитывая <tex>C'_j \leqslant d'_j, d'_j \leqslant C'_j \leqslant d_j и 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> d_j \leqslant C_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>. <br>
+
#:<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 \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 = 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>.
  
 
}}
 
}}
  
  
{{Лемма
+
{{Лемма|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 </tex>< <tex>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>.
  
  
 
|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> все еще будет выполнена до дедлайна. Таким образом, общее значение минимизируемой функции не возрастет.
 
Будем повторять перестановки, пока оптимальное расписание не будет удовлетворять условиям леммы.
 
Будем повторять перестановки, пока оптимальное расписание не будет удовлетворять условиям леммы.
 
  
 
}}
 
}}
  
 
{{Теорема
 
{{Теорема
|statement= Пусть работы <tex>j_1, j_2, ..., j_n</tex> отстортированы в порядке неубывания дедлайнов, и веса согласованы. Обозначим за <tex>k</tex> работу с наибольшим <tex>p_i</tex>.
+
|statement= Пусть работы <tex>j_1, j_2,\ldots, j_n</tex> отстортированы в порядке неубывания дедлайнов, и веса согласованы. Обозначим за <tex>k</tex> работу с наибольшим <tex>p_i</tex>.
Тогда существует работа <tex>j^* \geqslant k</tex> такая, что в оптимальном расписании все работы <tex>v = 1, ..., j^*, v \ne k</tex> размещены до <tex>k</tex>, а оставшиеся работы размещены после <tex>k</tex>.
+
Тогда существует работа <tex>j^* \geqslant k</tex> такая, что в оптимальном расписании все работы <tex>v = 1,\ldots, j^*, v \ne k</tex> размещены до <tex>k</tex>, а оставшиеся работы размещены после <tex>k</tex>.
  
 
|proof=
 
|proof=
Обозначим за <tex>C'_k</tex> максимально возможное время завершения работы <tex>k</tex> в любой последовательности, которая оптимальна в соответствии с <tex>d_1, d_2, ..., d_n</tex>. Обозначим за <tex>\pi</tex> оптимальную последовательность, соответствующую <tex>d_1, d_2, ..., d_k-1, d'_k = \max\{C'_k, d_k\}, d_k+1, ..., 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, ..., d_n</tex>. Тогда по определению <tex>C'_k</tex>: <tex>C_k \leqslant  C'_k \leqslant \max\{C'_k, d_k\} = 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</tex> >  <tex>p_k</tex>. Если мы выберем в качеству работы <tex>j^*</tex> самую большую работу такую, что <tex>d_j ^* \leqslant 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>i, j, k := \{ v \mid i \leqslant v \leqslant j; p_v</tex> < <tex>p_k\}</tex>, то есть могут быть полностью заданы тройкой чисел <tex>\langle i, j, k \rangle</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>\mathrm{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,..., n,</tex>  <tex>i</tex> < <tex>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