129
правок
Изменения
м
То есть имеем, что <tex> p_{i1} < \min(p_{j1}, p_{i2}) </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>, то лемма доказана.
Нет описания правки
<tex dpi=200>F2 \mid\mid C_{max} </tex>
{{Задача
|definition=Рассмотрим задачу:
*Дано дано <tex>n</tex> работ и <tex>2</tex> станка.,*Для для каждой работы известно её время выполнения на каждом станке <tex>p_{ij}</tex>.,*Каждую каждую работу необходимо выполнить сначала на первом станке, а потом на втором .
Требуется минимизировать время окончания выполнения всех работ. }}
Пусть <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; j = 1, 2\}</tex> </li>
</ul>
</li>
<li> Рассмотрим список <tex> T = L \circ + R</tex> - конкатенацию <tex> L</tex> и <tex>R</tex>. Утверждается, что этот список является оптимальной перестановкой работ как на первом, так и на втором станке. Далее расставляем подряд работы на первом станке согласно перестановке, после чего ставим в том же порядке работы на втором станке, при этом избегая одновременного выполнения одной и той же работы. </li>
</ol>
|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> рассматривается аналогично.
}}
