148
правок
Изменения
→Описание алгоритма
<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 le b_{y}</tex>, тогда. Будем строить расписание с двух концов:
<ul>
<li>Выполняем все работы Строим расписание слева: выполняем на первом станке в следующем порядке: сперва все работы из <tex>I \setminus \{x\}</tex>, затем из а на втором выполняем первой работу <tex>Jx</tex> и последней работу , затем <tex>I \setminus \{x\}</tex>.</li><li>На втором Теперь, упираясь в левую границу, можно построить расписание справа: выполняем на первом станке выполняем первой работу все работы из <tex>xJ</tex>, затем </litex>x<li/tex>Остальные работы выполняем на втором станке в порядке их завершения на первом тогда, когда второй станок свободен, а работа на первом уже выполненадля второго выполняем работы из <tex>J</tex></li>
</ul>
Второй случай рассматривается аналогично: первый все работы и второй станок станки меняются местами, и вместо <tex>x</tex> {{---}} работа <tex>y</tex>.
</li>
</ol>
