90
правок
Изменения
Нет описания правки
<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> T = L \circ R</tex>. Утверждается, что этот лист список является оптимальной перестановкой работ как на первом, так и на втором станке. Далее расставляем подряд работы на первом станке согласно перестановке, после чего ставим в том же порядке работы на втором стане, при этом избегая одновременного выполнения одной и той же работы. </li>
</ol>
}}
Таким образом задача сводится к поиску этой искомой перестановки. Докажем, что полученный нашим алгоритмом лист список является отпимальной перестановкой работ.
{{Леммалемма
|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> рассматривается аналогично.
}}
{{Леммалемма
|id=lemma2
|about=2
