129
правок
Изменения
F2Cmax
,Нет описания правки
<tex dpi=200>F2 \mid\mid C_{max} </tex>{{Задача|definition= Постановка задачи ==Рассмотрим задачу:<ol><li>Дано *дано <tex>n</tex> работ и <tex>2</tex> станка.</li>,<li>Для *для каждой работы известно её время выполнения на каждом станке.<tex>p_{ij}</litex>,<li>Каждую *каждую работу необходимо выполнить сначала на первом станке, а потом на втором.</li></ol>Требуется минимизировать время окончания выполнения всех работ.}}
== Описание алгоритма ==
Пусть <tex>p_{i1}</tex> {{---}} время выполнения <tex>i</tex>-ой работы на первом станке, а <tex>p_{i2}</tex> {{---}} на втором.<br/>
<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> X </tex> непусто будем распределять не пусто, распределяем работы по спискам следующим образом:
<ul>
<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> i </tex> из множества <tex> X </tex> . </li>
</ul>
</li>
<li> Рассмотрим лист список <tex> T = L ~\circ texttt{++}~ R</tex> {{---}} конкатенацию <tex> L</tex> и <tex>R</tex>. Утверждается, что этот лист список является оптимальной перестановкой работ как на первом, так и на втором станке. Далее расставляем подряд работы на первом станке согласно перестановке, после чего ставим в том же порядке работы на втором станестанке, при этом избегая одновременного выполнения одной и той же работы. </li>
</ol>
==Доказательство корректности алгоритма==
{{Теорема|statement=Существует оптимальное расписание, в котором станки выполняют работы в одном и том же порядке. |proof=[[Файл: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>. Таким образом нам удалось увеличить длину наибольшего общего префикса, а так как по нашему предположению она была максимальна, то предположение неверно и искомое расписание с одинаковым порядком выполнения работ на обоих станках существует.}} Таким образом задача сводится к поиску этой перестановки. Докажем, что полученный нашим приведенным выше алгоритмом лист список является отпимальной оптимальной перестановкой работ. {{Леммалемма
|id=lemma1
|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>.
|proof=
Пусть <tex> p_{i1} < p_{j2} </tex>. Случай <tex> p_{i1} > p_{j2} </tex> рассматривается аналогично.
}}
==Псевдокод==
'''function''' F2Cmax(p: '''int'''[n][2]): '''list<int>''' '''list<int>''' L = <tex>L \leftarrow \varnothing </tex> '''list<int>''' R = <tex>R \leftarrow \varnothing </tex> '''set<int>''' X = <tex>X \leftarrow \{1, \dotsldots, n\}</tex> '''while ''' X <tex> X \neq \varnothing</tex> Найти <tex> i </tex> и <tex> j </tex>, где такие что <tex>p_{ij} = \min \{ p_{ij} \mid i \in X; \land j = 1, 2\}</tex> '''if ''' j == 1 <tex> L \leftarrow L \circ .addLast(i </tex>) '''else ''' <tex> R \leftarrow .addFirst(i \circ R </tex>) <tex> X \leftarrow X \setminus \{.remove(i\} </tex>) '''list<texint>''' T \leftarrow = L \circ ++ R</tex> Расставляем работы на первом станке согласно перестановке <tex> '''return''' T </tex> Расставляем работы на втором станке согласно перестановке <tex> T </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
[[Категория: Дискретная математика Алгоритмы и алгоритмыструктуры данных]]
[[Категория: Теория расписаний]]