148
правок
Изменения
→Постановка задачи
</ol>
Требуется минимизировать время окончания всех работ, если каждую работу необходимо выполнить на обоих станках.
== Описание алгоритма ==
Пусть <tex>a_{i}</tex> {{---}} время выполнения <tex>i</tex>-ой работы на первом станке, а <tex>b_{i}</tex> {{---}} на втором.<br/>
<ol>
<li>Разобьём все работы на два множества: <tex>I = \{i \mid a_{i} \le b_{i}; i = 1, \dots, n\}</tex> и <tex>J = \{i \mid a_{i} > b_{i}; i = 1, \dots, n\}</tex></li>
<li>Найдем <tex>a_{x} = max \{a_{i} \mid i \in I\}</tex> и <tex>b_{y} = max \{b_{i} \mid i \in J\}</tex> </li>
<li> Рассмотрим 2 случая. Первый случай, когда <tex>a_{x} \ge b_{y}</tex>, тогда
<ul>
<li>Выполняем все работы на первом станке в следующем порядке: сперва все работы из <tex>I \setminus \{x\}</tex>, затем из <tex>J</tex> и последней работу <tex>x</tex></li>
<li>На втором станке выполняем первой работу <tex>x</tex></li>
<li>Остальные работы выполняем на втором станке в порядке их завершения на первом тогда, когда второй станок свободен, а работа на первом уже выполнена</li>
</ul>
Второй случай рассматривается аналогично: первый и второй станок меняются местами, и вместо <tex>x</tex> {{---}} работа <tex>y</tex>
</li>
</ol>
