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>Построим целевую функцию: <tex>C_{max} = \max \{\sum \limits_{i = 1}^{n} a_i, \sum \limits_{i = 1}^{n} b_i, \max \limits_{i = 1}^{n}\{a_i + b_{i}\}\}</tex>.</li>
<li> Рассмотрим 2 случая. Первый случай, когда <tex>a_{x} \le b_{y}</tex>. Будем строить расписание с двух концов:
<ul>
<li>Строим расписание слева: выполняем на первом станке все работы из <tex>I \setminus \{x\}</tex>, а на втором выполняем первой работу <tex>x</tex>, затем <tex>I \setminus \{x\}</tex>.</li>
<li>Теперь, упираясь в левую границу, зная значение <tex>C_{max}</tex>, можно построить расписание справа: выполняем на первом станке все работы из <tex>J</tex>, затем <tex>x</tex>, а для второго выполняем работы из <tex>J</tex></li>
</ul>
Второй случай рассматривается аналогично: все работы и станки меняются местами.
