90
правок
Изменения
→Описание алгоритма
== Описание алгоритма ==
Пусть <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>
<li>Если минимум достигается на первом станке (иными словами <tex> j = 1 </tex>), то допишем работу <tex> i </tex> в конец листа <tex> L </tex>, иначе дописываем в начало листа <tex> R </tex> </li>
</ul>
</li>
<li> Рассмотрим лист <tex> T = L + R</tex>. Утверждается, что этот лист является оптимальной перестановкой работ как на первом, так и на втором станке. Далее расставляем подряд работы на первом станке согласно перестановке, после чего ставим в том же порядке работы на втором стане, при этом избегая одновременного выполнения одной и той же работы. </li>
</ol>
==Доказательство корректности алгоритма==
