Изменения

Перейти к: навигация, поиск

O2Cmax

2821 байт добавлено, 20:43, 18 мая 2016
Нет описания правки
<tex dpi =200>O2 \mid \mid C_{max}</tex>{{Задача|definition= Постановка задачи ==Рассмотрим задачу:<ol><li>Дано *дано <tex>n</tex> работ и <tex>2</tex> станка.</li>,<li>Для *для каждой работы известно её время выполнения на каждом станке.</li></ol>Требуется минимизировать время окончания всех работ, если каждую работу необходимо выполнить на обоих станках.}}
== Описание алгоритма ==
Пусть <tex>a_{i}</tex> {{---}} время выполнения <tex>i</tex>-ой работы на первом станке, а <tex>b_{i}</tex> {{---}} на втором.<br/>
<ol><li>#Разобьём все работы на два множества: <tex>I = \{i \mid a_{i} \le leqslant 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 \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> </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> # Рассмотрим два случая. Первый случай, когда :## <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>.[[Файл:Picture2.gif‎|500px|center]]## </litex>a_{x} \leqslant b_{y}</ultex>Второй случай сводится . Сводится к первому: все работы , если поменять местами станки и станки меняются местамисоответствующие списки времён выполнения, при этом надо заново выполнить пункты 1, 2 и решается задача для первого случая3.</li></ol>[[Файл:O2CmaxПри выдаче ответа меняем станки обратно местами.gif|300px|center]]
==Доказательство корректности алгоритма==
Расписание, построенное данным алгоритмом, является корректным и оптимальным.
|proof=
Чтобы доказать корректность, надо доказать, что на каждом станке никакая из работ в любой момент времени выполняется не пересекаетсяболее одной работы, и что каждая работа в каждый момент времени выполняется только не более, чем на одном станке.<br/>Первое утверждение вытекает из того, что мы строили расписание, опираясь на <tex>C_{max}</tex>. Из построения <tex>C_{max} \ge geqslant \sum \limits_{i = 1}^{n}a_{i}, \sum \limits_{i = 1}^{n}b_{i}</tex>, следовательно на каждом станке нет пересечения работв любой момент времени выполняется не более одной работы.<br/>Докажем теперь второе утверждение. У нас имеется 3 три блокаработ: <tex> I \setminus \{x\}, \{x\}, J</tex>.<ol><li># Для блока <tex> \{x\}</tex> пересечения отсутствуют это следует из того, что <tex> C_{max} \ge geqslant a_{x}+b_{x}</tex>, а этот блок работа <tex> x </tex> выполняется с разных концов станков. Получили, значит он не может пересекаться.что отрезки выполнения работы <tex> x </litex>на разных станках не пересекаются.<li>Для блока # Покажем, что любая работа из <tex> I \setminus \{x\}</tex> рассмотри начинает выполняться на втором станке позже, чем заканчивает выполняться на первом. Для этого рассмотрим сумму:<ulbr><tex>\sum \limits_{i = 1}^k a_{i} \le leqslant \sum \limits_{i = 1}^k b_{i} \le = \sum \limits_{i = 1}^{k - 1} b_{i} + b_{x}</tex>, где <tex>1 \dots k</ultex> {{---}} это работы, выполняемые на первом станке во время данного блока.<br>Это неравенство следует из выбора <tex>I</tex> и из того, что <tex>b_{x} \ge geqslant a_{x} \ge geqslant a_{i}, \forall i \in I</tex>.<br/>Получили, что этот блок тоже не пересекаетсякаждая работа из этого блока начинает выполняться на втором станке позже, чем она заканчивается на первом.</libr><li>Для блока # Покажем, что любая работа из <tex>J</tex> рассмотри начинает выполняться на втором станке позже, чем заканчивает выполняться на первом. Для этого рассмотрим сумму:<ulbr><tex>\sum \limits_{i = 1}^k b_{i} \le leqslant \sum \limits_{i = 1}^k a_{i} \le leqslant \sum \limits_{i = 1}^{k - 1} a_{i} + a_{x}</tex>, где <tex>1 \dots k</ultex>{{---}} это работы, выполняемые на втором станке во время данного блока.Это неравенство следует из выбора <tex>J</tex> и из того, что <tex>a_{x} \ge geqslant a_{i}, \forall i \in I</tex>.<br/>Получили, что этот блок тоже не пересекаетсякаждая работа из этого блока начинает выполняться на втором станке позже, чем она заканчивается на первом.</li></ol>
Итого мы доказали корректность.<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>, а из построения оно равно максимум максимуму из нихэтих значений.
}}
==Псевдокод==
<font color=green>//Функция принимает список из времён выполнения на первом станке a и времён выполнения на втором станке b.<br>//Функция возвращает пару из расписания для первого станка и расписания для второго станка.</font> '''function''' scheduling(a: '''int'''[n], b: '''int[n]'''): '''pair<int[n], int[n]>''' <tex>I = \leftarrow varnothing </tex> <tex>J = \varnothing </tex> <tex>J 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}\leftarrow }\varnothing }</tex> '''for ''' <tex>i = 1 \dots </tex> '''to''' <tex>n</tex> '''if ''' <tex>a_{i} \le bleqslant b_{i}</tex> <tex> I \leftarrow = I \cup \{i\} </tex> '''else''' <tex> J \leftarrow = 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, x0</tex> Запомнить, что поменяли на первом станке расставляем расписание для <tex>time1 I \leftarrow 0setminus \{x\}</tex> shed2[x] Начиная с <tex>\leftarrow 0</tex> на втором станке расставляем расписание для <tex>time2 \leftarrow b_{x\}</tex> Для всех , затем для <tex>i \in I \setminus \{x\}</tex> sched1[i] <tex>\leftarrow time1<br/tex> От правой границы {{---}} <tex>time1 \leftarrow time1 + a_C_{imax}</tex> sched2[i] на первом станке расставляем расписание для <tex>\leftarrow time2</tex> <tex>time2 {x\leftarrow time2 + b_{i}</tex> Для всех , затем для <tex>i \in J</tex> sched1[i] От правой границы {{---}} <tex>\leftarrow time1</tex> <tex>time1 \leftarrow time1 + a_C_{imax}</tex> sched2[i] на втором станке расставляем расписание для <tex>\leftarrow time2J</tex> <tex>time2 \leftarrow time2 + b_{i}<br/tex> sched1 '''pair<int[n], int[xn] <tex>\leftarrow time1</tex>''' ans = пара из расписания для первого станка и расписания для второго станка <tex>time1 \leftarrow time1 + a_{x}</tex> '''return''' ans '''else''' '''pair<texint[n], int[n]>C_{max} \leftarrow \max\{time1''' ans = scheduling(b, time2\}</tex>a) if станки меняли Меняем местамирасписания для станков в ans поменять их обратно '''return''' ans
==Сложность алгоритма==
Каждое из множеств в сумме содержит <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
 
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Теория расписаний]]
251
правка

Навигация