129
правок
Изменения
Нет описания правки
<li> Пока множество <tex> X </tex> не пусто, распределяем работы по спискам следующим образом:
<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> j = 1 </tex>), то поставим работу <tex> i </tex> в конец списка <tex> L </tex>, иначе ставим в начало списка <tex> R </tex> , </li><li>Удаляем удаляем работу <tex> i </tex> из множества <tex> X </tex> . </li>
</ul>
</li>
<li>Работа <tex> i </tex> начинается на втором станке сразу же после завершения ее на первом
<ul>
</ul>
</li>
<li>Работа <tex> i </tex> не может начаться на втором станке сразу же после завершения ее на первом
</li>
</ol>
Таким образом, <tex> w_{ij} = \max (p_{i1} + p_{j1} + p_{j2}, p_{i1} + p_{i2} + p_{j2}, delta \Delta + p_{i2} + p_{j2}) </tex>. Иначе говоря , <tex> w_{ij} = \max (p_{i1} + \max(p_{j1}, p_{i2}) + p_{j2}, delta \Delta + p_{i2} + p_{j2}) </tex>.
Аналогично имеем, что <tex> w_{ji} = \max (p_{j1} + \max(p_{i1}, p_{j2}) + p_{i2}, delta \Delta + p_{i2} + p_{j2}) </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> ответ не ухудшается.
}}
==Псевдокод==
'''function''' F2Cmax(n: '''int''', p: '''int'''[in][2]):'''list''' '''list''' L = <tex>\varnothing </tex> '''list''' R = <tex>\varnothing </tex> '''set''' X = <tex>\{1, \dots, n\}</tex> '''while''' X <tex> \neq \varnothing</tex>:
Найти i и j , такие что <tex>p_{ij} = \min \{ p_{ij} \mid i \in X; j = 1, 2\}</tex>
'''if''' j == 1:
L.addLast(i)
'''else''':
R.addFirst(i)
X.remove(i)
'''list''' T = L + R
'''return''' T
==Сложность алгоритма==
Заметим, что на каждом шаге алгоритма мы выбираем минимум из оставшихся элементов за <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
[[Категория: Дискретная математика Алгоритмы и алгоритмыструктуры данных]]
[[Категория: Теория расписаний]]
