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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство корректности алгоритма)
м (rollbackEdits.php mass rollback)
 
(не показаны 24 промежуточные версии 4 участников)
Строка 1: Строка 1:
<div style="background-color: #ABCDEF; font-size: 16px; font-weight: bold; color: #000000; text-align: center; padding: 4px; border-style: solid; border-width: 1px;">Эта статья находится в разработке!</div>
+
<tex dpi=200>F2 \mid\mid C_{max} </tex>
<includeonly>[[Категория: В разработке]]</includeonly>
+
{{Задача
 +
|definition=Рассмотрим задачу:
 +
*дано <tex>n</tex> работ и <tex>2</tex> станка,
 +
*для каждой работы известно её время выполнения на каждом станке <tex>p_{ij}</tex>,
 +
*каждую работу необходимо выполнить сначала на первом станке, а потом на втором.
 +
Требуется минимизировать время окончания выполнения всех работ. }}
  
== Постановка задачи ==
 
Рассмотрим задачу:
 
<ol>
 
<li>Дано <tex>n</tex> работ и <tex>2</tex> станка.</li>
 
<li>Для каждой работы известно её время выполнения на каждом станке.</li>
 
<li>Каждую работу необходимо выполнить сначала на первом станке, а потом на втором.</li>
 
</ol>
 
Требуется минимизировать время окончания всех работ.
 
  
 
== Описание алгоритма ==
 
== Описание алгоритма ==
 
Пусть <tex>p_{i1}</tex> {{---}} время выполнения <tex>i</tex>-ой работы на первом станке, а <tex>p_{i2}</tex> {{---}} на втором.<br/>
 
Пусть <tex>p_{i1}</tex> {{---}} время выполнения <tex>i</tex>-ой работы на первом станке, а <tex>p_{i2}</tex> {{---}} на втором.<br/>
 
<ol>
 
<ol>
<li>Будем в ходе нашего алгоритма строить два списка <tex> L </tex> и <tex>  R </tex>. Изначально оба списка пусты. И будем поддерживать множество еще не распределенных по спискам <tex> L </tex> и <tex>  R </tex> работ <tex>X = \{i \mid  i = 1, \dots, n\}</tex>  </li>
+
<li>Алгоритм строит два списка <tex> L </tex> и <tex>  R </tex>. Изначально они пусты. Также поддерживается множество еще не распределенных по спискам <tex> L </tex> и <tex>  R </tex> работ <tex>X = \{i \mid  i = 1, \dots, n\}</tex>  </li>
<li> Пока множество <tex> X </tex> непусто будем распределять работы по спискам следующим образом:
+
<li> Пока множество <tex> X </tex> не пусто, распределяем работы по спискам следующим образом:
 
<ul>
 
<ul>
<li> Находим такие индексы <tex> i </tex> и <tex> j </tex>, что  <tex>p_{ij} = \min \{ p_{ij}  \mid i \in X; j = 1, 2\}</tex> </li>
+
<li> находим такие индексы <tex> i </tex> и <tex> j </tex>, что  <tex>p_{ij} = \min \{ p_{ij}  \mid i \in X \land j = 1, 2\}</tex>, </li>
<li>Если минимум достигается на первом станке (иными словами <tex> j = 1 </tex>), то поставим работу <tex> i </tex> в конец  листа <tex> L </tex>, иначе ставим в начало листа <tex> R </tex>  </li>
+
<li>если минимум достигается на первом станке (иными словами <tex> j = 1 </tex>), то поставим работу <tex> i </tex> в конец  списка <tex> L </tex>, иначе ставим в начало списка <tex> R </tex>, </li>
<li>Удаляем работу <tex> i </tex> из множества <tex> X </tex> </li>
+
<li>удаляем работу <tex> i </tex> из множества <tex> X </tex>. </li>
 
</ul>
 
</ul>
 
</li>
 
</li>
<li> Рассмотрим лист <tex> T = L \circ R</tex>. Утверждается, что этот лист является оптимальной перестановкой работ как на первом, так и на втором станке. Далее расставляем подряд работы на первом станке согласно перестановке, после чего ставим в том же порядке работы на втором стане, при этом избегая одновременного выполнения одной и той же работы. </li>
+
<li> Рассмотрим список <tex> T = L ~\texttt{++}~ R</tex> {{---}} конкатенацию <tex> L</tex> и <tex>R</tex>. Утверждается, что этот список является оптимальной перестановкой работ как на первом, так и на втором станке. Далее расставляем подряд работы на первом станке согласно перестановке, после чего ставим в том же порядке работы на втором станке, при этом избегая одновременного выполнения одной и той же работы. </li>
  
 
</ol>
 
</ol>
Строка 33: Строка 30:
 
|proof=
 
|proof=
 
[[Файл:f2cmax_first_fixed.png|400px|thumb|right|Рис. 1]]
 
[[Файл:f2cmax_first_fixed.png|400px|thumb|right|Рис. 1]]
Предположим обратное, что не существует оптимального расписания с одиннаковыми перестановками работ на станках. Рассмотрим некоторое оптимальное расписание с максимальным по длине общим префиксом на станках.  
+
Предположим обратное: что не существует оптимального расписания с одинаковыми перестановками работ на станках.  
 +
Рассмотрим некоторое оптимальное расписание с максимальным по длине общим префиксом на станках. Пусть его длина равна <tex> k </tex>, где <tex> k < n </tex>. Пусть на <tex> k </tex> позиции на первом и втором станках стоит работа <tex> i </tex>, а на втором станке на позиции <tex> k + 1 </tex> стоит работа <tex> j </tex>. Тогда заметим, что если мы поставим работу <tex> j </tex> на первом станке сразу после работы <tex> i </tex>, то последовательные работы с <tex> h </tex> по <tex> m </tex> (см. рис. 1) по-прежнему будут успевать выполниться, так как на втором станке они выполняются в текущем расписании после <tex> j </tex>. Таким образом нам удалось увеличить длину наибольшего общего префикса, а так как по нашему предположению она была максимальна, то предположение неверно и искомое расписание с одинаковым порядком выполнения работ на обоих станках существует.
 +
}}
  
Пусть его длина равна <tex> k </tex>, где <tex> k < n </tex>. Пусть на <tex> k </tex> позиций на первом и втором станках стоит работа <tex> i </tex>, а на втором станке на позиций <tex> k + 1 </tex> стоит работа <tex> j </tex>. Тогда заметим, что если мы поставим работу <tex> j </tex> на первом станке сразу после работы <tex> i </tex>, то работы <tex> h </tex> по <tex> m </tex> (см. Рис. 1) по-прежнему будут успевать выполниться, так как на втором станке они выполняются в текущем расписаний после <tex> j </tex>. Таким образом нам удалось увеличить длину наибольщего общего префикса, а так как по нашему предположению она была максимальна, то наше предположение неверно, то искомое расписание с одиннаковым порядком выполнения работ на обоих станках существует.
+
Таким образом задача сводится к поиску этой перестановки. Докажем, что полученный приведенным выше алгоритмом список является оптимальной перестановкой работ.  
}}
 
  
Таким образом задача сводится к поиску этой искомой перестановки.  Докажем, что полученный нашим алгоритмом лист является отпимальной перестановкой работ.
+
{{лемма
{{Лемма
 
 
|id=lemma1
 
|id=lemma1
 
|about=1
 
|about=1
|statement= Если для каких работ <tex> i </tex> и <tex> j </tex> из листа <tex> T </tex> верно неравенство <tex> \min(p_{i1}, p_{j2}) <   \min(p_{j1}, p_{i2}) </tex>, то работа <tex> i </tex> встречается в листе <tex> T </tex> раньше, чем <tex> j </tex>
+
|statement= Если для каких-то работ <tex> i </tex> и <tex> j </tex> из списка <tex> T </tex> верно неравенство <tex> \min(p_{i1}, p_{j2}) < \min(p_{j1}, p_{i2}) </tex>, то работа <tex> i </tex> встречается в списке <tex> T </tex> раньше, чем <tex> j </tex>.
 
|proof=
 
|proof=
 
Пусть <tex> p_{i1} < p_{j2} </tex>. Случай <tex> p_{i1} > p_{j2} </tex> рассматривается аналогично.  
 
Пусть <tex> p_{i1} < p_{j2} </tex>. Случай <tex> p_{i1} > p_{j2} </tex> рассматривается аналогично.  
  
То есть имеем, что <tex> p_{i1} < \min(p_{j1}, p_{i2}) </tex>. Так как <tex> p_{i1} < \min(p_{j1}, p_{i2}) \leq p_{i2} </tex>, то работа <tex> i \in L </tex>. Работа <tex> j </tex> либо стоит в <tex> R </tex>, либо она стоит в <tex> L </tex> и при этом <tex> p_{i1} < p_{j1} </tex>. Заметим, что в обоих случаях она расположена позже (в силу нашего построения), чем работа <tex> i </tex>, то лемма доказана.  
+
Так как <tex> p_{i1} < \min(p_{j1}, p_{i2}) \leqslant p_{i2} </tex>, то работа <tex> i \in L </tex>. Работа <tex> j </tex> либо стоит в <tex> R </tex>, либо она стоит в <tex> L </tex> и при этом <tex> p_{i1} < p_{j1} </tex>. Заметим, что в обоих случаях она расположена позже (в силу нашего построения), чем работа <tex> i </tex>.
  
 
}}
 
}}
  
{{Лемма
+
{{лемма
 
|id=lemma2
 
|id=lemma2
 
|about=2
 
|about=2
|statement= Пусть имеет случайное расписание, в котором работа <tex> j </tex> идет сразу же после работы <tex> i </tex>. Тогда если <tex> \min(p_{j1}, p_{i2}) \leq   \min(p_{i1}, p_{j2}) </tex>, то можем поменять местами эти работы без ухудшение целевой функций.  
+
|statement= Пусть имеем произвольное расписание, в котором работа <tex> j </tex> идет сразу же после работы <tex> i </tex>. Тогда если <tex> \min(p_{j1}, p_{i2}) \leqslant   \min(p_{i1}, p_{j2}) </tex>, то можем поменять местами эти работы без ухудшения целевой функции.  
 
|proof=
 
|proof=
[[Файл:f2cmax_fixed.png|400px|thumb|right|Рис. 2 - Расположение последовательных работ]]
+
[[Файл:f2cmax_fixed.png|200px|thumb|right|Рис. 2 {{---}} Расположение последовательных работ]]
 
Пусть <tex> w_{ij} </tex> {{---}} время, прошедшее с начала выполнения работы <tex> i </tex> на первом станке до окончания работы <tex> j </tex> на втором станке.  
 
Пусть <tex> w_{ij} </tex> {{---}} время, прошедшее с начала выполнения работы <tex> i </tex> на первом станке до окончания работы <tex> j </tex> на втором станке.  
  
Строка 62: Строка 59:
 
<li>Работа <tex> i </tex> начинается на втором станке сразу же после завершения ее на первом
 
<li>Работа <tex> i </tex> начинается на втором станке сразу же после завершения ее на первом
 
<ul>
 
<ul>
<li> Выполнение работы <tex> i </tex> на втором станке заканчивается позже, чем работы <tex> j </tex> на первом.  В этом случае <tex> w_{ij} = p_{i1} + p_{i2} + p_{j2} </tex>.</li>
+
* Выполнение работы <tex> i </tex> на втором станке заканчивается позже, чем работы <tex> j </tex> на первом.   
<li> Выполнение работы <tex> i </tex> на втором станке заканчивается раньше, чем работы <tex> j </tex> на первом.  В этом случае <tex> w_{ij} = p_{i1} + p_{j1} + p_{j2}  </tex>. </li>
+
*: Тогда <tex> w_{ij} = p_{i1} + p_{i2} + p_{j2} </tex>.
 +
* Выполнение работы <tex> i </tex> на втором станке заканчивается раньше, чем работы <tex> j </tex> на первом.   
 +
*: В этом случае <tex> w_{ij} = p_{i1} + p_{j1} + p_{j2}  </tex>.  
 
</ul>
 
</ul>
 
</li>
 
</li>
 
<li>Работа <tex> i </tex> не может  начаться на втором станке сразу же после завершения ее на первом  
 
<li>Работа <tex> i </tex> не может  начаться на втором станке сразу же после завершения ее на первом  
<ul>
+
 
<li> Выполнение работы <tex> i </tex> на втором станке заканчивается раньше, чем работы <tex> j </tex> на первом. В этом случае  снова имеем <tex> w_{ij} = p_{i1} + p_{j1} + p_{j2}  </tex>.</li>
+
* Выполнение работы <tex> i </tex> на втором станке заканчивается раньше, чем работы <tex> j </tex> на первом.  
<li> Выполнение работы <tex> i </tex> на втором станке заканчивается позже, чем работы <tex> j </tex> на первом. Пусть <tex> delta </tex> {{---}} время прошедшее с начала выполнения работы <tex> i</tex> на первом станке и до начала ее выполнения на втором станке. Тогда имеем, что <tex> w_{ij} = delta + p_{i2} + p_{j2} </tex>. </li>
+
*: Здесь снова имеем <tex> w_{ij} = p_{i1} + p_{j1} + p_{j2}  </tex>.
</ul>
+
* Выполнение работы <tex> i </tex> на втором станке заканчивается позже, чем работы <tex> j </tex> на первом.          
 +
*: Пусть <tex> \Delta </tex> {{---}} время прошедшее с начала выполнения работы <tex> i</tex> на первом станке и до начала ее выполнения на втором станке. Получили, что <tex> w_{ij} = \Delta + p_{i2} + p_{j2} </tex>.  
 +
 
 
</li>
 
</li>
 
</ol>
 
</ol>
  
Таким образом, <tex> w_{ij} = \max (p_{i1} + p_{j1} + p_{j2}, p_{i1} + p_{i2} + p_{j2}, delta + p_{i2} + p_{j2}) </tex>. Иначе говоря  <tex> w_{ij} = \max (p_{i1} + \max(p_{j1}, p_{i2}) + p_{j2}, delta + p_{i2} + p_{j2}) </tex>.
+
Таким образом, <tex> w_{ij} = \max (p_{i1} + p_{j1} + p_{j2}, p_{i1} + p_{i2} + p_{j2}, \Delta + p_{i2} + p_{j2}) </tex>.
 +
 +
Иначе говоря,   <tex> w_{ij} = \max (p_{i1} + \max(p_{j1}, p_{i2}) + p_{j2}, \Delta + p_{i2} + p_{j2}) </tex>.
  
Аналогично имеем, что <tex> w_{ji} = \max (p_{j1} + \max(p_{i1}, p_{j2}) + p_{i2},  delta + p_{i2} + p_{j2}) </tex>
+
Аналогично, <tex> w_{ji} = \max (p_{j1} + \max(p_{i1}, p_{j2}) + p_{i2},  \Delta + p_{i2} + p_{j2}) </tex>
  
Так как <tex> \min(a, b) = - \max(-a, -b)</tex>, то из условию леммы имеем <tex> \max(-p_{i1}, -p_{j2}) \leq   \max(-p_{j1}, -p_{i2}) </tex>, то добавим <tex> p_{i1} + p_{i2} + p_{j1} + p_{j2} </tex> к обеим частям. То получим, что <tex> p_{j1} + \max(p_{i1}, p_{j2}) + p_{i2} \leq p_{i1} + \max(p_{j1}, p_{i2}) + p_{j2} </tex>, то есть <tex> w_{ji} \leq w_{ij} </tex>, то при смене местами работ <tex> i </tex> и <tex> j </tex> ответ не ухудшается.  
+
Так как <tex> \min(a, b) = - \max(-a, -b)</tex>, то из условия леммы имеем <tex> \max(-p_{i1}, -p_{j2}) \leqslant   \max(-p_{j1}, -p_{i2}) </tex>. Добавив <tex> p_{i1} + p_{i2} + p_{j1} + p_{j2} </tex> к обеим частям, получим, что <tex> p_{j1} + \max(p_{i1}, p_{j2}) + p_{i2} \leqslant p_{i1} + \max(p_{j1}, p_{i2}) + p_{j2} </tex>, то есть <tex> w_{ji} \leqslant w_{ij} </tex> и при смене местами работ <tex> i </tex> и <tex> j </tex> ответ не ухудшается.  
  
 
}}
 
}}
Строка 88: Строка 91:
  
 
|proof=
 
|proof=
Рассмотрим случайную перестановку <tex> S </tex>. Пусть перестановки <tex> T </tex> и <tex> S </tex> имеют общий префикс длины <tex> l-1 </tex>. Пусть <tex> i = T_{l} </tex> и <tex> j = S_{l} </tex>. Рассмотрим множество работ <tex>M = \{T_{r} \mid  r = l, \dots, n\}</tex>. Заметим, что для любой работы <tex> k \in M </tex> верно, что <tex> \min(p_{k1}, p_{i2}) \geq \min(p_{i1}, p_{k2}) </tex>, так как если было бы верно обратное, то есть <tex> \min(p_{k1}, p_{i2}) < \min(p_{i1}, p_{k2}) </tex>, то по Лемме 1 было бы верно, что <tex> k </tex> идет раньше <tex> i </tex>, что неверно.  
+
Рассмотрим произвольную перестановку <tex> S </tex>. Пусть перестановки <tex> T </tex> и <tex> S </tex> имеют общий префикс длины <tex> l-1 </tex>. Пусть <tex> i = T_{l} </tex> и <tex> j = S_{l} </tex>. Рассмотрим множество работ <tex>M = \{T_{r} \mid  r = l, \dots, n\}</tex>. Заметим, что для любой работы <tex> k \in M </tex> верно, что <tex> \min(p_{k1}, p_{i2}) \geqslant \min(p_{i1}, p_{k2}) </tex>, так как если было бы верно обратное, то есть <tex> \min(p_{k1}, p_{i2}) < \min(p_{i1}, p_{k2}) </tex>, то по лемме 1 было бы верно, что <tex> k </tex> идет раньше <tex> i </tex>, что неверно.  
  
Очевидно, что в перестановке <tex> S </tex> работа <tex> i </tex> будет стоять после <tex> j </tex> (иначе общий префикс был бы короче), то заметим, что в этой перестановке для работы <tex> i </tex> и для предыдущей работы <tex> w </tex> верно <tex> \min(p_{w1}, p_{i2}) \geq \min(p_{i1}, p_{w2}) </tex> (так как <tex> w \in M </tex>), то по Лемме 2 можем поменять местами работы <tex> i </tex> и <tex> w </tex> без ухудшения ответа. То такими операциями сможем дойти до пары работ <tex> i </tex> и <tex> j </tex>, которые при смене увеличат общий префикс перестановок <tex> S </tex> и <tex> T </tex>.  
+
Очевидно, что в перестановке <tex> S </tex> работа <tex> i </tex> будет стоять после <tex> j </tex> (иначе общий префикс был бы длиннее), то заметим, что в этой перестановке для работы <tex> i </tex> и для предыдущей работы <tex> w </tex> верно <tex> \min(p_{w1}, p_{i2}) \geqslant \min(p_{i1}, p_{w2}) </tex> (так как <tex> w \in M </tex>), то по лемме 2 можем поменять местами работы <tex> i </tex> и <tex> w </tex> без ухудшения ответа. То такими операциями сможем дойти до пары работ <tex> i </tex> и <tex> j </tex>, которые при смене увеличат общий префикс перестановок <tex> S </tex> и <tex> T </tex>.  
  
 
Таким образом любая перестановка сводится к нашей без ухудшения ответа такими операциями, что подтверждает оптимальность перестановки <tex> T </tex>
 
Таким образом любая перестановка сводится к нашей без ухудшения ответа такими операциями, что подтверждает оптимальность перестановки <tex> T </tex>
Строка 97: Строка 100:
  
 
==Псевдокод==
 
==Псевдокод==
   <tex>L \leftarrow \varnothing </tex>
+
 
  <tex>R \leftarrow \varnothing </tex>
+
   '''function''' F2Cmax(p: '''int'''[n][2]): '''list<int>'''
  <tex>X \leftarrow \{1, \dots, n\}</tex>
+
      '''list<int>''' L = <tex>\varnothing </tex>
  while <tex> X \neq \varnothing</tex>
+
      '''list<int>''' R = <tex>\varnothing </tex>
      Найти <tex> i </tex> и <tex> j </tex>, где <tex>p_{ij} = \min \{ p_{ij} \mid i \in X; j = 1, 2\}</tex>
+
      '''set<int>''' X = <tex>\{1, \ldots, n\}</tex>
      if j = 1
+
      '''while''' X <tex>\neq \varnothing</tex>
        <tex>L \leftarrow L \circ i </tex>
+
        Найти i и j, такие что <tex>p_{ij} = \min \{ p_{ij} \mid i \in X \land j = 1, 2\}</tex>
      else  
+
        '''if''' j == 1
        <tex>R \leftarrow i \circ R </tex>
+
            L.addLast(i)
      <tex>X \leftarrow X \setminus \{i\} </tex>
+
        '''else'''
  <tex>T \leftarrow L \circ R</tex>
+
            R.addFirst(i)
+
        X.remove(i)
  Расставляем работы на первом станке согласно перестановке <tex> T </tex>
+
      '''list<int>''' T = L ++ R
 
+
      '''return''' T
  Расставляем работы на втором станке согласно перестановке <tex> T </tex>
 
  и времени начала соответсвующей работы на первом станке.
 
  
 
==Сложность алгоритма==
 
==Сложность алгоритма==
Заметим, что на каждом шаге алгоритма мы выбираем минимум из оставшихся элементов за <tex>O(\log n)</tex> (либо предварительной сортировкой, либо любой структурой данных, поддеживающей нахождение минимума и удаление за <tex>O(\log n)</tex>). И делаем мы это <tex> n </tex> раз, следовательно алгоритм работает за <tex>O(n\log n)</tex>.
+
Заметим, что на каждом шаге алгоритма мы выбираем минимум из оставшихся элементов за <tex>O(\log n)</tex> (либо предварительной [[Сортировка|сортировкой]], либо с помощью любой структуры данных, поддерживающей нахождение минимума и удаление за <tex>O(\log n)</tex>, например, [[Двоичная_куча|кучи]]). А так как мы делаем это <tex> n </tex> раз, алгоритм работает за <tex>O(n\log n)</tex>.
 +
 
 +
==См. также==
 +
* [[J2ni2Cmax|<tex>J2 \mid n_i \leqslant 2 \mid C_{max}</tex>]]
 +
* [[O2Cmax|<tex>O2\mid\mid C_{max}</tex>]]
 +
* [[R2Cmax|<tex>R2\mid\mid C_{max}</tex>]]
  
==Источники==
+
==Источники информации==
 
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 175 стр. {{---}} ISBN 978-3-540-69515-8
 
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 175 стр. {{---}} ISBN 978-3-540-69515-8
  
[[Категория: Дискретная математика и алгоритмы]]
+
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Теория расписаний]]
 
[[Категория: Теория расписаний]]

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

[math]F2 \mid\mid C_{max} [/math]

Задача:
Рассмотрим задачу:
  • дано [math]n[/math] работ и [math]2[/math] станка,
  • для каждой работы известно её время выполнения на каждом станке [math]p_{ij}[/math],
  • каждую работу необходимо выполнить сначала на первом станке, а потом на втором.
Требуется минимизировать время окончания выполнения всех работ.


Описание алгоритма

Пусть [math]p_{i1}[/math] — время выполнения [math]i[/math]-ой работы на первом станке, а [math]p_{i2}[/math] — на втором.

  1. Алгоритм строит два списка [math] L [/math] и [math] R [/math]. Изначально они пусты. Также поддерживается множество еще не распределенных по спискам [math] L [/math] и [math] R [/math] работ [math]X = \{i \mid i = 1, \dots, n\}[/math]
  2. Пока множество [math] X [/math] не пусто, распределяем работы по спискам следующим образом:
    • находим такие индексы [math] i [/math] и [math] j [/math], что [math]p_{ij} = \min \{ p_{ij} \mid i \in X \land j = 1, 2\}[/math],
    • если минимум достигается на первом станке (иными словами [math] j = 1 [/math]), то поставим работу [math] i [/math] в конец списка [math] L [/math], иначе ставим в начало списка [math] R [/math],
    • удаляем работу [math] i [/math] из множества [math] X [/math].
  3. Рассмотрим список [math] T = L ~\texttt{++}~ R[/math] — конкатенацию [math] L[/math] и [math]R[/math]. Утверждается, что этот список является оптимальной перестановкой работ как на первом, так и на втором станке. Далее расставляем подряд работы на первом станке согласно перестановке, после чего ставим в том же порядке работы на втором станке, при этом избегая одновременного выполнения одной и той же работы.

Доказательство корректности алгоритма

Теорема:
Существует оптимальное расписание, в котором станки выполняют работы в одном и том же порядке.
Доказательство:
[math]\triangleright[/math]
Рис. 1

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

Рассмотрим некоторое оптимальное расписание с максимальным по длине общим префиксом на станках. Пусть его длина равна [math] k [/math], где [math] k \lt n [/math]. Пусть на [math] k [/math] позиции на первом и втором станках стоит работа [math] i [/math], а на втором станке на позиции [math] k + 1 [/math] стоит работа [math] j [/math]. Тогда заметим, что если мы поставим работу [math] j [/math] на первом станке сразу после работы [math] i [/math], то последовательные работы с [math] h [/math] по [math] m [/math] (см. рис. 1) по-прежнему будут успевать выполниться, так как на втором станке они выполняются в текущем расписании после [math] j [/math]. Таким образом нам удалось увеличить длину наибольшего общего префикса, а так как по нашему предположению она была максимальна, то предположение неверно и искомое расписание с одинаковым порядком выполнения работ на обоих станках существует.
[math]\triangleleft[/math]

Таким образом задача сводится к поиску этой перестановки. Докажем, что полученный приведенным выше алгоритмом список является оптимальной перестановкой работ.

Лемма (1):
Если для каких-то работ [math] i [/math] и [math] j [/math] из списка [math] T [/math] верно неравенство [math] \min(p_{i1}, p_{j2}) \lt \min(p_{j1}, p_{i2}) [/math], то работа [math] i [/math] встречается в списке [math] T [/math] раньше, чем [math] j [/math].
Доказательство:
[math]\triangleright[/math]

Пусть [math] p_{i1} \lt p_{j2} [/math]. Случай [math] p_{i1} \gt p_{j2} [/math] рассматривается аналогично.

Так как [math] p_{i1} \lt \min(p_{j1}, p_{i2}) \leqslant p_{i2} [/math], то работа [math] i \in L [/math]. Работа [math] j [/math] либо стоит в [math] R [/math], либо она стоит в [math] L [/math] и при этом [math] p_{i1} \lt p_{j1} [/math]. Заметим, что в обоих случаях она расположена позже (в силу нашего построения), чем работа [math] i [/math].
[math]\triangleleft[/math]
Лемма (2):
Пусть имеем произвольное расписание, в котором работа [math] j [/math] идет сразу же после работы [math] i [/math]. Тогда если [math] \min(p_{j1}, p_{i2}) \leqslant \min(p_{i1}, p_{j2}) [/math], то можем поменять местами эти работы без ухудшения целевой функции.
Доказательство:
[math]\triangleright[/math]
Рис. 2 — Расположение последовательных работ

Пусть [math] w_{ij} [/math] — время, прошедшее с начала выполнения работы [math] i [/math] на первом станке до окончания работы [math] j [/math] на втором станке.

Рассмотрим возможные случаи расположения работ [math] i [/math] и [math] j [/math] (см. Рис. 2)

  1. Работа [math] i [/math] начинается на втором станке сразу же после завершения ее на первом
      • Выполнение работы [math] i [/math] на втором станке заканчивается позже, чем работы [math] j [/math] на первом.
        Тогда [math] w_{ij} = p_{i1} + p_{i2} + p_{j2} [/math].
      • Выполнение работы [math] i [/math] на втором станке заканчивается раньше, чем работы [math] j [/math] на первом.
        В этом случае [math] w_{ij} = p_{i1} + p_{j1} + p_{j2} [/math].
  2. Работа [math] i [/math] не может начаться на втором станке сразу же после завершения ее на первом
    • Выполнение работы [math] i [/math] на втором станке заканчивается раньше, чем работы [math] j [/math] на первом.
      Здесь снова имеем [math] w_{ij} = p_{i1} + p_{j1} + p_{j2} [/math].
    • Выполнение работы [math] i [/math] на втором станке заканчивается позже, чем работы [math] j [/math] на первом.
      Пусть [math] \Delta [/math] — время прошедшее с начала выполнения работы [math] i[/math] на первом станке и до начала ее выполнения на втором станке. Получили, что [math] w_{ij} = \Delta + p_{i2} + p_{j2} [/math].

Таким образом, [math] w_{ij} = \max (p_{i1} + p_{j1} + p_{j2}, p_{i1} + p_{i2} + p_{j2}, \Delta + p_{i2} + p_{j2}) [/math].

Иначе говоря, [math] w_{ij} = \max (p_{i1} + \max(p_{j1}, p_{i2}) + p_{j2}, \Delta + p_{i2} + p_{j2}) [/math].

Аналогично, [math] w_{ji} = \max (p_{j1} + \max(p_{i1}, p_{j2}) + p_{i2}, \Delta + p_{i2} + p_{j2}) [/math]

Так как [math] \min(a, b) = - \max(-a, -b)[/math], то из условия леммы имеем [math] \max(-p_{i1}, -p_{j2}) \leqslant \max(-p_{j1}, -p_{i2}) [/math]. Добавив [math] p_{i1} + p_{i2} + p_{j1} + p_{j2} [/math] к обеим частям, получим, что [math] p_{j1} + \max(p_{i1}, p_{j2}) + p_{i2} \leqslant p_{i1} + \max(p_{j1}, p_{i2}) + p_{j2} [/math], то есть [math] w_{ji} \leqslant w_{ij} [/math] и при смене местами работ [math] i [/math] и [math] j [/math] ответ не ухудшается.
[math]\triangleleft[/math]


Теорема:
Построенная перестановка [math] T [/math] является оптимальной.
Доказательство:
[math]\triangleright[/math]

Рассмотрим произвольную перестановку [math] S [/math]. Пусть перестановки [math] T [/math] и [math] S [/math] имеют общий префикс длины [math] l-1 [/math]. Пусть [math] i = T_{l} [/math] и [math] j = S_{l} [/math]. Рассмотрим множество работ [math]M = \{T_{r} \mid r = l, \dots, n\}[/math]. Заметим, что для любой работы [math] k \in M [/math] верно, что [math] \min(p_{k1}, p_{i2}) \geqslant \min(p_{i1}, p_{k2}) [/math], так как если было бы верно обратное, то есть [math] \min(p_{k1}, p_{i2}) \lt \min(p_{i1}, p_{k2}) [/math], то по лемме 1 было бы верно, что [math] k [/math] идет раньше [math] i [/math], что неверно.

Очевидно, что в перестановке [math] S [/math] работа [math] i [/math] будет стоять после [math] j [/math] (иначе общий префикс был бы длиннее), то заметим, что в этой перестановке для работы [math] i [/math] и для предыдущей работы [math] w [/math] верно [math] \min(p_{w1}, p_{i2}) \geqslant \min(p_{i1}, p_{w2}) [/math] (так как [math] w \in M [/math]), то по лемме 2 можем поменять местами работы [math] i [/math] и [math] w [/math] без ухудшения ответа. То такими операциями сможем дойти до пары работ [math] i [/math] и [math] j [/math], которые при смене увеличат общий префикс перестановок [math] S [/math] и [math] T [/math].

Таким образом любая перестановка сводится к нашей без ухудшения ответа такими операциями, что подтверждает оптимальность перестановки [math] T [/math]
[math]\triangleleft[/math]

Псевдокод

  function F2Cmax(p: int[n][2]): list<int>
     list<int> L = [math]\varnothing [/math]
     list<int> R = [math]\varnothing [/math]
     set<int> X = [math]\{1, \ldots, n\}[/math]
     while X [math]\neq \varnothing[/math]
        Найти i и j, такие что [math]p_{ij} = \min \{ p_{ij} \mid i \in X \land j = 1, 2\}[/math]
        if j == 1
           L.addLast(i)
        else 
           R.addFirst(i)
        X.remove(i)
     list<int> T = L ++ R
     return T

Сложность алгоритма

Заметим, что на каждом шаге алгоритма мы выбираем минимум из оставшихся элементов за [math]O(\log n)[/math] (либо предварительной сортировкой, либо с помощью любой структуры данных, поддерживающей нахождение минимума и удаление за [math]O(\log n)[/math], например, кучи). А так как мы делаем это [math] n [/math] раз, алгоритм работает за [math]O(n\log n)[/math].

См. также

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

  • Peter Brucker. «Scheduling Algorithms» — «Springer», 2006 г. — 175 стр. — ISBN 978-3-540-69515-8