40
правок
Изменения
м
→Описание алгоритма
<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> x </tex> и <tex> y </tex>, что <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>
Второй случай рассматривается аналогичносводится к первому: все работы и станки меняются местами, и решается задача для первого случая.
</li>
</ol>
