251
правка
Изменения
→Описание алгоритма
#Найдем такие <tex> x </tex> и <tex> y </tex>, что <tex>a_{x} = \max \limits_{i \in I} \{a_{i}\}</tex> и <tex>b_{y} = \max \limits_{i \in J} \{b_{i}\}</tex>.
#Построим оптимальное значение целевой функции: <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>.
# Рассмотрим два случая. Первый случай, когда :## <tex>a_{x} > b_{y}</tex> (он показан на рисунке ниже). Будем строить расписание с двух концов:##*Строим расписание слева: выполняем на первом станке все работы из <tex>I \setminus \{x\}</tex>, а на втором выполняем первой работу <tex>x</tex>, затем <tex>I \setminus \{x\}</tex>.##*Теперь, упираясь в правую границу, равную <tex> C_{max} </tex>, можно построить расписание справа: выполняем на первом станке все работы из <tex>J</tex>, затем <tex>x</tex>, а для второго выполняем работы из <tex>J</tex>.:Второй случай сводится к первому: все работы и станки меняются местами, и решается задача для первого случая. [[Файл:Picture2.gif|500px|center]]## <tex>a_{x} \leqslant b_{y}</tex>. Сводится к первому, если поменять местами станки,при этом надо заново выполнить пункты 1-3. При выдаче ответа ответа меняем станки обратно местами.
==Доказательство корректности алгоритма==
