Изменения

*Дано дано <tex>n</tex> работ и <tex>2</tex> станка.,*Для для каждой работы известно её время выполнения на каждом станке.

#Найдем такие <tex> x </tex> и <tex> y </tex>, что <tex>a_{x} = \max \limits_{i \in I} \{a_{i} \mid i \in I\}</tex> и <tex>b_{y} = \max \limits_{i \in J} \{b_{i} \mid i \in J\}</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,2 и 3. При выдаче ответа меняем станки обратно местами.

Докажем теперь второе утверждение. У нас имеется 3 три блока работ: <tex> I \setminus \{x\}, \{x\}, J</tex>.

Оптимальность вытекает из того, что <tex>C_{max}</tex> не может быть меньше <tex>\sum \limits_{i = 1}^{n} a_i, \ \sum \limits_{i = 1}^{n} b_i, \ \max \limits_{i = 1}^{n}\{a_i + b_{i}\}</tex>, а из построения оно равно максимуму из этих значений.

<font color=green>//Функция принимает список из времён выполнения на первом станке a и времён выполнения на втором станке b.<br>//Функция возвращает пару из расписания для первого станка и расписания для второго станка.</font> '''function''' scheduling(a: '''int'''[n], b: '''int[n]'''): '''pair<int[n], int[n]>''' <tex>I = \varnothing </tex> <tex>J = \varnothing </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> '''for''' <tex>i = 1</tex> '''to''' <tex>n</tex> '''if''' <tex>a_{i} \leqslant bb_{i}</tex> <tex> I = I \cup \{i\} </tex> '''else''' <tex> J = J \cup \{i\} </tex> Найти <tex>x</tex>, где <tex>a_{x} = \max \limits_{i \in I} \{a_{i}\}</tex> Найти <tex>y</tex>, где <tex>b_{y} = \max \limits_{i \in J} \{b_{i}\}</tex> '''if''' <tex>a_{x} < > b_{y}</tex> Поменять местами первый и второй станок Пересчитать <tex>I, J, x</tex> Запомнить, что поменяли Начиная с <tex>0</tex> на первом станке расставляем расписание для <tex>I \setminus \{x\}</tex> Начиная с <tex>0</tex> на втором станке расставляем расписание для <tex>\{x\}</tex>, затем для <tex>I \setminus \{x\}</tex><br/> От правой границы {{---}} <tex>C_{max}</tex> на первом станке расставляем расписание для <tex>\{x\}</tex>, затем для <tex>J</tex> От правой границы {{---}} <tex>C_{max}</tex> на втором станке расставляем расписание для <tex>J</tex><br/> '''pair<int[n], int[n]>''' ans = пара из расписания для первого станка и расписания для второго станка '''return''' ans '''else''' '''ifpair<int[n], int[n]>''' станки меняли ans = scheduling(b, a) Меняем местамирасписания для станков в ans поменять их обратно '''return''' ans

==См. также==* [[P2precpi1Lmax|<tex>P2 \mid prec, p_i = 1 \mid L_{\max}</tex>]]* [[R2Cmax|<tex>R2 \mid \mid C_{max}</tex>]]* [[F2Cmax|<tex>F2 \mid \mid C_{max}</tex>]]* [[O2Cmax|<tex>O2 \mid \mid C_{max}</tex>]]* [[J2ni2Cmax|<tex>J2 \mid n_{i} \leqslant 2 \mid C_{max}</tex>]]* [[J2pij1Lmax| <tex>J2\mid p_{ij} = 1\mid L_{max}</tex>]] == Источники информации ==* Peter Brucker «Scheduling Algorithms», fifth edition, Springer {{---}} с. 158{{---}}160 ISBN 978-3-540-69515-8 [[Категория: Дискретная математика Алгоритмы и алгоритмыструктуры данных]]