251
правка
Изменения
Нет описания правки
{{Задача
|definition=Рассмотрим задачу:
*Дано дано <tex>n</tex> работ и <tex>2</tex> станка.,*Для для каждой работы известно её время выполнения на каждом станке.
Требуется минимизировать время окончания всех работ, если каждую работу необходимо выполнить на обоих станках.}}
Пусть <tex>a_{i}</tex> {{---}} время выполнения <tex>i</tex>-ой работы на первом станке, а <tex>b_{i}</tex> {{---}} на втором.<br/>
#Разобьём все работы на два множества: <tex>I = \{i \mid a_{i} \leqslant b_{i}; i = 1, \dots, n\}</tex> и <tex>J = \{i \mid a_{i} > b_{i}; i = 1, \dots, n\}</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>.
Итого мы доказали корректность.<br/>
Оптимальность вытекает из того, что <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>, а из построения оно равно максимуму из этих значений.
}}
<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>n</tex> элементов. Следовательно, чтобы найти максимум в каждом из множеств нам потребуется <tex>O(n)</tex> операций, чтобы составить расписание для каждой работы из множества нам потребуется так же <tex>O(n)</tex> операций. Получаем сложность алгоритма <tex>O(n)</tex>.
==См. также==* [[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 [[Категория: Дискретная математика Алгоритмы и алгоритмыструктуры данных]]
[[Категория: Теория расписаний]]
