Изменения

<div styletex dpi ="background-color: #ABCDEF; font-size: 16px; font-weight: bold; color: #000000; text-align: center; padding: 4px; border-style: solid; border-width: 1px;"200>Эта статья находится в разработке!O2 \mid \mid C_{max}</div><includeonly>[[Категория: В разработке]]</includeonlytex>{{Задача|definition== Постановка задачи ==Рассмотрим задачу:<ol><li>Дано *дано <tex>n</tex> работ и <tex>2</tex> станка.</li>,<li>Для *для каждой работы известно её время выполнения на каждом станке.</li></ol>Требуется минимизировать время окончания всех работ, если каждую работу необходимо выполнить на обоих станках.}}

<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>.#Найдем такие <tex> x </litex> и <tex>y <li/tex>Найдем , что <tex>a_{x} = \max \limits_{i \in I} \{a_{i} \mid }</tex> и <tex>b_{y} = \max \limits_{i \in IJ} \{b_{i}\}</tex> и .#Построим оптимальное значение целевой функции: <tex>b_C_{ymax} = \max \{b_\sum \limits_{i = 1}^{n} a_i, \ \sum \limits_{i = 1}^{n} b_i,\ \max \limits_{i= 1}^{n} \mid {a_i + b_{i }\in J}\}</tex> .# Рассмотрим два случая:## <tex>a_{x} > b_{y}</litex>. Будем строить расписание с двух концов:##*Строим расписание слева: выполняем на первом станке все работы из <tex>I \setminus \{x\}<li/tex> Рассмотрим 2 случая, а на втором выполняем первой работу <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} \ge leqslant b_{y}</tex>. Сводится к первому, тогдаесли поменять местами станки и соответствующие списки времён выполнения, при этом надо заново выполнить пункты 1,2 и 3. При выдаче ответа меняем станки обратно местами. ==Доказательство корректности алгоритма=={{Теорема|statement=Расписание, построенное данным алгоритмом, является корректным и оптимальным.|proof=Чтобы доказать корректность, надо доказать, что на каждом станке в любой момент времени выполняется не более одной работы, и что каждая работа в каждый момент времени выполняется не более, чем на одном станке.<ulbr/>Первое утверждение вытекает из того, что мы строили расписание, опираясь на <tex>C_{max}</tex>. Из построения <litex>C_{max} \geqslant \sum \limits_{i = 1}^{n}a_{i}, \sum \limits_{i = 1}^{n}b_{i}</tex>Выполняем все работы , следовательно на первом каждом станке в следующем порядкелюбой момент времени выполняется не более одной работы.<br/>Докажем теперь второе утверждение. У нас имеется три блока работ: сперва все <tex> I \setminus \{x\}, \{x\}, J</tex>.# Для блока <tex> \{x\}</tex> это следует из того, что <tex> C_{max} \geqslant a_{x}+b_{x}</tex>, а работа <tex> x </tex> выполняется с разных концов станков. Получили, что отрезки выполнения работы <tex> x </tex> на разных станках не пересекаются.# Покажем, что любая работа из <tex>I \setminus \{x\}</tex>начинает выполняться на втором станке позже, затем чем заканчивает выполняться на первом. Для этого рассмотрим сумму:<br><tex>\sum \limits_{i = 1}^k a_{i} \leqslant \sum \limits_{i = 1}^k b_{i} = \sum \limits_{i = 1}^{k - 1} b_{i} + b_{x}</tex>, где <tex>1 \dots k</tex> {{---}} это работы, выполняемые на первом станке во время данного блока.<br>Это неравенство следует из выбора <tex>JI</tex> и последней работу из того, что <tex>b_{x} \geqslant a_{x} \geqslant a_{i}, \forall i \in I</tex>.</libr>Получили, что каждая работа из этого блока начинает выполняться на втором станке позже, чем она заканчивается на первом.<br># Покажем, что любая работа из <litex>J</tex>На начинает выполняться на втором станке выполняем первой работу позже, чем заканчивает выполняться на первом. Для этого рассмотрим сумму:<br><tex>\sum \limits_{i = 1}^k b_{i} \leqslant \sum \limits_{i = 1}^k a_{i} \leqslant \sum \limits_{i = 1}^{k - 1} a_{i} + a_{x}</tex>, где <tex>1 \dots k</litex>{{---}} это работы, выполняемые на втором станке во время данного блока.Это неравенство следует из выбора <tex>J</tex> и из того, что <litex>Остальные работы выполняем a_{x} \geqslant a_{i}, \forall i \in I</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>, а работа из построения оно равно максимуму из этих значений.}} ==Псевдокод== <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 b_{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}</litex> Начиная с <tex>0</tex> на первом станке расставляем расписание для <tex>I \setminus \{x\}</ultex>Второй случай рассматривается аналогично: первый и второй станок меняются местами Начиная с <tex>0</tex> на втором станке расставляем расписание для <tex>\{x\}</tex>, и вместо затем для <tex>I \setminus \{x\}</tex><br/> От правой границы {{---}} <tex>C_{max}</tex> на первом станке расставляем расписание для <tex>\{x\}</tex>, затем для <tex>J</tex> От правой границы {{---}} работа <tex>yC_{max}</tex> на втором станке расставляем расписание для <tex>J</tex><br/> '''pair<int[n], int[n]>''' ans = пара из расписания для первого станка и расписания для второго станка '''return''' ans '''else''' '''pair<int[n], int[n]>''' ans = scheduling(b, a) Меняем местами расписания для станков в 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}</litex>]]* [[J2pij1Lmax| <tex>J2\mid p_{ij} = 1\mid L_{max}</oltex>]] == Источники информации ==* Peter Brucker «Scheduling Algorithms», fifth edition, Springer {{---}} с. 158{{---}}160 ISBN 978-3-540-69515-8 [[Категория: Алгоритмы и структуры данных]][[Категория: Теория расписаний]]