http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=Sergej+ArkhipovВикиконспекты - Вклад участника [ru]2026-08-04T13:39:21ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=1ripi1sumwc&diff=475611ripi1sumwc2015-06-05T12:18:28Z<p>Sergej Arkhipov: /* Реализация 2 */</p>
<hr />
<div><tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum w_i C_i</tex><br />
<br />
{{Задача<br />
|definition=<br />
Дано <tex>n</tex> работ и один станок. Для каждой работы известно её время появления <tex>r_{i}</tex> и вес <tex>w_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>. Требуется выполнить все работы, чтобы значение <tex>\sum w_{i} C_{i}</tex> было минимальным, где <tex>C_{i}</tex> {{---}} время окончания работы.<br />
}}<br />
<br />
==Более простые варианты исходной задачи==<br />
<br />
Перед решением основной задачи рассмотрим более простые.<br />
<br />
===Вариант 1===<br />
<tex> 1 \mid p_i = 1\mid \sum C_i</tex><br />
<br />
Этот случай простейший. Ответом будет <tex>\sum\limits_{k = 1}^n(k)</tex>, так как мы <tex>n</tex> раз сложим время окончания выполнения одной работы. Воспользовавшись формулой суммы первых <tex>n</tex> членов арифметической прогрессии алгоритм <tex>S_n=\frac{a_1+a_n}2 \cdot n</tex> будет работает за <tex>O(1)</tex>, но если нужно вывести и само расписание время работы будет <tex>O(n)</tex>.<br />
<br />
===Вариант 2===<br />
<tex> 1 \mid p_i = 1\mid \sum w_i C_i</tex><br />
<br />
Для верного выполнения просто выставим работы по порядку невозрастания весов, тогда ответом будет <tex> \sum\limits_{i = 1}^nw_i C_i</tex>, так как мы <tex>n</tex> раз сложим время окончания выполнения одной работы (которое в нашем случае <tex>C_{i-1}+1</tex>) домноженное на вес этой работы. Данный алгоритм корректен по [[Задача_о_минимуме/максимуме_скалярного_произведения|теореме о минимуме/максимуме скалярного произведения]], так как мы сопоставляем две последовательности, подходящие под условия теоремы. <br />
<br />
Так как [[Сортировка|сортировка]] весов занимает <tex>O(n \log n)</tex> время, то асимптотика времени работы алгорита равна <tex>O(n + n \log n)</tex>.<br />
<br />
===Вариант 3===<br />
<tex> 1 \mid r_i,p_i = 1 \mid \sum f_i</tex><br />
<br />
<tex>f_{i}</tex> {{---}} монотонная функция времени окончания работы <tex>C_{i}</tex> для работ <tex>i = 1, 2, \ldots , n</tex>.<br />
<br />
<br />
Нам нужно распределить <tex>n</tex> работ в разное время. Если мы назначим время <tex>t</tex> для работы <tex>i</tex> то цена будет <tex>f_i(t + 1)</tex>. Функция <tex>f_i</tex> монотонно неубывающая, тогда работы в расписании надо располагать как можно раньше для получения верного решения. <tex>n</tex> временных интервалов <tex>t_i</tex> для <tex>n</tex> работ могут быть получены с помощью следующего алгоритма, где предполагается что работы отсортированы так:<br />
<br />
<tex> r_1 \leqslant r_2 \leqslant \ldots \leqslant r_n</tex> <br />
<br />
'''Псевдокод'''<br />
<br />
<tex>t_1 \leftarrow r_1 </tex><br />
'''for''' <tex> i \leftarrow 2</tex> '''to''' <tex>n</tex> '''do'''<br />
<tex> t_i \leftarrow </tex> '''max'''<tex>(r_i, \ t_{i-1} - 1)</tex><br />
<br />
Этот алгоритм работает за <tex>O(n \log n +n)</tex><br />
==Основная задача== <br />
===Описание алгоритма===<br />
Пусть <tex>time</tex> {{---}} текущий момент времени.<br/><br />
Для каждого очередного значения <tex>time</tex>, которое изменяется от <tex>0</tex> до времени окончания последней работы, будем:<br />
<ol><br />
<li> Выбирать работу <tex>j</tex> из множества невыполненных работ, у которой <tex>r_{i} \leqslant time</tex>, а значение <tex>w_{i}</tex> максимально.</li><br />
<li> Если мы смогли найти работу <tex>j</tex>, то выполняем её в момент времени <tex>time</tex> и удаляем из множества невыполненных работ.</li><br />
<li> Увеличиваем <tex>time</tex> на один.</li><br />
</ol><br />
<br />
===Доказательство корректности алгоритма===<br />
{{Теорема<br />
|statement=<br />
Расписание, построенное данным алгоритмом, является корректным и оптимальным.<br />
|proof=<br />
Доказательство будем вести от противного.<br/><br />
Рассмотрим расписание <tex>S_{1}</tex>, полученное после выполнения нашего алгоритма, и оптимальное расписание <tex>S_{2}</tex>.<br/><br />
Возьмём первый момент времени <tex>t_{1}</tex>, когда расписания различаются. Пусть в этот момент времени в <tex>S_{1}</tex>, будет выполняться работа с весом <tex>w_{1}</tex>, а в <tex>S_{2}</tex> {{---}} работа с весом <tex>w_{2}</tex>.<br/><br />
Это первый момент, в котором расписания отличаются, значит в <tex>S_{2}</tex> работа с весом <tex>w_{1}</tex> выполнится в момент времени <tex>t_{2} > t_{1}</tex>.<br/><br />
Поменяем местами работы с весами <tex>w_{1}</tex> и <tex>w_{2}</tex> в <tex>S_{2}</tex> и полуим расписание <tex>S_{3}</tex>. Это возможно, потому что время появления этих работ не меньше <tex>t_{1}</tex>.<br/><br />
При такой перестановке ответы на задачу для <tex>S_{2}</tex> и <tex>S_{3}</tex> будут отличаться на <br />
<ul><tex>t_{1}w_{2} + t_{2}w_{1} - t_{1}w_{1} + t_{2}w_{2} = t_{1}(w_{2} - w_{1}) + t_{2}(w_{1} - w_{2}) = (t_{1} - t_{2})(w_{2} - w_{1})</tex></ul><br />
Первая скобка отрицательная: <tex>t_{1} < t_{2}</tex>. Вторая скобка тоже отрицательная из того, что в <tex>S_{1}</tex> работа с весом <tex>w_1</tex> выполняется раньше, значит её вес должен быть больше <tex>w_2</tex>.<br/><br />
Итого имеем, что ответ для <tex>S_{2}</tex> больше, чем ответ для <tex>S_{3}</tex>. Следовательно расписание <tex>S_2</tex> неоптимальное. Получили противоречие. Значит не существует такого момента времени, когда расписание <tex>S_{1}</tex> отличается от оптимального. Следовательно мы доказали, что оно оптимальное.<br />
}}<br />
<br />
===Псевдокод===<br />
<br />
====Реализация 1====<br />
<tex> S \leftarrow \{1 \ldots n\}</tex><br />
<tex> \mathtt{time} \leftarrow 0</tex><br />
<tex> \mathtt{answer} \leftarrow 0</tex><br />
'''while''' <tex> S \neq \varnothing </tex><br />
<tex> j \leftarrow null </tex><br />
'''if''' <tex> i \in S</tex> '''and''' <tex> r_{i} \leqslant \mathtt{time}</tex> '''and''' <tex>w_i \geqslant \max\limits_{j \in S, j = 1 \ldots n} w_j</tex><br />
<tex> j \leftarrow i </tex><br />
'''if''' <tex>j \neq null </tex><br />
<tex> S \leftarrow S \setminus j</tex><br />
<tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot w_{j}</tex><br />
<tex> \mathtt{time++}</tex><br />
<br />
Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \max\limits_{i = 1 \ldots n} r_{i}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, [[:Категория:Приоритетные_очереди|очередь с приоритетами]]. Значит общее время работы алгоритма <tex>O((n + \max\limits_{i = 1 \ldots n} r_{i})\log n)</tex><br />
<br />
====Реализация 2====<br />
Перед началом алгоритма [[Сортировка|отсортируем]] работы по порядку неубывания веса.<br />
<tex> \mathtt{time} \leftarrow r_1</tex><br />
<tex> \mathtt{answer} \leftarrow 0</tex><br />
'''for''' <tex>i \leftarrow 1 </tex> '''to''' <tex>n</tex> '''do'''<br />
'''if''' <tex> r_{i} \leqslant \mathtt{time}</tex><br />
<tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot w_{i}</tex><br />
'''else'''<br />
<tex> \mathtt{time} \leftarrow r_i</tex><br />
<tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot w_{i}</tex><br />
<tex> \mathtt{time++}</tex><br />
<br />
В начале алгоритма сортируем работы <tex>O(n \log n)</tex> времени. Затем мы тратим <tex>O(n)</tex> на получение ответа. Тогда суммарное время работы алгоритма составит <tex>O(n \log n + n )</tex> что есть <tex>O(n (\log n + 1))</tex> времени.<br />
<br />
==См. также==<br />
* [[Классификация задач]]<br />
* [[1outtreesumwc|<tex>1 \mid outtree \mid \sum w_i C_i</tex>]]<br />
* [[1ridipi1|<tex>1 | r_{i}, d_{i}, p_{i}=1 | -</tex>]]<br />
<br />
==Источники информации==<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 19-20<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 38-39<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 84-85<br />
* Лазарев А.А., Мусатова Е.Г., Кварацхелия А.Г., Гафаров Е.Р. Пособие по теории расписаний.<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Теория расписаний]]</div>Sergej Arkhipovhttp://neerc.ifmo.ru/wiki/index.php?title=Fpij1sumwu&diff=47548Fpij1sumwu2015-06-05T10:49:27Z<p>Sergej Arkhipov: </p>
<hr />
<div><tex dpi = "200">F \mid p_{ij} = 1 \mid \sum w_iu_i</tex><br />
{{Задача<br />
|definition=<br />
Дано <tex>m</tex> станков, на которых нужно обработать <tex>n</tex> деталей. Каждую деталь нужно обработать по очереди на всех станках. Любая работа на любом станке выполняется единицу времени. Для каждой работы есть дедлайн <tex>d_i</tex> {{---}} время, до которого она должна быть закончена, и штраф <tex>w_i</tex>, который нужно будет выплатить в случае, если работа была закончена после <tex>d_i</tex>. Необходимо минимизировать суммарный штраф, который придется выплатить.<br />
}}<br />
<br />
==Алгоритм==<br />
<br />
===Описание алгоритма===<br />
<br />
{{Утверждение<br />
|statement=Существует оптимальное расписание, в котором каждая работа делается непрерывно.<br />
|proof=<br />
Рассмотрим расписание, в котором есть работы, которые делаются не непрерывно. Рассмотрим самый ранний разрыв: работа <tex>i</tex> делалась в моменты <tex>t(i), t(i) + 1, \ldots, t(i) + k</tex>, где <tex>k < m</tex>, но не делалась в момент времени <tex>t(i) + k + 1</tex>. Докажем, что в момент времени <tex>t(i) + k + 1</tex>, <tex>k + 1</tex>-й станок простаивает и можно продолжить делать <tex>i</tex>-ю работу. <br />
<br />
Пусть в момент времени <tex>t(i) + k + 1</tex> на <tex>k + 1</tex>-м станке делается работа <tex>j</tex>. <br />
В <tex>t(i) + k</tex>-й момент времени <tex>k</tex>-й станок был занят выполнением <tex>i</tex>-й работы, а значит, не мог выполнять <tex>j</tex>-ю. Значит, разрыв был раньше, что противоречит тому, что был выбран самый ранний разрыв. Значит, в <tex>t(i) + k + 1</tex>-й момент <tex>k + 1</tex>-й станок свободен и туда можно поставить <tex>i</tex>-ю работу, устранив разрыв. <br />
<br />
После устранения каждого разрыва получим расписание без разрывов, в котором каждая работа заканчивает выполняться не позже, чем в изначальном.<br />
}}<br />
<br />
По этому утверждению, если работу <tex>i</tex> начали делать в <tex>t(i)</tex>, то закончена она будет в <tex>t(i) + m</tex>. Найдем время <tex>d'_i</tex> такое, что начав выполнять в него работу <tex>i</tex>, мы успеем выполнить ее до <tex>d_i</tex>: <tex>d'_i = d_i - m</tex>. Таким образом, вычтя из всех <tex>d_i</tex> число <tex>m</tex>, мы свели задачу к <tex>1 \mid p_i = 1 \mid \sum w_i U_i</tex>. <br />
<br />
Построив оптимальное расписание для <tex>1 \mid p_i = 1 \mid \sum w_i U_i</tex>, мы найдем времена, в которые нужно начинать выполнять работы. По утверждению выше, работы можно выполнять непрерывно.<br />
<br />
===Сложность алгоритма===<br />
Задача <tex>F \mid p_{i j} = 1 \mid \sum w_iu_i</tex> за <tex>O(n)</tex> сводится к [[1pi1sumwu|задаче <tex>1 \mid p_i = 1 \mid \sum w_i u_i</tex>]]. Задача <tex>1 \mid p_i = 1 \mid \sum u_iw_i</tex> решается за <tex>O(n \log n)</tex>. После решения этой задачи, нужно вывести ответ, имеющий размер <tex>O(nm)</tex>. Значит, итоговая сложность алгоритма {{---}} <tex>O(n \log n + nm)</tex>.<br />
<br />
==См. также.==<br />
* [[Классификация задач]]<br />
* [[Flow shop]]<br />
<br />
==Источники информации==<br />
* Лазарев А.А., Мусатова Е.Г., Кварацхелия А.Г., Гафаров Е.Р. Пособие по теории расписаний.<br />
* Vladimír Modrák, R. Sudhakara Pandian. FLOW SHOP SCHEDULING ALGORITHM TO MINIMIZE COMPLETION TIME FOR -JOBS -MACHINES PROBLEM<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Теория расписаний]]</div>Sergej Arkhipovhttp://neerc.ifmo.ru/wiki/index.php?title=Flow_shop&diff=47545Flow shop2015-06-05T10:27:43Z<p>Sergej Arkhipov: </p>
<hr />
<div>== Описание ==<br />
{{Определение<br />
|definition =<br />
'''Flow shop''' ('''<tex>F_{m}</tex>''' в нотации Грэхема): В системе находится <tex> m </tex> машин, работающих параллельно. Машины упорядочены. Каждая работа должна быть выполнена последовательно на всех машинах с первой по последнюю.}}<br />
<br />
Рассмотрим пример: <tex>F \mid p_{ij} = 1 \mid C_{max}</tex><br />
<br />
Допустим, у нас <tex>n</tex> работ и <tex>m</tex> машин. В начальный момент времени мы можем начать обрабатывать любую работу на первой машине. В следующий момент на первой машине можно обрабатывать следующую работу, а на второй перейдёт предыдущая работа с первой машины, и так далее. Таким образом, на выполнение всех работ у нас уйдёт <tex>n + m - 1</tex> единиц времени. Проиллюстрируем это диаграммой Гантта для случая <tex>n = 6, m = 5</tex>:<br />
'''0 1 2 3 4 5 6 7 8 9 10'''<br />
-------------------------------------------<br />
'''M_1''' | 1 2 3 4 5 6 - - - -<br />
'''M_2''' | - 1 2 3 4 5 6 - - -<br />
'''M_3''' | - - 1 2 3 4 5 6 - -<br />
'''M_4''' | - - - 1 2 3 4 5 6 -<br />
'''M_5''' | - - - - 1 2 3 4 5 6<br />
<br />
Заметим, что в данном случае <tex>p_{ij}</tex> может быть равно не только единице, но и любой константе.<br />
<br />
{{Утверждение<br />
|statement = Любая задача вида <tex>F \mid p_{ij} = 1 \mid ? </tex> сводится к соответствующей задаче вида <tex>1 \mid p_{ij} = 1 \mid ?</tex>. <br />
|proof = <br />
Поскольку работа всегда заканчивает выполняться на последней машине, нас интересуют только времена завершения работ на последней машине. Также очевидно, что последняя машина может начать работать только в момент времени <tex> m - 1 </tex>. Оказывается, что любое решение задачи <tex> 1 \mid p_{ij} = 1 \mid ? </tex> с дедлайнами, уменьшенными на <tex> m - 1 </tex> можно преобразовать в оптимальное расписание для задачи <tex>F \mid p_{ij} = 1 \mid ? </tex>. Докажем это.<br />
<br />
Возьмем оптимальное расписание для соответствующей задачи с одним станком, выполним работы в этом порядке на первой машине, затем на второй машине, начиная с момента времени <tex> 1 </tex>, и так далее, до выполнения на последней машине, начиная с <tex> m - 1 </tex>. Это расписание корректно и соблюдает все дедлайны. Поскольку целевая функция совпадает с соответствующей функцией для задачи на одном станке, оно оптимально и для данной задачи.<br />
}}<br />
<br />
Примером применения этого утверждения может служить следующая [[Fpij1sumwu|задача: <tex>F \mid p_{ij} = 1 \mid \sum w_iu_i</tex>]].<br />
<br />
Задачи с произвольными временами выполнения работ почти все являются NP-трудными.<br />
<br />
== Задача Джонсона о двух станках <tex>F_2 \mid \mid C_{max}</tex> ==<br />
<br />
Это единственная из flow shop задач с произвольными временами выполнения работ, которая решается за полиномиальное время.<br />
<br />
Приведём здесь решение задачи без доказательства, его можно посмотреть в [1].<br />
<br />
Оптимальное расписание для первой и второй машины будет совпадать. Таким образом, нам требуется найти порядок, в котором будут выполняться работы на каждой машине.<br />
<br />
Алгоритм такой: возьмём два пустых списка. Будем рассматривать работы в порядке возрастания <tex>min(p_1, p_2)</tex>, то есть, минимума из времён выполнения данной работы на первой и второй машине. Если у работы <tex>p_1 \le p_2</tex>, то добавим её в конец первого списка. В противном случае, добавим её в начало второго списка. Итоговое расписание — это конкатенация первого и второго списков.<br />
<br />
Псевдокод:<br />
J - множество работ<br />
Head <tex> \leftarrow \emptyset </tex><br />
Tail <tex> \leftarrow \emptyset </tex><br />
'''while''' J <tex> \ne \emptyset </tex> <br />
'''do'''<br />
I <tex> \leftarrow </tex> работа с минимальным значением <tex>min(p_1, p_2)</tex><br />
'''if''' <tex>p_1 <= p_2</tex> Head <tex> \leftarrow </tex> Head <tex>\circ</tex> I<br />
'''else''' Tail <tex> \leftarrow </tex> I <tex>\circ</tex> Tail<br />
J <tex> \leftarrow </tex> J <tex> \backslash </tex> I<br />
Result <tex> \leftarrow </tex> Head <tex>\circ</tex> Tail<br />
<br />
== Задача Джонсона о двух станках с прерываниями <tex>F_2 \mid pmtn \mid C_{max}</tex> ==<br />
<br />
Оптимальное решение этой задачи совпадает с решением задачи <tex>F_2 \mid \mid C_{max}</tex>, приведённой выше. Докажем это.<br />
<br />
Пусть у нас есть оптимальное расписание для задачи <tex>F_2 \mid pmtn \mid C_{max}</tex>. Покажем, что его за конечное число шагов можно преобразовать к расписанию без прерываний, не изменив при это значение <tex>C_{max}</tex> .<br />
<br />
Рассмотрим первую машину. Допустим, что некоторая работа <tex> J </tex> выполняется в <tex> 2 </tex> или более разных промежутка времени. Тогда передвинем более ранний промежуток вправо по оси времени так, чтоб он заканчивался в тот момент, когда начинается второй промежуток, при этом работы, которые были между этими двумя промежутками, сдвинем влево на длину первого промежутка. Расписание при этом осталось корректным, так как работы на машинах по-прежнему не пересекаются, и каждая работа на второй машине делается после того, как она сделана на первой: работа <tex> J </tex> может начать выполняться на второй машине только после того, как она целиком выполнится на первой, то есть уже после конца второго промежутка; а время окончания выполнения остальных работ на первой машине неувеличилось.<br />
Важно, что подобная операция не увеличивает <tex> C_{max} </tex>.<br />
<br />
Будем повторять эту операцию до тех пор, пока на первой машине все работы не станут выполняться без прерываний. Так как количество прерываний конечно, а такая операция уменьшает их количество на один, этот процесс конечен.<br />
<br />
Теперь избавимся от прерываний на второй машине. Точно так же рассмотрим работу, разбитую на два или более промежутка. Передвинем более поздний промежуток к концу более раннего, а работы между ними сдвинем вправо. Доказательство корректности измененного расписания аналогично доказательству для первой машины. Будем повторять данную операцию, пока на второй машине присутствуют прерывания.<br />
<br />
Таким образом, мы получили корректное расписание без прерываний, не изменив при этом значение <tex>C_{max}</tex>, что и требовалось доказать.<br />
<br />
== См. также ==<br />
* [[Классификация задач]]<br />
* [[Fpij1sumwu|<tex>F \mid p_{ij} = 1 \mid \sum w_i u_i</tex>]]<br />
<br />
== Литература ==<br />
*[1][http://books.google.ru/books?id=FrUytMqlCv8C&printsec=frontcover&dq=scheduling+algorithms&hl=ru&sa=X&ei=0MPMT4HqKYSk4gSBm6gp&sqi=2&ved=0CDEQ6AEwAA#v=onepage&q=scheduling%20algorithms&f=false Scheduling Algorithms, Peter Brucker]</div>Sergej Arkhipovhttp://neerc.ifmo.ru/wiki/index.php?title=1ripi1sumwc&diff=475391ripi1sumwc2015-06-05T09:45:17Z<p>Sergej Arkhipov: /* Вариант 2 */</p>
<hr />
<div><tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum w_i C_i</tex><br />
<br />
{{Задача<br />
|definition=<br />
Дано <tex>n</tex> работ и один станок. Для каждой работы известно её время появления <tex>r_{i}</tex> и вес <tex>w_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>. Требуется выполнить все работы, чтобы значение <tex>\sum w_{i} C_{i}</tex> было минимальным, где <tex>C_{i}</tex> {{---}} время окончания работы.<br />
}}<br />
<br />
==Более простые варианты исходной задачи==<br />
<br />
Перед решением основной задачи рассмотрим более простые.<br />
<br />
===Вариант 1===<br />
<tex> 1 \mid p_i = 1\mid \sum C_i</tex><br />
<br />
Этот случай простейший. Ответом будет <tex>\sum\limits_{k = 1}^n(k)</tex>, так как мы <tex>n</tex> раз сложим время окончания выполнения одной работы. Воспользовавшись формулой суммы первых <tex>n</tex> членов арифметической прогрессии алгоритм <tex>S_n=\frac{a_1+a_n}2 \cdot n</tex> будет работает за <tex>O(1)</tex>, но если нужно вывести и само расписание время работы будет <tex>O(n)</tex>.<br />
<br />
===Вариант 2===<br />
<tex> 1 \mid p_i = 1\mid \sum w_i C_i</tex><br />
<br />
Для верного выполнения просто выставим работы по порядку невозрастания весов, тогда ответом будет <tex> \sum\limits_{i = 1}^n(w_i C_i)</tex>, так как мы <tex>n</tex> раз сложим время окончания выполнения одной работы (которое в нашем случае <tex>C_{i-1}+1</tex>) домноженное на вес этой работы. <br />
<br />
Данный алгоритм корректен по [[Задача_о_минимуме/максимуме_скалярного_произведения|теореме о минимуме/максимуме скалярного произведения]], так как мы сопоставляем две последовательности подходящие под условия теоремы. <br />
<br />
Вес работ [[Сортировка|отсортировали]] за <tex>O(n \log n)</tex>. Алгоритм работает за <tex>O(n + n \log n)</tex><br />
<br />
===Вариант 3===<br />
<tex> 1 \mid r_i,p_i = 1 \mid \sum f_i</tex><br />
<br />
<tex>f_{i}</tex> {{---}} монотонная функция времени окончания работы <tex>C_{i}</tex> для работ <tex>i = 1, 2, \ldots , n</tex>.<br />
<br />
<br />
Нам нужно распределить <tex>n</tex> работ в разное время. Если мы назначим время <tex>t</tex> для работы <tex>i</tex> то цена будет <tex>f_i(t + 1)</tex>. Функция <tex>f_i</tex> монотонно неубывающая, тогда работы в расписании надо располагать как можно раньше для получения верного решения. <tex>n</tex> временных интервалов <tex>t_i</tex> для <tex>n</tex> работ могут быть получены с помощью следующего алгоритма, где предполагается что работы отсортированы так:<br />
<br />
<tex> r_1 \leqslant r_2 \leqslant \ldots \leqslant r_n</tex> <br />
<br />
'''Псевдокод'''<br />
<br />
<tex>t_1 \leftarrow r_1 </tex><br />
'''for''' <tex> i \leftarrow 2</tex> '''to''' <tex>n</tex> '''do'''<br />
<tex> t_i \leftarrow </tex> '''max'''<tex>(r_i, \ t_{i-1} - 1)</tex><br />
<br />
Этот алгоритм работает за <tex>O(n \log n +n)</tex><br />
==Основная задача== <br />
===Описание алгоритма===<br />
Пусть <tex>time</tex> {{---}} текущий момент времени.<br/><br />
Для каждого очередного значения <tex>time</tex>, которое изменяется от <tex>0</tex> до времени окончания последней работы, будем:<br />
<ol><br />
<li> Выбирать работу <tex>j</tex> из множества невыполненных работ, у которой <tex>r_{i} \leqslant time</tex>, а значение <tex>w_{i}</tex> максимально.</li><br />
<li> Если мы смогли найти работу <tex>j</tex>, то выполняем её в момент времени <tex>time</tex> и удаляем из множества невыполненных работ.</li><br />
<li> Увеличиваем <tex>time</tex> на один.</li><br />
</ol><br />
<br />
===Доказательство корректности алгоритма===<br />
{{Теорема<br />
|statement=<br />
Расписание, построенное данным алгоритмом, является корректным и оптимальным.<br />
|proof=<br />
Доказательство будем вести от противного.<br/><br />
Рассмотрим расписание <tex>S_{1}</tex>, полученное после выполнения нашего алгоритма, и оптимальное расписание <tex>S_{2}</tex>.<br/><br />
Возьмём первый момент времени <tex>t_{1}</tex>, когда расписания различаются. Пусть в этот момент времени в <tex>S_{1}</tex>, будет выполняться работа с весом <tex>w_{1}</tex>, а в <tex>S_{2}</tex> {{---}} работа с весом <tex>w_{2}</tex>.<br/><br />
Это первый момент, в котором расписания отличаются, значит в <tex>S_{2}</tex> работа с весом <tex>w_{1}</tex> выполнится в момент времени <tex>t_{2} > t_{1}</tex>.<br/><br />
Поменяем местами работы с весами <tex>w_{1}</tex> и <tex>w_{2}</tex> в <tex>S_{2}</tex> и полуим расписание <tex>S_{3}</tex>. Это возможно, потому что время появления этих работ не меньше <tex>t_{1}</tex>.<br/><br />
При такой перестановке ответы на задачу для <tex>S_{2}</tex> и <tex>S_{3}</tex> будут отличаться на <br />
<ul><tex>t_{1}w_{2} + t_{2}w_{1} - t_{1}w_{1} + t_{2}w_{2} = t_{1}(w_{2} - w_{1}) + t_{2}(w_{1} - w_{2}) = (t_{1} - t_{2})(w_{2} - w_{1})</tex></ul><br />
Первая скобка отрицательная: <tex>t_{1} < t_{2}</tex>. Вторая скобка тоже отрицательная из того, что в <tex>S_{1}</tex> работа с весом <tex>w_1</tex> выполняется раньше, значит её вес должен быть больше <tex>w_2</tex>.<br/><br />
Итого имеем, что ответ для <tex>S_{2}</tex> больше, чем ответ для <tex>S_{3}</tex>. Следовательно расписание <tex>S_2</tex> неоптимальное. Получили противоречие. Значит не существует такого момента времени, когда расписание <tex>S_{1}</tex> отличается от оптимального. Следовательно мы доказали, что оно оптимальное.<br />
}}<br />
<br />
===Псевдокод===<br />
<br />
====Реализация 1====<br />
<tex> S \leftarrow \{1 \ldots n\}</tex><br />
<tex> \mathtt{time} \leftarrow 0</tex><br />
<tex> \mathtt{answer} \leftarrow 0</tex><br />
'''while''' <tex> S \neq \varnothing </tex><br />
<tex> j \leftarrow null </tex><br />
'''if''' <tex> i \in S</tex> '''and''' <tex> r_{i} \leqslant \mathtt{time}</tex> '''and''' <tex>w_i \geqslant \max\limits_{j \in S, j = 1 \ldots n} w_j</tex><br />
<tex> j \leftarrow i </tex><br />
'''if''' <tex>j \neq null </tex><br />
<tex> S \leftarrow S \setminus j</tex><br />
<tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot w_{j}</tex><br />
<tex> \mathtt{time++}</tex><br />
<br />
Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \max\limits_{i = 1 \ldots n} r_{i}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, [[:Категория:Приоритетные_очереди|очередь с приоритетами]]. Значит общее время работы алгоритма <tex>O((n + \max\limits_{i = 1 \ldots n} r_{i})\log n)</tex><br />
<br />
====Реализация 2====<br />
Перед началом алгоритма [[Сортировка|отсортируем]] работы по порядку неубывания веса.<br />
<tex> \mathtt{time} \leftarrow r_1</tex><br />
<tex> \mathtt{answer} \leftarrow 0</tex><br />
'''for''' <tex>i \leftarrow 1 </tex> '''to''' <tex>n</tex> '''do'''<br />
'''if''' <tex> r_{i} \leqslant \mathtt{time}</tex><br />
<tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot w_{i}</tex><br />
'''else'''<br />
<tex> \mathtt{time} \leftarrow r_i</tex><br />
<tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot w_{i}</tex><br />
<br />
В начале алгоритма сортируем работы <tex>O(n \log n)</tex> времени. Затем мы тратим <tex>O(n)</tex> на получение ответа. Тогда суммарное время работы алгоритма составит <tex>O(n \log n + n )</tex> что есть <tex>O(n (\log n + 1))</tex> времени.<br />
<br />
==См. также==<br />
* [[Классификация задач]]<br />
* [[1outtreesumwc|<tex>1 \mid outtree \mid \sum w_i C_i</tex>]]<br />
* [[1ridipi1|<tex>1 | r_{i}, d_{i}, p_{i}=1 | -</tex>]]<br />
<br />
==Источники информации==<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 19-20<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 38-39<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 84-85<br />
* Лазарев А.А., Мусатова Е.Г., Кварацхелия А.Г., Гафаров Е.Р. Пособие по теории расписаний.<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Теория расписаний]]</div>Sergej Arkhipovhttp://neerc.ifmo.ru/wiki/index.php?title=1ripi1sumwc&diff=473651ripi1sumwc2015-06-03T20:40:03Z<p>Sergej Arkhipov: </p>
<hr />
<div><tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum w_i C_i</tex><br />
<br />
{{Задача<br />
|definition=<br />
Дано <tex>n</tex> работ и один станок. Для каждой работы известно её время появления <tex>r_{i}</tex> и вес <tex>w_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>. Требуется выполнить все работы, чтобы значение <tex>\sum w_{i} C_{i}</tex> было минимальным, где <tex>C_{i}</tex> {{---}} время окончания работы.<br />
}}<br />
<br />
==Более простые варианты исходной задачи==<br />
<br />
Перед решением основной задачи рассмотрим более простые.<br />
<br />
===Вариант 1===<br />
<tex> 1 \mid p_i = 1\mid \sum C_i</tex><br />
<br />
Этот случай простейший. Ответом будет <tex>\sum\limits_{k = 1}^n(k)</tex>, так как мы <tex>n</tex> раз сложим время окончания выполнения одной работы. Воспользовавшись формулой суммы первых <tex>n</tex> членов арифметической прогрессии алгоритм <tex>S_n=\frac{a_1+a_n}2 \cdot n</tex> будет работает за <tex>O(1)</tex>, но если нужно вывести и само расписание время работы будет <tex>O(n)</tex>.<br />
<br />
===Вариант 2===<br />
<tex> 1 \mid p_i = 1\mid \sum w_i C_i</tex><br />
<br />
Для верного выполнения просто выставим работы по порядку невозрастания весов, тогда ответом будет <tex> \sum\limits_{i = 1}^n(w_i C_i)</tex>, так как мы <tex>n</tex> раз сложим время окончания выполнения одной работы (которое в нашем случае <tex>C_{i-1}+1</tex>) домноженное на вес этой работы. <br />
<br />
Покажем что алгоритм [[Методы_решения_задач_теории_расписаний|жадного построения расписания]] корректен. <tex>w_i C_i \geqslant w_j C_j</tex>, где <tex>w_i C_i</tex> произведение на текущем шаге до сортировки, а <tex>w_j C_j</tex> после. Полученное произведение <tex>w_j C_j</tex> «более похоже» на оптимальное, чем произведение <tex>w_i C_i</tex>. Тогда применение жадного алгоритма дает верный ответ.<br />
<br />
Вес работ [[Сортировка|отсортировали]] за <tex>O(n \log n)</tex>. Алгоритм работает за <tex>O(n + n \log n)</tex> <br />
<br />
===Вариант 3===<br />
<tex> 1 \mid r_i,p_i = 1 \mid \sum f_i</tex><br />
<br />
<tex>f_{i}</tex> {{---}} монотонная функция времени окончания работы <tex>C_{i}</tex> для работ <tex>i = 1, 2, \ldots , n</tex>.<br />
<br />
<br />
Нам нужно распределить <tex>n</tex> работ в разное время. Если мы назначим время <tex>t</tex> для работы <tex>i</tex> то цена будет <tex>f_i(t + 1)</tex>. Функция <tex>f_i</tex> монотонно неубывающая, тогда работы в расписании надо располагать как можно раньше для получения верного решения. <tex>n</tex> временных интервалов <tex>t_i</tex> для <tex>n</tex> работ могут быть получены с помощью следующего алгоритма, где предполагается что работы отсортированы так:<br />
<br />
<tex> r_1 \leqslant r_2 \leqslant \ldots \leqslant r_n</tex> <br />
<br />
'''Псевдокод'''<br />
<br />
<tex>t_1 \leftarrow r_1 </tex><br />
'''for''' <tex> i \leftarrow 2</tex> '''to''' <tex>n</tex> '''do'''<br />
<tex> t_i \leftarrow </tex> '''max'''<tex>(r_i, \ t_{i-1} - 1)</tex><br />
<br />
Этот алгоритм работает за <tex>O(n \log n +n)</tex><br />
==Основная задача== <br />
===Описание алгоритма===<br />
Пусть <tex>time</tex> {{---}} текущий момент времени.<br/><br />
Для каждого очередного значения <tex>time</tex>, которое изменяется от <tex>0</tex> до времени окончания последней работы, будем:<br />
<ol><br />
<li> Выбирать работу <tex>j</tex> из множества невыполненных работ, у которой <tex>r_{i} \leqslant time</tex>, а значение <tex>w_{i}</tex> максимально.</li><br />
<li> Если мы смогли найти работу <tex>j</tex>, то выполняем её в момент времени <tex>time</tex> и удаляем из множества невыполненных работ.</li><br />
<li> Увеличиваем <tex>time</tex> на один.</li><br />
</ol><br />
<br />
===Доказательство корректности алгоритма===<br />
{{Теорема<br />
|statement=<br />
Расписание, построенное данным алгоритмом, является корректным и оптимальным.<br />
|proof=<br />
Доказательство будем вести от противного.<br/><br />
Рассмотрим расписание <tex>S_{1}</tex>, полученное после выполнения нашего алгоритма, и оптимальное расписание <tex>S_{2}</tex>.<br/><br />
Возьмём первый момент времени <tex>t_{1}</tex>, когда расписания различаются. Пусть в этот момент времени в <tex>S_{1}</tex>, будет выполняться работа с весом <tex>w_{1}</tex>, а в <tex>S_{2}</tex> {{---}} работа с весом <tex>w_{2}</tex>.<br/><br />
Это первый момент, в котором расписания отличаются, значит в <tex>S_{2}</tex> работа с весом <tex>w_{1}</tex> выполнится в момент времени <tex>t_{2} > t_{1}</tex>.<br/><br />
Поменяем местами работы с весами <tex>w_{1}</tex> и <tex>w_{2}</tex> в <tex>S_{2}</tex> и полуим расписание <tex>S_{3}</tex>. Это возможно, потому что время появления этих работ не меньше <tex>t_{1}</tex>.<br/><br />
При такой перестановке ответы на задачу для <tex>S_{2}</tex> и <tex>S_{3}</tex> будут отличаться на <br />
<ul><tex>t_{1}w_{2} + t_{2}w_{1} - t_{1}w_{1} + t_{2}w_{2} = t_{1}(w_{2} - w_{1}) + t_{2}(w_{1} - w_{2}) = (t_{1} - t_{2})(w_{2} - w_{1})</tex></ul><br />
Первая скобка отрицательная: <tex>t_{1} < t_{2}</tex>. Вторая скобка тоже отрицательная из того, что в <tex>S_{1}</tex> работа с весом <tex>w_1</tex> выполняется раньше, значит её вес должен быть больше <tex>w_2</tex>.<br/><br />
Итого имеем, что ответ для <tex>S_{2}</tex> больше, чем ответ для <tex>S_{3}</tex>. Следовательно расписание <tex>S_2</tex> неоптимальное. Получили противоречие. Значит не существует такого момента времени, когда расписание <tex>S_{1}</tex> отличается от оптимального. Следовательно мы доказали, что оно оптимальное.<br />
}}<br />
<br />
===Псевдокод===<br />
<br />
====Реализация 1====<br />
<tex> S \leftarrow \{1 \ldots n\}</tex><br />
<tex> \mathtt{time} \leftarrow 0</tex><br />
<tex> \mathtt{answer} \leftarrow 0</tex><br />
'''while''' <tex> S \neq \varnothing </tex><br />
<tex> j \leftarrow null </tex><br />
'''if''' <tex> i \in S</tex> '''and''' <tex> r_{i} \leqslant \mathtt{time}</tex> '''and''' <tex>w_i \geqslant \max\limits_{j \in S, j = 1 \ldots n} w_j</tex><br />
<tex> j \leftarrow i </tex><br />
'''if''' <tex>j \neq null </tex><br />
<tex> S \leftarrow S \setminus j</tex><br />
<tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot w_{j}</tex><br />
<tex> \mathtt{time++}</tex><br />
<br />
Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \max\limits_{i = 1 \ldots n} r_{i}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, [[:Категория:Приоритетные_очереди|очередь с приоритетами]]. Значит общее время работы алгоритма <tex>O((n + \max\limits_{i = 1 \ldots n} r_{i})\log n)</tex><br />
<br />
====Реализация 2====<br />
Перед началом алгоритма [[Сортировка|отсортируем]] работы по порядку неубывания веса.<br />
<tex> \mathtt{time} \leftarrow r_1</tex><br />
<tex> \mathtt{answer} \leftarrow 0</tex><br />
'''for''' <tex>i \leftarrow 1 </tex> '''to''' <tex>n</tex> '''do'''<br />
'''if''' <tex> r_{i} \leqslant \mathtt{time}</tex><br />
<tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot w_{i}</tex><br />
'''else'''<br />
<tex> \mathtt{time} \leftarrow r_i</tex><br />
<tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot w_{i}</tex><br />
<br />
В начале алгоритма сортируем работы <tex>O(n \log n)</tex> времени. Затем мы тратим <tex>O(n)</tex> на получение ответа. Тогда суммарное время работы алгоритма составит <tex>O(n \log n + n )</tex> что есть <tex>O(n (\log n + 1))</tex> времени.<br />
<br />
==См. также==<br />
* [[Классификация задач]]<br />
* [[1outtreesumwc|<tex>1 \mid outtree \mid \sum w_i C_i</tex>]]<br />
* [[1ridipi1|<tex>1 | r_{i}, d_{i}, p_{i}=1 | -</tex>]]<br />
<br />
==Источники информации==<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 19-20<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 38-39<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 84-85<br />
* Лазарев А.А., Мусатова Е.Г., Кварацхелия А.Г., Гафаров Е.Р. Пособие по теории расписаний.<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Теория расписаний]]</div>Sergej Arkhipovhttp://neerc.ifmo.ru/wiki/index.php?title=1ripi1sumwc&diff=473551ripi1sumwc2015-06-03T19:37:00Z<p>Sergej Arkhipov: </p>
<hr />
<div><tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum w_i C_i</tex><br />
<br />
{{Задача<br />
|definition=<br />
Дано <tex>n</tex> работ и один станок. Для каждой работы известно её время появления <tex>r_{i}</tex> и вес <tex>w_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>. Требуется выполнить все работы, чтобы значение <tex>\sum w_{i} C_{i}</tex> было минимальным, где <tex>C_{i}</tex> {{---}} время окончания работы.<br />
}}<br />
<br />
==Более простые варианты исходной задачи==<br />
<br />
Перед решением основной задачи рассмотрим более простые.<br />
<br />
===Вариант 1===<br />
<tex> 1 \mid p_i = 1\mid \sum C_i</tex><br />
<br />
Этот случай простейший. Ответом будет <tex>\sum\limits_{k = 1}^n(k)</tex>, так как мы <tex>n</tex> раз сложим время окончания выполнения одной работы. Воспользовавшись формулой суммы первых <tex>n</tex> членов арифметической прогрессии алгоритм <tex>S_n=\frac{a_1+a_n}2 \cdot n</tex> будет работает за <tex>O(1)</tex>, но если нужно вывести и само расписание время работы будет <tex>O(n)</tex>.<br />
<br />
===Вариант 2===<br />
<tex> 1 \mid p_i = 1\mid \sum w_i C_i</tex><br />
<br />
Для верного выполнения просто выставим работы по порядку невозрастания весов, тогда ответом будет <tex> \sum\limits_{i = 1}^n(w_i C_i)</tex>, так как мы <tex>n</tex> раз сложим время окончания выполнения одной работы (которое в нашем случае <tex>C_{i-1}+1</tex>) домноженное на вес этой работы. То есть решаем жадным алгоритмом: на каждом шаге получаем оптимальное решение и в результате верный ответ. Вес работ [[Сортировка|отсортировали]] за <tex>O(n \log n)</tex>. Алгоритм работает за <tex>O(n + n \log n)</tex> <br />
<br />
===Вариант 3===<br />
<tex> 1 \mid r_i,p_i = 1 \mid \sum f_i</tex><br />
<br />
<tex>f_{i}</tex> {{---}} монотонная функция времени окончания работы <tex>C_{i}</tex> для работ <tex>i = 1, 2, \ldots , n</tex>.<br />
<br />
<br />
Нам нужно распределить <tex>n</tex> работ в разное время. Если мы назначим время <tex>t</tex> для работы <tex>i</tex> то цена будет <tex>f_i(t + 1)</tex>. Функция <tex>f_i</tex> монотонно неубывающая, тогда работы в расписании надо располагать как можно раньше для получения верного решения. <tex>n</tex> временных интервалов <tex>t_i</tex> для <tex>n</tex> работ могут быть получены с помощью следующего алгоритма, где предполагается что работы отсортированы так:<br />
<br />
<tex> r_1 \leqslant r_2 \leqslant \ldots \leqslant r_n</tex> <br />
<br />
'''Псевдокод'''<br />
<br />
<tex>t_1 \leftarrow r_1 </tex><br />
'''for''' <tex> i \leftarrow 2</tex> '''to''' <tex>n</tex> '''do'''<br />
<tex> t_i \leftarrow </tex> '''max'''<tex>(r_i, \ t_{i-1} - 1)</tex><br />
<br />
Этот алгоритм работает за <tex>O(n \log n +n)</tex><br />
==Основная задача== <br />
===Описание алгоритма===<br />
Пусть <tex>time</tex> {{---}} текущий момент времени.<br/><br />
Для каждого очередного значения <tex>time</tex>, которое изменяется от <tex>0</tex> до времени окончания последней работы, будем:<br />
<ol><br />
<li> Выбирать работу <tex>j</tex> из множества невыполненных работ, у которой <tex>r_{i} \leqslant time</tex>, а значение <tex>w_{i}</tex> максимально.</li><br />
<li> Если мы смогли найти работу <tex>j</tex>, то выполняем её в момент времени <tex>time</tex> и удаляем из множества невыполненных работ.</li><br />
<li> Увеличиваем <tex>time</tex> на один.</li><br />
</ol><br />
<br />
===Доказательство корректности алгоритма===<br />
{{Теорема<br />
|statement=<br />
Расписание, построенное данным алгоритмом, является корректным и оптимальным.<br />
|proof=<br />
Доказательство будем вести от противного.<br/><br />
Рассмотрим расписание <tex>S_{1}</tex>, полученное после выполнения нашего алгоритма, и оптимальное расписание <tex>S_{2}</tex>.<br/><br />
Возьмём первый момент времени <tex>t_{1}</tex>, когда расписания различаются. Пусть в этот момент времени в <tex>S_{1}</tex>, будет выполняться работа с весом <tex>w_{1}</tex>, а в <tex>S_{2}</tex> {{---}} работа с весом <tex>w_{2}</tex>.<br/><br />
Это первый момент, в котором расписания отличаются, значит в <tex>S_{2}</tex> работа с весом <tex>w_{1}</tex> выполнится в момент времени <tex>t_{2} > t_{1}</tex>.<br/><br />
Поменяем местами работы с весами <tex>w_{1}</tex> и <tex>w_{2}</tex> в <tex>S_{2}</tex> и полуим расписание <tex>S_{3}</tex>. Это возможно, потому что время появления этих работ не меньше <tex>t_{1}</tex>.<br/><br />
При такой перестановке ответы на задачу для <tex>S_{2}</tex> и <tex>S_{3}</tex> будут отличаться на <br />
<ul><tex>t_{1}w_{2} + t_{2}w_{1} - t_{1}w_{1} + t_{2}w_{2} = t_{1}(w_{2} - w_{1}) + t_{2}(w_{1} - w_{2}) = (t_{1} - t_{2})(w_{2} - w_{1})</tex></ul><br />
Первая скобка отрицательная: <tex>t_{1} < t_{2}</tex>. Вторая скобка тоже отрицательная из того, что в <tex>S_{1}</tex> работа с весом <tex>w_1</tex> выполняется раньше, значит её вес должен быть больше <tex>w_2</tex>.<br/><br />
Итого имеем, что ответ для <tex>S_{2}</tex> больше, чем ответ для <tex>S_{3}</tex>. Следовательно расписание <tex>S_2</tex> неоптимальное. Получили противоречие. Значит не существует такого момента времени, когда расписание <tex>S_{1}</tex> отличается от оптимального. Следовательно мы доказали, что оно оптимальное.<br />
}}<br />
<br />
===Псевдокод===<br />
<br />
====Реализация 1====<br />
<tex> S \leftarrow \{1 \ldots n\}</tex><br />
<tex> \mathtt{time} \leftarrow 0</tex><br />
<tex> \mathtt{answer} \leftarrow 0</tex><br />
'''while''' <tex> S \neq \varnothing </tex><br />
<tex> j \leftarrow null </tex><br />
'''if''' <tex> i \in S</tex> '''and''' <tex> r_{i} \leqslant \mathtt{time}</tex> '''and''' <tex>w_i \geqslant \max\limits_{j \in S, j = 1 \ldots n} w_j</tex><br />
<tex> j \leftarrow i </tex><br />
'''if''' <tex>j \neq null </tex><br />
<tex> S \leftarrow S \setminus j</tex><br />
<tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot w_{j}</tex><br />
<tex> \mathtt{time++}</tex><br />
<br />
Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \max\limits_{i = 1 \ldots n} r_{i}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, [[:Категория:Приоритетные_очереди|очередь с приоритетами]]. Значит общее время работы алгоритма <tex>O((n + \max\limits_{i = 1 \ldots n} r_{i})\log n)</tex><br />
<br />
====Реализация 2====<br />
Перед началом алгоритма [[Сортировка|отсортируем]]работы по порядку неубывания веса.<br />
<tex> \mathtt{time} \leftarrow r_1</tex><br />
<tex> \mathtt{answer} \leftarrow 0</tex><br />
'''for''' <tex>i \leftarrow 1 </tex> '''to''' <tex>n</tex> '''do'''<br />
'''if''' <tex> r_{i} \leqslant \mathtt{time}</tex><br />
<tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot w_{i}</tex><br />
'''else'''<br />
<tex> \mathtt{time} \leftarrow r_i</tex><br />
<tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot w_{i}</tex><br />
<br />
В начале алгоритма сортируем работы <tex>O(n \log n)</tex> времени. Затем мы тратим <tex>O(n)</tex> на получение ответа. Тогда суммарное время работы алгоритма составит <tex>O(n \log n + n )</tex> что есть <tex>O(n (\log n + 1))</tex> времени.<br />
<br />
==См. также==<br />
* [[Классификация задач]]<br />
* [[1outtreesumwc|<tex>1 \mid outtree \mid \sum w_i C_i</tex>]]<br />
* [[1ridipi1|<tex>1 | r_{i}, d_{i}, p_{i}=1 | -</tex>]]<br />
<br />
==Источники информации==<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 19-20<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 38-39<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 84-85<br />
* Лазарев А.А., Мусатова Е.Г., Кварацхелия А.Г., Гафаров Е.Р. Пособие по теории расписаний.<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Теория расписаний]]</div>Sergej Arkhipovhttp://neerc.ifmo.ru/wiki/index.php?title=1ripi1sumwc&diff=473351ripi1sumwc2015-06-03T17:40:51Z<p>Sergej Arkhipov: </p>
<hr />
<div><tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum w_i C_i</tex><br />
<br />
{{Задача<br />
|definition=<br />
Дано <tex>n</tex> работ и один станок. Для каждой работы известно её время появления <tex>r_{i}</tex> и вес <tex>w_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>. Требуется выполнить все работы, чтобы значение <tex>\sum w_{i} C_{i}</tex> было минимальным, где <tex>C_{i}</tex> {{---}} время окончания работы.<br />
}}<br />
<br />
==Более простые варианты исходной задачи==<br />
<br />
Перед решением основной задачи рассмотрим более простые.<br />
<br />
===Вариант 1===<br />
<tex> 1 \mid p_i = 1\mid \sum C_i</tex><br />
<br />
Этот случай простейший. Ответом будет <tex>\sum\limits_{k = 1}^n(k)</tex>, так как мы <tex>n</tex> раз сложим время окончания выполнения одной работы. Воспользовавшись формулой суммы первых <tex>n</tex> членов арифметической прогрессии алгоритм <tex>S_n=\frac{a_1+a_n}2 \cdot n</tex> будет работает за <tex>O(1)</tex>.<br />
<br />
===Вариант 2===<br />
<tex> 1 \mid p_i = 1\mid \sum w_i C_i</tex><br />
<br />
Для верного выполнения просто выставим работы по порядку невозрастания весов, тогда ответом будет <tex> \sum\limits_{i = 1}^n(w_i C_i)</tex>, так как мы <tex>n</tex> раз сложим время окончания выполнения одной работы (которое в нашем случае <tex>C_{i-1}+1</tex>) домноженное на вес этой работы. Вес работ [[Сортировка|отсортировали]] за <tex>O(n \log n)</tex>. Алгоритм работает за <tex>O(n + n \log n)</tex> <br />
<br />
===Вариант 3===<br />
<tex> 1 \mid r_i,p_i = 1 \mid \sum f_i</tex><br />
<br />
<tex>f_{i}</tex> {{---}} монотонная функция времени окончания работы <tex>C_{i}</tex> для работ <tex>i = 1, 2, \ldots , n</tex>.<br />
<br />
<br />
Нам нужно распределить <tex>n</tex> работ в разное время. Если мы назначим время <tex>t</tex> для работы <tex>i</tex> то цена будет <tex>f_i(t + 1)</tex>. Функция <tex>f_i</tex> монотонно неубывающая, тогда работы в расписании надо располагать как можно раньше для получения верного решения. <tex>n</tex> временных интервалов <tex>t_i</tex> для <tex>n</tex> работ могут быть получены с помощью следующего алгоритма, где предполагается что работы отсортированы так:<br />
<br />
<tex> r_1 \leqslant r_2 \leqslant \ldots \leqslant r_n</tex> <br />
<br />
'''Псевдокод'''<br />
<br />
<tex>t_1 \leftarrow r_1 </tex><br />
'''for''' <tex> i \leftarrow 2</tex> '''to''' <tex>n</tex> '''do'''<br />
<tex> t_i \leftarrow </tex> '''max'''<tex>(r_i, \ t_{i-1} - 1)</tex><br />
<br />
Этот алгоритм работает за <tex>O(n \log n +n)</tex><br />
==Основная задача== <br />
===Описание алгоритма===<br />
Пусть <tex>time</tex> {{---}} текущий момент времени.<br/><br />
Для каждого очередного значения <tex>time</tex>, которое изменяется от <tex>0</tex> до времени окончания последней работы, будем:<br />
<ol><br />
<li> Выбирать работу <tex>j</tex> из множества невыполненных работ, у которой <tex>r_{i} \leqslant time</tex>, а значение <tex>w_{i}</tex> максимально.</li><br />
<li> Если мы смогли найти работу <tex>j</tex>, то выполняем её в момент времени <tex>time</tex> и удаляем из множества невыполненных работ.</li><br />
<li> Увеличиваем <tex>time</tex> на один.</li><br />
</ol><br />
<br />
===Доказательство корректности алгоритма===<br />
{{Теорема<br />
|statement=<br />
Расписание, построенное данным алгоритмом, является корректным и оптимальным.<br />
|proof=<br />
Доказательство будем вести от противного.<br/><br />
Рассмотрим расписание <tex>S_{1}</tex>, полученное после выполнения нашего алгоритма, и оптимальное расписание <tex>S_{2}</tex>.<br/><br />
Возьмём первый момент времени <tex>t_{1}</tex>, когда расписания различаются. Пусть в этот момент времени в <tex>S_{1}</tex>, будет выполняться работа с весом <tex>w_{1}</tex>, а в <tex>S_{2}</tex> {{---}} работа с весом <tex>w_{2}</tex>.<br/><br />
Это первый момент, в котором расписания отличаются, значит в <tex>S_{2}</tex> работа с весом <tex>w_{1}</tex> выполнится в момент времени <tex>t_{2} > t_{1}</tex>.<br/><br />
Поменяем местами работы с весами <tex>w_{1}</tex> и <tex>w_{2}</tex> в <tex>S_{2}</tex> и полуим расписание <tex>S_{3}</tex>. Это возможно, потому что время появления этих работ не меньше <tex>t_{1}</tex>.<br/><br />
При такой перестановке ответы на задачу для <tex>S_{2}</tex> и <tex>S_{3}</tex> будут отличаться на <br />
<ul><tex>t_{1}w_{2} + t_{2}w_{1} - t_{1}w_{1} + t_{2}w_{2} = t_{1}(w_{2} - w_{1}) + t_{2}(w_{1} - w_{2}) = (t_{1} - t_{2})(w_{2} - w_{1})</tex></ul><br />
Первая скобка отрицательная: <tex>t_{1} < t_{2}</tex>. Вторая скобка тоже отрицательная из того, что в <tex>S_{1}</tex> работа с весом <tex>w_1</tex> выполняется раньше, значит её вес должен быть больше <tex>w_2</tex>.<br/><br />
Итого имеем, что ответ для <tex>S_{2}</tex> больше, чем ответ для <tex>S_{3}</tex>. Следовательно расписание <tex>S_2</tex> неоптимальное. Получили противоречие. Значит не существует такого момента времени, когда расписание <tex>S_{1}</tex> отличается от оптимального. Следовательно мы доказали, что оно оптимальное.<br />
}}<br />
<br />
===Псевдокод===<br />
<br />
====Реализация 1====<br />
<tex> S \leftarrow \{1 \ldots n\}</tex><br />
<tex> \mathtt{time} \leftarrow 0</tex><br />
<tex> \mathtt{answer} \leftarrow 0</tex><br />
'''while''' <tex> S \neq \varnothing </tex><br />
<tex> j \leftarrow null </tex><br />
'''if''' <tex> i \in S</tex> '''and''' <tex> r_{i} \leqslant \mathtt{time}</tex> '''and''' <tex>w_i \geqslant \max\limits_{j \in S, j = 1 \ldots n} w_j</tex><br />
<tex> j \leftarrow i </tex><br />
'''if''' <tex>j \neq null </tex><br />
<tex> S \leftarrow S \setminus j</tex><br />
<tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot w_{j}</tex><br />
<tex> \mathtt{time++}</tex><br />
<br />
====Реализация 2====<br />
Эта реализация использует [[Двоичная_куча|двоичную кучу]] <tex>\mathtt{Heap}</tex> в которой операции вставки и извлечения выполняются за <tex>O(\log n)</tex>, а операция поиска максимального элемента за <tex>O(1)</tex><br />
<tex> S \leftarrow \{1 \ldots n\}</tex><br />
<tex> \mathtt{time} \leftarrow 0</tex><br />
<tex> \mathtt{answer} \leftarrow 0</tex><br />
'''for''' <tex>i \leftarrow 1 </tex> '''to''' <tex>n</tex> '''do'''<br />
Heap.insert(<tex>w_i</tex>)<br />
'''while''' <tex> S \neq \varnothing </tex><br />
<tex> j \leftarrow null </tex><br />
'''if''' <tex> i \in S</tex> '''and''' <tex> r_{i} \leqslant \mathtt{time}</tex> '''and''' <tex>w_i \geqslant </tex> Heap.Max()<br />
<tex> j \leftarrow i </tex><br />
'''if''' <tex>j \neq null </tex><br />
<tex> S \leftarrow S \setminus j</tex><br />
Heap.extractMax()<br />
<tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot w_{j}</tex><br />
<tex> \mathtt{time++}</tex><br />
<br />
===Сложность алгоритмов===<br />
====Алгоритм 1====<br />
Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \max\limits_{i = 1 \ldots n} r_{i}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, [[:Категория:Приоритетные_очереди|очередь с приоритетами]]. Значит общее время работы алгоритма <tex>O((n + \max\limits_{i = 1 \ldots n} r_{i})\log n)</tex><br />
<br />
====Алгоритм 2====<br />
В начале алгоритма мы добавляем все элементы <tex>w_i</tex> в двоичную кучу тратя на это <tex>O(n \log n)</tex> времени. Затем мы тратим <tex>O(n \log n)</tex> на получение ответа. Тогда суммарное время работы алгоритма составит <tex>O(n \log n + n \log n)</tex> что есть <tex>O(n \log n)</tex> времени.<br />
<br />
==См. также==<br />
* [[Классификация задач]]<br />
* [[1outtreesumwc|<tex>1 \mid outtree \mid \sum w_i C_i</tex>]]<br />
* [[1ridipi1|<tex>1 | r_{i}, d_{i}, p_{i}=1 | -</tex>]]<br />
<br />
==Источники информации==<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 19-20<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 38-39<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 84-85<br />
* Лазарев А.А., Мусатова Е.Г., Кварацхелия А.Г., Гафаров Е.Р. Пособие по теории расписаний.<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Теория расписаний]]</div>Sergej Arkhipovhttp://neerc.ifmo.ru/wiki/index.php?title=1ripi1sumwc&diff=473341ripi1sumwc2015-06-03T17:38:17Z<p>Sergej Arkhipov: </p>
<hr />
<div><tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum w_i C_i</tex><br />
<br />
{{Задача<br />
|definition=<br />
Дано <tex>n</tex> работ и один станок. Для каждой работы известно её время появления <tex>r_{i}</tex> и вес <tex>w_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>. Требуется выполнить все работы, чтобы значение <tex>\sum w_{i} C_{i}</tex> было минимальным, где <tex>C_{i}</tex> {{---}} время окончания работы.<br />
}}<br />
<br />
==Более простые варианты исходной задачи==<br />
<br />
Перед решением основной задачи рассмотрим более простые.<br />
<br />
===Вариант 1===<br />
<tex> 1 \mid p_i = 1\mid \sum C_i</tex><br />
<br />
Этот случай простейший. Ответом будет <tex>\sum\limits_{k = 1}^n(k)</tex>, так как мы <tex>n</tex> раз сложим время окончания выполнения одной работы. Воспользовавшись формулой суммы первых <tex>n</tex> членов арифметической прогрессии алгоритм <tex>S_n=\frac{a_1+a_n}2 \cdot n</tex> будет работает за <tex>O(1)</tex>.<br />
<br />
===Вариант 2===<br />
<tex> 1 \mid p_i = 1\mid \sum w_i C_i</tex><br />
<br />
Для верного выполнения просто выставим работы по порядку невозрастания весов, тогда ответом будет <tex> \sum\limits_{i = 1}^n(w_i C_i)</tex>, так как мы <tex>n</tex> раз сложим время окончания выполнения одной работы (которое в нашем случае <tex>C_{i-1}+1</tex>) домноженное на вес этой работы. Вес работ [[Сортировка|отсортировали]] за <tex>O(n \log n)</tex>. Алгоритм работает за <tex>O(n + n \log n)</tex> <br />
<br />
===Вариант 3===<br />
<tex> 1 \mid r_i,p_i = 1 \mid \sum f_i</tex><br />
<br />
<tex>f_{i}</tex> {{---}} монотонная функция времени окончания работы <tex>C_{i}</tex> для работ <tex>i = 1, 2, \ldots , n</tex>.<br />
<br />
<br />
Нам нужно распределить <tex>n</tex> работ в разное время. Если мы назначим время <tex>t</tex> для работы <tex>i</tex> то цена будет <tex>f_i(t + 1)</tex>. Функция <tex>f_i</tex> монотонно неубывающая, тогда работы в расписании надо располагать как можно раньше для получения верного решения. <tex>n</tex> временных интервалов <tex>t_i</tex> для <tex>n</tex> работ могут быть получены с помощью следующего алгоритма, где предполагается что работы отсортированы так:<br />
<br />
<tex> r_1 \leqslant r_2 \leqslant \ldots \leqslant r_n</tex> <br />
<br />
'''Псевдокод'''<br />
<br />
<tex>t_1 \leftarrow r_1 </tex><br />
'''for''' <tex> i \leftarrow 2</tex> '''to''' <tex>n</tex> '''do'''<br />
<tex> t_i \leftarrow </tex> '''max'''<tex>(r_i, \ t_{i-1} - 1)</tex><br />
<br />
Этот алгоритм работает за <tex>O(n \log n +n)</tex><br />
==Основная задача== <br />
===Описание алгоритма===<br />
Пусть <tex>time</tex> {{---}} текущий момент времени.<br/><br />
Для каждого очередного значения <tex>time</tex>, которое изменяется от <tex>0</tex> до времени окончания последней работы, будем:<br />
<ol><br />
<li> Выбирать работу <tex>j</tex> из множества невыполненных работ, у которой <tex>r_{i} \leqslant time</tex>, а значение <tex>w_{i}</tex> максимально.</li><br />
<li> Если мы смогли найти работу <tex>j</tex>, то выполняем её в момент времени <tex>time</tex> и удаляем из множества невыполненных работ.</li><br />
<li> Увеличиваем <tex>time</tex> на один.</li><br />
</ol><br />
<br />
===Доказательство корректности алгоритма===<br />
{{Теорема<br />
|statement=<br />
Расписание, построенное данным алгоритмом, является корректным и оптимальным.<br />
|proof=<br />
Доказательство будем вести от противного.<br/><br />
Рассмотрим расписание <tex>S_{1}</tex>, полученное после выполнения нашего алгоритма, и оптимальное расписание <tex>S_{2}</tex>.<br/><br />
Возьмём первый момент времени <tex>t_{1}</tex>, когда расписания различаются. Пусть в этот момент времени в <tex>S_{1}</tex>, будет выполняться работа с весом <tex>w_{1}</tex>, а в <tex>S_{2}</tex> {{---}} работа с весом <tex>w_{2}</tex>.<br/><br />
Это первый момент, в котором расписания отличаются, значит в <tex>S_{2}</tex> работа с весом <tex>w_{1}</tex> выполнится в момент времени <tex>t_{2} > t_{1}</tex>.<br/><br />
Поменяем местами работы с весами <tex>w_{1}</tex> и <tex>w_{2}</tex> в <tex>S_{2}</tex> и полуим расписание <tex>S_{3}</tex>. Это возможно, потому что время появления этих работ не меньше <tex>t_{1}</tex>.<br/><br />
При такой перестановке ответы на задачу для <tex>S_{2}</tex> и <tex>S_{3}</tex> будут отличаться на <br />
<ul><tex>t_{1}w_{2} + t_{2}w_{1} - t_{1}w_{1} + t_{2}w_{2} = t_{1}(w_{2} - w_{1}) + t_{2}(w_{1} - w_{2}) = (t_{1} - t_{2})(w_{2} - w_{1})</tex></ul><br />
Первая скобка отрицательная: <tex>t_{1} < t_{2}</tex>. Вторая скобка тоже отрицательная из того, что в <tex>S_{1}</tex> работа с весом <tex>w_1</tex> выполняется раньше, значит её вес должен быть больше <tex>w_2</tex>.<br/><br />
Итого имеем, что ответ для <tex>S_{2}</tex> больше, чем ответ для <tex>S_{3}</tex>. Следовательно расписание <tex>S_2</tex> неоптимальное. Получили противоречие. Значит не существует такого момента времени, когда расписание <tex>S_{1}</tex> отличается от оптимального. Следовательно мы доказали, что оно оптимальное.<br />
}}<br />
<br />
===Псевдокод===<br />
<br />
====Алгоритм 1====<br />
<tex> S \leftarrow \{1 \ldots n\}</tex><br />
<tex> \mathtt{time} \leftarrow 0</tex><br />
<tex> \mathtt{answer} \leftarrow 0</tex><br />
'''while''' <tex> S \neq \varnothing </tex><br />
<tex> j \leftarrow null </tex><br />
'''if''' <tex> i \in S</tex> '''and''' <tex> r_{i} \leqslant \mathtt{time}</tex> '''and''' <tex>w_i \geqslant \max\limits_{j \in S, j = 1 \ldots n} w_j</tex><br />
<tex> j \leftarrow i </tex><br />
'''if''' <tex>j \neq null </tex><br />
<tex> S \leftarrow S \setminus j</tex><br />
<tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot w_{j}</tex><br />
<tex> \mathtt{time++}</tex><br />
<br />
====Алгоритм 2====<br />
Этот алгоритм реализован с помощью [[Двоичная_куча|двоичной кучи]] <tex>\mathtt{Heap}</tex> в которой операции вставки и извлечения выполняются за <tex>O(\log n)</tex>, а операция поиска максимального элемента за <tex>O(1)</tex><br />
<tex> S \leftarrow \{1 \ldots n\}</tex><br />
<tex> \mathtt{time} \leftarrow 0</tex><br />
<tex> \mathtt{answer} \leftarrow 0</tex><br />
'''for''' <tex>i \leftarrow 1 </tex> '''to''' <tex>n</tex> '''do'''<br />
Heap.insert(<tex>w_i</tex>)<br />
'''while''' <tex> S \neq \varnothing </tex><br />
<tex> j \leftarrow null </tex><br />
'''if''' <tex> i \in S</tex> '''and''' <tex> r_{i} \leqslant \mathtt{time}</tex> '''and''' <tex>w_i \geqslant </tex> Heap.Max()<br />
<tex> j \leftarrow i </tex><br />
'''if''' <tex>j \neq null </tex><br />
<tex> S \leftarrow S \setminus j</tex><br />
Heap.ExtractMax()<br />
<tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot w_{j}</tex><br />
<tex> \mathtt{time++}</tex><br />
<br />
===Сложность алгоритмов===<br />
====Алгоритм 1====<br />
Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \max\limits_{i = 1 \ldots n} r_{i}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, [[:Категория:Приоритетные_очереди|очередь с приоритетами]]. Значит общее время работы алгоритма <tex>O((n + \max\limits_{i = 1 \ldots n} r_{i})\log n)</tex><br />
<br />
====Алгоритм 2====<br />
В начале алгоритма мы добавляем все элементы <tex>w_i</tex> в двоичную кучу тратя на это <tex>O(n \log n)</tex> времени. Затем мы тратим <tex>O(n \log n)</tex> на получение ответа. Тогда суммарное время работы алгоритма составит <tex>O(n \log n + n \log n)</tex> что есть <tex>O(n \log n)</tex> времени.<br />
<br />
==См. также==<br />
* [[Классификация задач]]<br />
* [[1outtreesumwc|<tex>1 \mid outtree \mid \sum w_i C_i</tex>]]<br />
* [[1ridipi1|<tex>1 | r_{i}, d_{i}, p_{i}=1 | -</tex>]]<br />
<br />
==Источники информации==<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 19-20<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 38-39<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 84-85<br />
* Лазарев А.А., Мусатова Е.Г., Кварацхелия А.Г., Гафаров Е.Р. Пособие по теории расписаний.<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Теория расписаний]]</div>Sergej Arkhipovhttp://neerc.ifmo.ru/wiki/index.php?title=Fpij1sumwu&diff=47332Fpij1sumwu2015-06-03T17:36:07Z<p>Sergej Arkhipov: </p>
<hr />
<div><tex dpi = "200">F \mid p_{ij} = 1 \mid \sum w_iu_i</tex><br />
{{Задача<br />
|definition=<br />
Дано <tex>m</tex> станков, на которых нужно обработать <tex>n</tex> деталей. Каждую деталь нужно обработать по очереди на всех станках. Любая работа на любом станке выполняется единицу времени. Для каждой работы есть дедлайн <tex>d_i</tex> {{---}} время, до которого она должна быть закончена, и штраф <tex>w_i</tex>, который нужно будет выплатить в случае, если работа была закончена после <tex>d_i</tex>. Необходимо минимизировать суммарный штраф, который придется выплатить.<br />
}}<br />
<br />
==Алгоритм==<br />
<br />
===Описание алгоритма===<br />
<br />
{{Утверждение<br />
|statement=Существует оптимальное расписание, в котором каждая работа делается непрерывно.<br />
|proof=<br />
Рассмотрим расписание, в котором есть работы, которые делаются не непрерывно. Рассмотрим самый ранний разрыв: работа <tex>i</tex> делалась в моменты <tex>t(i), t(i) + 1, \ldots, t(i) + k</tex>, где <tex>k < m</tex>, но не делалась в момент времени <tex>t(i) + k + 1</tex>. Докажем, что в момент времени <tex>t(i) + k + 1</tex>, <tex>k + 1</tex>-й станок простаивает и можно продолжить делать <tex>i</tex>-ю работу. <br />
<br />
Пусть в момент времени <tex>t(i) + k + 1</tex> на <tex>k + 1</tex>-м станке делается работа <tex>j</tex>. <br />
В <tex>t(i) + k</tex>-й момент времени <tex>k</tex>-й станок был занят выполнением <tex>i</tex>-й работы, а значит, не мог выполнять <tex>j</tex>-ю. Значит, разрыв был раньше, что противоречит тому, что был выбран самый ранний разрыв. Значит, в <tex>t(i) + k + 1</tex>-й момент <tex>k + 1</tex>-й станок свободен и туда можно поставить <tex>i</tex>-ю работу, устранив разрыв. <br />
<br />
После устранения каждого разрыва получим расписание без разрывов, в котором каждая работа заканчивает выполняться не позже, чем в изначальном.<br />
}}<br />
<br />
По этому утверждению, если работу <tex>i</tex> начали делать в <tex>t(i)</tex>, то закончена она будет в <tex>t(i) + m</tex>. Найдем время <tex>d'_i</tex> такое, что начав выполнять в него работу <tex>i</tex>, мы успеем выполнить ее до <tex>d_i</tex>: <tex>d'_i = d_i - m</tex>. Таким образом, вычтя из всех <tex>d_i</tex> число <tex>m</tex>, мы свели задачу к <tex>1 \mid p_i = 1 \mid \sum w_i U_i</tex>. <br />
<br />
Построив оптимальное расписание для <tex>1 \mid p_i = 1 \mid \sum w_i U_i</tex>, мы найдем времена, в которые нужно начинать выполнять работы. По утверждению выше, работы можно выполнять непрерывно.<br />
<br />
===Сложность алгоритма===<br />
Задача <tex>F \mid p_{i j} = 1 \mid \sum w_iu_i</tex> за <tex>O(n)</tex> сводится к задаче <tex>1 \mid p_i = 1 \mid \sum w_i u_i</tex>. Задача <tex>1 \mid p_i = 1 \mid \sum u_iw_i</tex> решается за <tex>O(n \log n)</tex>. После решения этой задачи, нужно вывести ответ, имеющий размер <tex>O(nm)</tex>. Значит, итоговая сложность алгоритма {{---}} <tex>O(n \log n + nm)</tex>.<br />
<br />
==См. также.==<br />
* [[Классификация задач]]<br />
* [[Flow shop]]<br />
<br />
==Источники информации==<br />
* Лазарев А.А., Мусатова Е.Г., Кварацхелия А.Г., Гафаров Е.Р. Пособие по теории расписаний.<br />
* Vladimír Modrák, R. Sudhakara Pandian. FLOW SHOP SCHEDULING ALGORITHM TO MINIMIZE COMPLETION TIME FOR -JOBS -MACHINES PROBLEM<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Теория расписаний]]</div>Sergej Arkhipovhttp://neerc.ifmo.ru/wiki/index.php?title=1ripi1sumwc&diff=473311ripi1sumwc2015-06-03T17:33:47Z<p>Sergej Arkhipov: </p>
<hr />
<div><tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum w_i C_i</tex><br />
<br />
{{Задача<br />
|definition=<br />
Дано <tex>n</tex> работ и один станок. Для каждой работы известно её время появления <tex>r_{i}</tex> и вес <tex>w_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>. Требуется выполнить все работы, чтобы значение <tex>\sum w_{i} C_{i}</tex> было минимальным, где <tex>C_{i}</tex> {{---}} время окончания работы.<br />
}}<br />
<br />
==Более простые варианты исходной задачи==<br />
<br />
Перед решением основной задачи рассмотрим более простые.<br />
<br />
===Вариант 1===<br />
<tex> 1 \mid p_i = 1\mid \sum C_i</tex><br />
<br />
Этот случай простейший. Ответом будет <tex>\sum\limits_{k = 1}^n(k)</tex>, так как мы <tex>n</tex> раз сложим время окончания выполнения одной работы. Воспользовавшись формулой суммы первых <tex>n</tex> членов арифметической прогрессии алгоритм <tex>S_n=\frac{a_1+a_n}2 \cdot n</tex> будет работает за <tex>O(1)</tex>.<br />
<br />
===Вариант 2===<br />
<tex> 1 \mid p_i = 1\mid \sum w_i C_i</tex><br />
<br />
Для верного выполнения просто выставим работы по порядку невозрастания весов, тогда ответом будет <tex> \sum\limits_{i = 1}^n(w_i C_i)</tex>, так как мы <tex>n</tex> раз сложим время окончания выполнения одной работы (которое в нашем случае <tex>C_{i-1}+1</tex>) домноженное на вес этой работы. Вес работ [[Сортировка|отсортировали]] за <tex>O(n \log n)</tex>. Алгоритм работает за <tex>O(n + n \log n)</tex> <br />
<br />
===Вариант 3===<br />
<tex> 1 \mid r_i,p_i = 1 \mid \sum f_i</tex><br />
<br />
<tex>f_{i}</tex> {{---}} монотонная функция времени окончания работы <tex>C_{i}</tex> для работ <tex>i = 1, 2, \ldots , n</tex>.<br />
<br />
<br />
Нам нужно распределить <tex>n</tex> работ в разное время. Если мы назначим время <tex>t</tex> для работы <tex>i</tex> то цена будет <tex>f_i(t + 1)</tex>. Функция <tex>f_i</tex> монотонно неубывающая, тогда работы в расписании надо располагать как можно раньше для получения верного решения. <tex>n</tex> временных интервалов <tex>t_i</tex> для <tex>n</tex> работ могут быть получены с помощью следующего алгоритма, где предполагается что работы отсортированы так:<br />
<br />
<tex> r_1 \leqslant r_2 \leqslant \ldots \leqslant r_n</tex> <br />
<br />
'''Псевдокод'''<br />
<br />
<tex>t_1 \leftarrow r_1 </tex><br />
'''for''' <tex> i \leftarrow 2</tex> '''to''' <tex>n</tex> '''do'''<br />
<tex> t_i \leftarrow </tex> '''max'''<tex>(r_i, \ t_{i-1} - 1)</tex><br />
<br />
Этот алгоритм работает за <tex>O(n \log n +n)</tex><br />
==Основная задача== <br />
===Описание алгоритма===<br />
Пусть <tex>time</tex> {{---}} текущий момент времени.<br/><br />
Для каждого очередного значения <tex>time</tex>, которое изменяется от <tex>0</tex> до времени окончания последней работы, будем:<br />
<ol><br />
<li> Выбирать работу <tex>j</tex> из множества невыполненных работ, у которой <tex>r_{i} \leqslant time</tex>, а значение <tex>w_{i}</tex> максимально.</li><br />
<li> Если мы смогли найти работу <tex>j</tex>, то выполняем её в момент времени <tex>time</tex> и удаляем из множества невыполненных работ.</li><br />
<li> Увеличиваем <tex>time</tex> на один.</li><br />
</ol><br />
<br />
===Доказательство корректности алгоритма===<br />
{{Теорема<br />
|statement=<br />
Расписание, построенное данным алгоритмом, является корректным и оптимальным.<br />
|proof=<br />
Доказательство будем вести от противного.<br/><br />
Рассмотрим расписание <tex>S_{1}</tex>, полученное после выполнения нашего алгоритма, и оптимальное расписание <tex>S_{2}</tex>.<br/><br />
Возьмём первый момент времени <tex>t_{1}</tex>, когда расписания различаются. Пусть в этот момент времени в <tex>S_{1}</tex>, будет выполняться работа с весом <tex>w_{1}</tex>, а в <tex>S_{2}</tex> {{---}} работа с весом <tex>w_{2}</tex>.<br/><br />
Это первый момент, в котором расписания отличаются, значит в <tex>S_{2}</tex> работа с весом <tex>w_{1}</tex> выполнится в момент времени <tex>t_{2} > t_{1}</tex>.<br/><br />
Поменяем местами работы с весами <tex>w_{1}</tex> и <tex>w_{2}</tex> в <tex>S_{2}</tex> и полуим расписание <tex>S_{3}</tex>. Это возможно, потому что время появления этих работ не меньше <tex>t_{1}</tex>.<br/><br />
При такой перестановке ответы на задачу для <tex>S_{2}</tex> и <tex>S_{3}</tex> будут отличаться на <br />
<ul><tex>t_{1}w_{2} + t_{2}w_{1} - t_{1}w_{1} + t_{2}w_{2} = t_{1}(w_{2} - w_{1}) + t_{2}(w_{1} - w_{2}) = (t_{1} - t_{2})(w_{2} - w_{1})</tex></ul><br />
Первая скобка отрицательная: <tex>t_{1} < t_{2}</tex>. Вторая скобка тоже отрицательная из того, что в <tex>S_{1}</tex> работа с весом <tex>w_1</tex> выполняется раньше, значит её вес должен быть больше <tex>w_2</tex>.<br/><br />
Итого имеем, что ответ для <tex>S_{2}</tex> больше, чем ответ для <tex>S_{3}</tex>. Следовательно расписание <tex>S_2</tex> неоптимальное. Получили противоречие. Значит не существует такого момента времени, когда расписание <tex>S_{1}</tex> отличается от оптимального. Следовательно мы доказали, что оно оптимальное.<br />
}}<br />
<br />
===Псевдокод===<br />
<br />
====Алгоритм 1====<br />
<tex> S \leftarrow \{1 \ldots n\}</tex><br />
<tex> \mathtt{time} \leftarrow 0</tex><br />
<tex> \mathtt{answer} \leftarrow 0</tex><br />
'''while''' <tex> S \neq \varnothing </tex><br />
<tex> j \leftarrow null </tex><br />
'''if''' <tex> i \in S</tex> '''and''' <tex> r_{i} \leqslant \mathtt{time}</tex> '''and''' <tex>w_i \geqslant \max\limits_{j \in S, j = 1 \ldots n} w_j</tex><br />
<tex> j \leftarrow i </tex><br />
'''if''' <tex>j \neq null </tex><br />
<tex> S \leftarrow S \setminus j</tex><br />
<tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot w_{j}</tex><br />
<tex> \mathtt{time++}</tex><br />
<br />
====Алгоритм 2====<br />
Этот алгоритм реализован с помощью [[Двоичная_куча|двоичной кучи]] <tex>\mathtt{Heap}</tex> в которой операции вставки и извлечения выполняются за <tex>O(\log n)</tex>, а операция поиска максимального элемента за <tex>O(1)</tex><br />
<tex> S \leftarrow \{1 \ldots n\}</tex><br />
<tex> \mathtt{time} \leftarrow 0</tex><br />
<tex> \mathtt{answer} \leftarrow 0</tex><br />
'''for''' <tex>i \leftarrow 1 </tex> '''to''' <tex>n</tex> '''do'''<br />
Heap.insert(<tex>w_i</tex>)<br />
'''while''' <tex> S \neq \varnothing </tex><br />
<tex> j \leftarrow null </tex><br />
'''if''' <tex> i \in S</tex> '''and''' <tex> r_{i} \leqslant \mathtt{time}</tex> '''and''' <tex>w_i \geqslant </tex> Heap.Max()<br />
<tex> j \leftarrow i </tex><br />
'''if''' <tex>j \neq null </tex><br />
<tex> S \leftarrow S \setminus j</tex><br />
Heap.ExtractMax()<br />
<tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot w_{j}</tex><br />
<tex> \mathtt{time++}</tex><br />
<br />
В начале алгоритма мы добавляем все элементы <tex>w_i</tex> в двоичную кучу тратя на это <tex>O(n \log n)</tex> времени. Затем мы тратим <tex>O(n \log n)</tex> на получение ответа. Тогда суммарное время работы алгоритма составит <tex>O(n \log n + n \log n)</tex> что есть <tex>O(n \log n)</tex> времени.<br />
<br />
===Сложность алгоритма===<br />
Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \max\limits_{i = 1 \ldots n} r_{i}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, [[:Категория:Приоритетные_очереди|очередь с приоритетами]]. Значит общее время работы алгоритма <tex>O((n + \max\limits_{i = 1 \ldots n} r_{i})\log n)</tex><br />
<br />
==См. также==<br />
* [[Классификация задач]]<br />
* [[1outtreesumwc|<tex>1 \mid outtree \mid \sum w_i C_i</tex>]]<br />
* [[1ridipi1|<tex>1 | r_{i}, d_{i}, p_{i}=1 | -</tex>]]<br />
<br />
==Источники информации==<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 19-20<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 38-39<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 84-85<br />
* Лазарев А.А., Мусатова Е.Г., Кварацхелия А.Г., Гафаров Е.Р. Пособие по теории расписаний.<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Теория расписаний]]</div>Sergej Arkhipovhttp://neerc.ifmo.ru/wiki/index.php?title=1ripi1sumwc&diff=473241ripi1sumwc2015-06-03T13:52:41Z<p>Sergej Arkhipov: </p>
<hr />
<div><tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum w_i C_i</tex><br />
<br />
{{Задача<br />
|definition=<br />
Дано <tex>n</tex> работ и один станок. Для каждой работы известно её время появления <tex>r_{i}</tex> и вес <tex>w_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>. Требуется выполнить все работы, чтобы значение <tex>\sum w_{i} C_{i}</tex> было минимальным, где <tex>C_{i}</tex> {{---}} время окончания работы.<br />
}}<br />
<br />
==Более простые варианты исходной задачи==<br />
<br />
Перед решением основной задачи рассмотрим более простые.<br />
<br />
===Вариант 1===<br />
<tex> 1 \mid p_i = 1\mid \sum C_i</tex><br />
<br />
Этот случай простейший. Ответом будет <tex>\sum\limits_{k = 1}^n(k)</tex>, так как мы <tex>n</tex> раз сложим время окончания выполнения одной работы. Воспользовавшись формулой суммы первых <tex>n</tex> членов арифметической прогрессии алгоритм <tex>S_n=\frac{a_1+a_n}2 \cdot n</tex> будет работает за <tex>O(1)</tex>.<br />
<br />
===Вариант 2===<br />
<tex> 1 \mid p_i = 1\mid \sum w_i C_i</tex><br />
<br />
Для верного выполнения просто выставим работы по порядку невозрастания весов, тогда ответом будет <tex> \sum\limits_{i = 1}^n(w_i C_i)</tex>, так как мы <tex>n</tex> раз сложим время окончания выполнения одной работы (которое в нашем случае <tex>C_{i-1}+1</tex>) домноженное на вес этой работы. Вес работ [[Сортировка|отсортировали]] за <tex>O(n \log n)</tex>. Алгоритм работает за <tex>O(n + n \log n)</tex> <br />
<br />
===Вариант 3===<br />
<tex> 1 \mid r_i,p_i = 1 \mid \sum f_i</tex><br />
<br />
<tex>f_{i}</tex> {{---}} монотонная функция времени окончания работы <tex>C_{i}</tex> для работ <tex>i = 1, 2, \ldots , n</tex>.<br />
<br />
<br />
Нам нужно распределить <tex>n</tex> работ в разное время. Если мы назначим время <tex>t</tex> для работы <tex>i</tex> то цена будет <tex>f_i(t + 1)</tex>. Функция <tex>f_i</tex> монотонно неубывающая, тогда работы в расписании надо располагать как можно раньше для получения верного решения. <tex>n</tex> временных интервалов <tex>t_i</tex> для <tex>n</tex> работ могут быть получены с помощью следующего алгоритма, где предполагается что работы отсортированы так:<br />
<br />
<tex> r_1 \leqslant r_2 \leqslant \ldots \leqslant r_n</tex> <br />
<br />
'''Псевдокод'''<br />
<br />
<tex>t_1 \leftarrow r_1 </tex><br />
'''for''' <tex> i \leftarrow 2</tex> '''to''' <tex>n</tex> '''do'''<br />
<tex> t_i \leftarrow </tex> '''max'''<tex>(r_i, \ t_{i-1} - 1)</tex><br />
<br />
Этот алгоритм работает за <tex>O(n \log n +n)</tex><br />
==Основная задача== <br />
===Описание алгоритма===<br />
Пусть <tex>time</tex> {{---}} текущий момент времени.<br/><br />
Для каждого очередного значения <tex>time</tex>, которое изменяется от <tex>0</tex> до времени окончания последней работы, будем:<br />
<ol><br />
<li> Выбирать работу <tex>j</tex> из множества невыполненных работ, у которой <tex>r_{i} \leqslant time</tex>, а значение <tex>w_{i}</tex> максимально.</li><br />
<li> Если мы смогли найти работу <tex>j</tex>, то выполняем её в момент времени <tex>time</tex> и удаляем из множества невыполненных работ.</li><br />
<li> Увеличиваем <tex>time</tex> на один.</li><br />
</ol><br />
<br />
===Доказательство корректности алгоритма===<br />
{{Теорема<br />
|statement=<br />
Расписание, построенное данным алгоритмом, является корректным и оптимальным.<br />
|proof=<br />
Доказательство будем вести от противного.<br/><br />
Рассмотрим расписание <tex>S_{1}</tex>, полученное после выполнения нашего алгоритма, и оптимальное расписание <tex>S_{2}</tex>.<br/><br />
Возьмём первый момент времени <tex>t_{1}</tex>, когда расписания различаются. Пусть в этот момент времени в <tex>S_{1}</tex>, будет выполняться работа с весом <tex>w_{1}</tex>, а в <tex>S_{2}</tex> {{---}} работа с весом <tex>w_{2}</tex>.<br/><br />
Это первый момент, в котором расписания отличаются, значит в <tex>S_{2}</tex> работа с весом <tex>w_{1}</tex> выполнится в момент времени <tex>t_{2} > t_{1}</tex>.<br/><br />
Поменяем местами работы с весами <tex>w_{1}</tex> и <tex>w_{2}</tex> в <tex>S_{2}</tex> и полуим расписание <tex>S_{3}</tex>. Это возможно, потому что время появления этих работ не меньше <tex>t_{1}</tex>.<br/><br />
При такой перестановке ответы на задачу для <tex>S_{2}</tex> и <tex>S_{3}</tex> будут отличаться на <br />
<ul><tex>t_{1}w_{2} + t_{2}w_{1} - t_{1}w_{1} + t_{2}w_{2} = t_{1}(w_{2} - w_{1}) + t_{2}(w_{1} - w_{2}) = (t_{1} - t_{2})(w_{2} - w_{1})</tex></ul><br />
Первая скобка отрицательная: <tex>t_{1} < t_{2}</tex>. Вторая скобка тоже отрицательная из того, что в <tex>S_{1}</tex> работа с весом <tex>w_1</tex> выполняется раньше, значит её вес должен быть больше <tex>w_2</tex>.<br/><br />
Итого имеем, что ответ для <tex>S_{2}</tex> больше, чем ответ для <tex>S_{3}</tex>. Следовательно расписание <tex>S_2</tex> неоптимальное. Получили противоречие. Значит не существует такого момента времени, когда расписание <tex>S_{1}</tex> отличается от оптимального. Следовательно мы доказали, что оно оптимальное.<br />
}}<br />
<br />
===Псевдокод===<br />
<br />
====Алгоритм 1====<br />
<tex> S \leftarrow \{1 \ldots n\}</tex><br />
<tex> \mathtt{time} \leftarrow 0</tex><br />
<tex> \mathtt{answer} \leftarrow 0</tex><br />
'''while''' <tex> S \neq \varnothing </tex><br />
<tex> j \leftarrow null </tex><br />
'''if''' <tex> i \in S</tex> '''and''' <tex> r_{i} \leqslant \mathtt{time}</tex> '''and''' <tex>w_i \geqslant \max\limits_{j \in S, j = 1 \ldots n} w_j</tex><br />
<tex> j \leftarrow i </tex><br />
'''if''' <tex>j \neq null </tex><br />
<tex> S \leftarrow S \setminus j</tex><br />
<tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot w_{j}</tex><br />
<tex> \mathtt{time++}</tex><br />
<br />
====Алгоритм 2====<br />
Этот алгоритм реализован с помощью [[Двоичная_куча|двоичной кучи]] <tex>\mathtt{Heap}</tex> в которой операции вставки и извлечения выполняются за <tex>O(\log n)</tex>, а операция поиска максимального элемента за <tex>O(1)</tex><br />
<tex> S \leftarrow \{1 \ldots n\}</tex><br />
<tex> \mathtt{time} \leftarrow 0</tex><br />
<tex> \mathtt{answer} \leftarrow 0</tex><br />
'''for''' <tex>i \leftarrow 1 </tex> '''to''' <tex>n</tex> '''do'''<br />
Heap.insert(<tex>w_i</tex>)<br />
'''while''' <tex> S \neq \varnothing </tex><br />
<tex> j \leftarrow null </tex><br />
'''if''' <tex> i \in S</tex> '''and''' <tex> r_{i} \leqslant \mathtt{time}</tex> '''and''' <tex>w_i \geqslant </tex> Heap.Max()<br />
<tex> j \leftarrow i </tex><br />
'''if''' <tex>j \neq null </tex><br />
<tex> S \leftarrow S \setminus j</tex><br />
Heap.extractMax()<br />
<tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot w_{j}</tex><br />
<tex> \mathtt{time++}</tex><br />
<br />
В начале алгоритма мы добавляем все элементы <tex>w_i</tex> в двоичную кучу тратя на это <tex>O(n \log n)</tex> времени. Затем мы тратим <tex>O(n \log n)</tex> на получение ответа. Тогда суммарное время работы алгоритма составит <tex>O(n \log n + n \log n)</tex> что равно <tex>O(n \log n)</tex> времени.<br />
<br />
===Сложность алгоритма===<br />
Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \max\limits_{i = 1 \ldots n} r_{i}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, [[:Категория:Приоритетные_очереди|очередь с приоритетами]]. Значит общее время работы алгоритма <tex>O((n + \max\limits_{i = 1 \ldots n} r_{i})\log n)</tex><br />
<br />
==См. также==<br />
* [[Классификация задач]]<br />
* [[1outtreesumwc|<tex>1 \mid outtree \mid \sum w_i C_i</tex>]]<br />
* [[1ridipi1|<tex>1 | r_{i}, d_{i}, p_{i}=1 | -</tex>]]<br />
<br />
==Источники информации==<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 19-20<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 38-39<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 84-85<br />
* Лазарев А.А., Мусатова Е.Г., Кварацхелия А.Г., Гафаров Е.Р. Пособие по теории расписаний.<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Теория расписаний]]</div>Sergej Arkhipovhttp://neerc.ifmo.ru/wiki/index.php?title=1ripi1sumwc&diff=473211ripi1sumwc2015-06-03T12:43:15Z<p>Sergej Arkhipov: </p>
<hr />
<div><tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum w_i C_i</tex><br />
<br />
{{Задача<br />
|definition=<br />
Дано <tex>n</tex> работ и один станок. Для каждой работы известно её время появления <tex>r_{i}</tex> и вес <tex>w_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>. Требуется выполнить все работы, чтобы значение <tex>\sum w_{i} C_{i}</tex> было минимальным, где <tex>C_{i}</tex> {{---}} время окончания работы.<br />
}}<br />
<br />
==Более простые варианты исходной задачи==<br />
<br />
Перед решением основной задачи рассмотрим более простые.<br />
<br />
===Вариант 1===<br />
<tex> 1 \mid p_i = 1\mid \sum C_i</tex><br />
<br />
Этот случай простейший. Ответом будет <tex>\sum\limits_{k = 1}^n(k)</tex>, так как мы <tex>n</tex> раз сложим время окончания выполнения одной работы. Воспользовавшись формулой суммы первых <tex>n</tex> членов арифметической прогрессии алгоритм <tex>S_n=\frac{a_1+a_n}2 \cdot n</tex> будет работает за <tex>O(1)</tex>.<br />
<br />
===Вариант 2===<br />
<tex> 1 \mid p_i = 1\mid \sum w_i C_i</tex><br />
<br />
Для верного выполнения просто выставим работы по порядку невозрастания весов, тогда ответом будет <tex> \sum\limits_{i = 1}^n(w_i C_i)</tex>, так как мы <tex>n</tex> раз сложим время окончания выполнения одной работы (которое в нашем случае <tex>C_{i-1}+1</tex>) домноженное на вес этой работы. Вес работ [[Сортировка|отсортировали]] за <tex>O(n \log n)</tex>. Алгоритм работает за <tex>O(n + n \log n)</tex> <br />
<br />
===Вариант 3===<br />
<tex> 1 \mid r_i,p_i = 1 \mid \sum f_i</tex><br />
<br />
<tex>f_{i}</tex> {{---}} монотонная функция времени окончания работы <tex>C_{i}</tex> для работ <tex>i = 1, 2, \ldots , n</tex>.<br />
<br />
<br />
Нам нужно распределить <tex>n</tex> работ в разное время. Если мы назначим время <tex>t</tex> для работы <tex>i</tex> то цена будет <tex>f_i(t + 1)</tex>. Функция <tex>f_i</tex> монотонно неубывающая, тогда работы в расписании надо располагать как можно раньше для получения верного решения. <tex>n</tex> временных интервалов <tex>t_i</tex> для <tex>n</tex> работ могут быть получены с помощью следующего алгоритма, где предполагается что работы отсортированы так:<br />
<br />
<tex> r_1 \leqslant r_2 \leqslant \ldots \leqslant r_n</tex> <br />
<br />
'''Псевдокод'''<br />
<br />
<tex>t_1 \leftarrow r_1 </tex><br />
'''for''' <tex> i \leftarrow 2</tex> '''to''' <tex>n</tex> '''do'''<br />
<tex> t_i \leftarrow </tex> '''max'''<tex>(r_i, \ t_{i-1} - 1)</tex><br />
<br />
Этот алгоритм работает за <tex>O(n \log n +n)</tex><br />
==Основная задача== <br />
===Описание алгоритма===<br />
Пусть <tex>time</tex> {{---}} текущий момент времени.<br/><br />
Для каждого очередного значения <tex>time</tex>, которое изменяется от <tex>0</tex> до времени окончания последней работы, будем:<br />
<ol><br />
<li> Выбирать работу <tex>j</tex> из множества невыполненных работ, у которой <tex>r_{i} \leqslant time</tex>, а значение <tex>w_{i}</tex> максимально.</li><br />
<li> Если мы смогли найти работу <tex>j</tex>, то выполняем её в момент времени <tex>time</tex> и удаляем из множества невыполненных работ.</li><br />
<li> Увеличиваем <tex>time</tex> на один.</li><br />
</ol><br />
<br />
===Доказательство корректности алгоритма===<br />
{{Теорема<br />
|statement=<br />
Расписание, построенное данным алгоритмом, является корректным и оптимальным.<br />
|proof=<br />
Доказательство будем вести от противного.<br/><br />
Рассмотрим расписание <tex>S_{1}</tex>, полученное после выполнения нашего алгоритма, и оптимальное расписание <tex>S_{2}</tex>.<br/><br />
Возьмём первый момент времени <tex>t_{1}</tex>, когда расписания различаются. Пусть в этот момент времени в <tex>S_{1}</tex>, будет выполняться работа с весом <tex>w_{1}</tex>, а в <tex>S_{2}</tex> {{---}} работа с весом <tex>w_{2}</tex>.<br/><br />
Это первый момент, в котором расписания отличаются, значит в <tex>S_{2}</tex> работа с весом <tex>w_{1}</tex> выполнится в момент времени <tex>t_{2} > t_{1}</tex>.<br/><br />
Поменяем местами работы с весами <tex>w_{1}</tex> и <tex>w_{2}</tex> в <tex>S_{2}</tex> и полуим расписание <tex>S_{3}</tex>. Это возможно, потому что время появления этих работ не меньше <tex>t_{1}</tex>.<br/><br />
При такой перестановке ответы на задачу для <tex>S_{2}</tex> и <tex>S_{3}</tex> будут отличаться на <br />
<ul><tex>t_{1}w_{2} + t_{2}w_{1} - t_{1}w_{1} + t_{2}w_{2} = t_{1}(w_{2} - w_{1}) + t_{2}(w_{1} - w_{2}) = (t_{1} - t_{2})(w_{2} - w_{1})</tex></ul><br />
Первая скобка отрицательная: <tex>t_{1} < t_{2}</tex>. Вторая скобка тоже отрицательная из того, что в <tex>S_{1}</tex> работа с весом <tex>w_1</tex> выполняется раньше, значит её вес должен быть больше <tex>w_2</tex>.<br/><br />
Итого имеем, что ответ для <tex>S_{2}</tex> больше, чем ответ для <tex>S_{3}</tex>. Следовательно расписание <tex>S_2</tex> неоптимальное. Получили противоречие. Значит не существует такого момента времени, когда расписание <tex>S_{1}</tex> отличается от оптимального. Следовательно мы доказали, что оно оптимальное.<br />
}}<br />
<br />
===Псевдокод===<br />
<tex> S \leftarrow \{1 \ldots n\}</tex><br />
<tex> \mathtt{time} \leftarrow 0</tex><br />
<tex> \mathtt{answer} \leftarrow 0</tex><br />
'''while''' <tex> S \neq \varnothing </tex><br />
<tex> j \leftarrow null </tex><br />
'''if''' <tex> i \in S</tex> '''and''' <tex> r_{i} \leqslant \mathtt{time}</tex> '''and''' <tex>w_i \geqslant \max\limits_{j \in S, j = 1 \ldots n} w_j</tex><br />
<tex> j \leftarrow i </tex><br />
'''if''' <tex>j \neq null </tex><br />
<tex> S \leftarrow S \setminus j</tex><br />
<tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot w_{j}</tex><br />
<tex> \mathtt{time++}</tex><br />
<br />
===Сложность алгоритма===<br />
Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \max\limits_{i = 1 \ldots n} r_{i}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, [[:Категория:Приоритетные_очереди|очередь с приоритетами]]. Значит общее время работы алгоритма <tex>O((n + \max\limits_{i = 1 \ldots n} r_{i})\log n)</tex><br />
<br />
==См. также==<br />
* [[Классификация задач]]<br />
* [[1outtreesumwc|<tex>1 \mid outtree \mid \sum w_i C_i</tex>]]<br />
* [[1ridipi1|<tex>1 | r_{i}, d_{i}, p_{i}=1 | -</tex>]]<br />
<br />
==Источники информации==<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 19-20<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 38-39<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 84-85<br />
* Лазарев А.А., Мусатова Е.Г., Кварацхелия А.Г., Гафаров Е.Р. Пособие по теории расписаний.<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Теория расписаний]]</div>Sergej Arkhipovhttp://neerc.ifmo.ru/wiki/index.php?title=Fpij1sumwu&diff=47309Fpij1sumwu2015-06-03T11:45:08Z<p>Sergej Arkhipov: </p>
<hr />
<div><tex dpi = "200">F \mid p_{ij} = 1 \mid \sum w_iu_i</tex><br />
{{Задача<br />
|definition=<br />
Дано <tex>m</tex> станков, на которых нужно обработать <tex>n</tex> деталей. Каждую деталь нужно обработать по очереди на всех станках. Любая работа на любом станке выполняется единицу времени. Для каждой работы есть дедлайн <tex>d_i</tex> {{---}} время, до которого она должна быть закончена, и штраф <tex>w_i</tex>, который нужно будет выплатить в случае, если работа была закончена после <tex>d_i</tex>. Необходимо минимизировать суммарный штраф, который придется выплатить.<br />
}}<br />
<br />
==Алгоритм==<br />
<br />
===Эвристика NEH===<br />
<br />
Одним из наиболее известных алгоритмов решения этой задачи является эвристика Наваза, Энскора и Хама (Nawaz, Enscore, Ham)<br />
<br />
Первое что нужно сделать это упорядочить требования по <tex>\sum\limits_{j = 1}^n p_{i j}</tex> и пронумеровать их в соответствии с этим порядком. Затем нужно определить порядок обслуживания двух первых требований так, чтобы минимизировать время их обслуживания. После этого использовать алгоритм<br />
<br />
'''for''' <tex> i = 3</tex> '''to''' <tex>m</tex> '''do'''<br />
Поместить требование <tex>i</tex> на позицию <tex>k \in [1 , i]</tex> которое минимизирует общее время обслуживания первых <tex>i</tex> требований.<br />
<br />
==Алгоритм сведения==<br />
<br />
===Описание алгоритма===<br />
<br />
{{Утверждение<br />
|statement=Существует оптимальное расписание, в котором каждая работа делается непрерывно.<br />
|proof=<br />
Рассмотрим расписание, в котором есть работы, которые делаются не непрерывно. Рассмотрим самый ранний разрыв: работа <tex>i</tex> делалась в моменты <tex>t(i), t(i) + 1, \ldots, t(i) + k</tex>, где <tex>k < m</tex>, но не делалась в момент времени <tex>t(i) + k + 1</tex>. Докажем, что в момент времени <tex>t(i) + k + 1</tex>, <tex>k + 1</tex>-й станок простаивает и можно продолжить делать <tex>i</tex>-ю работу. <br />
<br />
Пусть в момент времени <tex>t(i) + k + 1</tex> на <tex>k + 1</tex>-м станке делается работа <tex>j</tex>. <br />
В <tex>t(i) + k</tex>-й момент времени <tex>k</tex>-й станок был занят выполнением <tex>i</tex>-й работы, а значит, не мог выполнять <tex>j</tex>-ю. Значит, разрыв был раньше, что противоречит тому, что был выбран самый ранний разрыв. Значит, в <tex>t(i) + k + 1</tex>-й момент <tex>k + 1</tex>-й станок свободен и туда можно поставить <tex>i</tex>-ю работу, устранив разрыв. <br />
<br />
После устранения каждого разрыва получим расписание без разрывов, в котором каждая работа заканчивает выполняться не позже, чем в изначальном.<br />
}}<br />
<br />
По этому утверждению, если работу <tex>i</tex> начали делать в <tex>t(i)</tex>, то закончена она будет в <tex>t(i) + m</tex>. Найдем время <tex>d'_i</tex> такое, что начав выполнять в него работу <tex>i</tex>, мы успеем выполнить ее до <tex>d_i</tex>: <tex>d'_i = d_i - m</tex>. Таким образом, вычтя из всех <tex>d_i</tex> число <tex>m</tex>, мы свели задачу к <tex>1 \mid p_i = 1 \mid \sum w_i U_i</tex>. <br />
<br />
Построив оптимальное расписание для <tex>1 \mid p_i = 1 \mid \sum w_i U_i</tex>, мы найдем времена, в которые нужно начинать выполнять работы. По утверждению выше, работы можно выполнять непрерывно.<br />
<br />
===Сложность алгоритма===<br />
Задача <tex>F \mid p_{i j} = 1 \mid \sum w_iu_i</tex> за <tex>O(n)</tex> сводится к задаче <tex>1 \mid p_i = 1 \mid \sum w_i u_i</tex>. Задача <tex>1 \mid p_i = 1 \mid \sum u_iw_i</tex> решается за <tex>O(n \log n)</tex>. После решения этой задачи, нужно вывести ответ, имеющий размер <tex>O(nm)</tex>. Значит, итоговая сложность алгоритма {{---}} <tex>O(n \log n + nm)</tex>.<br />
<br />
==См. также.==<br />
* [[Классификация задач]]<br />
* [[Flow shop]]<br />
<br />
==Источники информации==<br />
* Лазарев А.А., Мусатова Е.Г., Кварацхелия А.Г., Гафаров Е.Р. Пособие по теории расписаний.<br />
* Vladimír Modrák, R. Sudhakara Pandian. FLOW SHOP SCHEDULING ALGORITHM TO MINIMIZE COMPLETION TIME FOR -JOBS -MACHINES PROBLEM<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Теория расписаний]]</div>Sergej Arkhipovhttp://neerc.ifmo.ru/wiki/index.php?title=Fpij1sumwu&diff=47307Fpij1sumwu2015-06-03T11:42:35Z<p>Sergej Arkhipov: </p>
<hr />
<div><tex dpi = "200">F \mid p_{ij} = 1 \mid \sum w_iu_i</tex><br />
{{Задача<br />
|definition=<br />
Дано <tex>m</tex> станков, на которых нужно обработать <tex>n</tex> деталей. Каждую деталь нужно обработать по очереди на всех станках. Любая работа на любом станке выполняется единицу времени. Для каждой работы есть дедлайн <tex>d_i</tex> {{---}} время, до которого она должна быть закончена, и штраф <tex>w_i</tex>, который нужно будет выплатить в случае, если работа была закончена после <tex>d_i</tex>. Необходимо минимизировать суммарный штраф, который придется выплатить.<br />
}}<br />
==Эвристика NEH==<br />
<br />
Одним из наиболее известных алгоритмов решения этой задачи является эвристика Наваза, Энскора и Хама (Nawaz, Enscore, Ham)<br />
<br />
Первое что нужно сделать это упорядочить требования по <tex>\sum\limits_{j = 1}^n p_{i j}</tex> и пронумеровать их в соответствии с этим порядком. Затем нужно определить порядок обслуживания двух первых требований так, чтобы минимизировать время их обслуживания. После этого использовать алгоритм<br />
<br />
'''for''' <tex> i = 3</tex> '''to''' <tex>m</tex> '''do'''<br />
Поместить требование <tex>i</tex> на позицию <tex>k \in [1 , i]</tex> которое минимизирует общее время обслуживания первых <tex>i</tex> требований.<br />
<br />
==Описание алгоритма==<br />
<br />
{{Утверждение<br />
|statement=Существует оптимальное расписание, в котором каждая работа делается непрерывно.<br />
|proof=<br />
Рассмотрим расписание, в котором есть работы, которые делаются не непрерывно. Рассмотрим самый ранний разрыв: работа <tex>i</tex> делалась в моменты <tex>t(i), t(i) + 1, \ldots, t(i) + k</tex>, где <tex>k < m</tex>, но не делалась в момент времени <tex>t(i) + k + 1</tex>. Докажем, что в момент времени <tex>t(i) + k + 1</tex>, <tex>k + 1</tex>-й станок простаивает и можно продолжить делать <tex>i</tex>-ю работу. <br />
<br />
Пусть в момент времени <tex>t(i) + k + 1</tex> на <tex>k + 1</tex>-м станке делается работа <tex>j</tex>. <br />
В <tex>t(i) + k</tex>-й момент времени <tex>k</tex>-й станок был занят выполнением <tex>i</tex>-й работы, а значит, не мог выполнять <tex>j</tex>-ю. Значит, разрыв был раньше, что противоречит тому, что был выбран самый ранний разрыв. Значит, в <tex>t(i) + k + 1</tex>-й момент <tex>k + 1</tex>-й станок свободен и туда можно поставить <tex>i</tex>-ю работу, устранив разрыв. <br />
<br />
После устранения каждого разрыва получим расписание без разрывов, в котором каждая работа заканчивает выполняться не позже, чем в изначальном.<br />
}}<br />
<br />
По этому утверждению, если работу <tex>i</tex> начали делать в <tex>t(i)</tex>, то закончена она будет в <tex>t(i) + m</tex>. Найдем время <tex>d'_i</tex> такое, что начав выполнять в него работу <tex>i</tex>, мы успеем выполнить ее до <tex>d_i</tex>: <tex>d'_i = d_i - m</tex>. Таким образом, вычтя из всех <tex>d_i</tex> число <tex>m</tex>, мы свели задачу к <tex>1 \mid p_i = 1 \mid \sum w_i U_i</tex>. <br />
<br />
Построив оптимальное расписание для <tex>1 \mid p_i = 1 \mid \sum w_i U_i</tex>, мы найдем времена, в которые нужно начинать выполнять работы. По утверждению выше, работы можно выполнять непрерывно.<br />
<br />
==Сложность алгоритма==<br />
Задача <tex>F \mid p_{i j} = 1 \mid \sum w_iu_i</tex> за <tex>O(n)</tex> сводится к задаче <tex>1 \mid p_i = 1 \mid \sum w_i u_i</tex>. Задача <tex>1 \mid p_i = 1 \mid \sum u_iw_i</tex> решается за <tex>O(n \log n)</tex>. После решения этой задачи, нужно вывести ответ, имеющий размер <tex>O(nm)</tex>. Значит, итоговая сложность алгоритма {{---}} <tex>O(n \log n + nm)</tex>.<br />
<br />
==См. также.==<br />
* [[Классификация задач]]<br />
* [[Flow shop]]<br />
<br />
==Источники информации==<br />
* Лазарев А.А., Мусатова Е.Г., Кварацхелия А.Г., Гафаров Е.Р. Пособие по теории расписаний.<br />
* Vladimír Modrák, R. Sudhakara Pandian. FLOW SHOP SCHEDULING ALGORITHM TO MINIMIZE COMPLETION TIME FOR -JOBS -MACHINES PROBLEM<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Теория расписаний]]</div>Sergej Arkhipovhttp://neerc.ifmo.ru/wiki/index.php?title=Fpij1sumwu&diff=47306Fpij1sumwu2015-06-03T11:38:42Z<p>Sergej Arkhipov: </p>
<hr />
<div><tex dpi = "200">F \mid p_{ij} = 1 \mid \sum w_iu_i</tex><br />
{{Задача<br />
|definition=<br />
Дано <tex>m</tex> станков, на которых нужно обработать <tex>n</tex> деталей. Каждую деталь нужно обработать по очереди на всех станках. Любая работа на любом станке выполняется единицу времени. Для каждой работы есть дедлайн <tex>d_i</tex> {{---}} время, до которого она должна быть закончена, и штраф <tex>w_i</tex>, который нужно будет выплатить в случае, если работа была закончена после <tex>d_i</tex>. Необходимо минимизировать суммарный штраф, который придется выплатить.<br />
}}<br />
==Эвристика NEH==<br />
<br />
Одним из наиболее известных алгоритмов решения этой задачи является эвристика Наваза, Энскора и Хама (Nawaz, Enscore, Ham)<br />
Первое что нужно сделать это упорядочить требования по <tex>\sum\limits_{j = 1}^n p_{i j}</tex> и пронумеровать их в соответствии с этим порядком. Затем нужно определить порядок обслуживания двух первых требований так, чтобы минимизировать время их обслуживания. После этого использовать алгоритм<br />
<br />
'''for''' <tex> i = 3</tex> '''to''' <tex>m</tex> '''do'''<br />
Поместить требование <tex>i</tex> на позицию <tex>k \in [1 , i]</tex> которое минимизирует общее время обслуживания первых <tex>i</tex> требований.<br />
<br />
==Описание алгоритма==<br />
<br />
{{Утверждение<br />
|statement=Существует оптимальное расписание, в котором каждая работа делается непрерывно.<br />
|proof=<br />
Рассмотрим расписание, в котором есть работы, которые делаются не непрерывно. Рассмотрим самый ранний разрыв: работа <tex>i</tex> делалась в моменты <tex>t(i), t(i)+1, \ldots, t(i)+k</tex>, где <tex>k<m</tex>, но не делалась в момент времени <tex>t(i)+k+1</tex>. Докажем, что в момент времени <tex>t(i)+k+1</tex>, <tex>k+1</tex>-й станок простаивает и можно продолжить делать <tex>i</tex>-ю работу. <br />
<br />
Пусть в момент времени <tex>t(i)+k+1</tex> на <tex>k+1</tex>-м станке делается работа <tex>j</tex>. <br />
В <tex>t(i)+k</tex>-й момент времени <tex>k</tex>-й станок был занят выполнением <tex>i</tex>-й работы, а значит, не мог выполнять <tex>j</tex>-ю. Значит, разрыв был раньше, что противоречит тому, что был выбран самый ранний разрыв. Значит, в <tex>t(i)+k+1</tex>-й момент <tex>k+1</tex>-й станок свободен и туда можно поставить <tex>i</tex>-ю работу, устранив разрыв. <br />
<br />
После устранения каждого разрыва получим расписание без разрывов, в котором каждая работа заканчивает выполняться не позже, чем в изначальном.<br />
}}<br />
<br />
По этому утверждению, если работу <tex>i</tex> начали делать в <tex>t(i)</tex>, то закончена она будет в <tex>t(i)+m</tex>. Найдем время <tex>d'_i</tex> такое, что начав выполнять в него работу <tex>i</tex>, мы успеем выполнить ее до <tex>d_i</tex>: <tex>d'_i = d_i - m</tex>. Таким образом, вычтя из всех <tex>d_i</tex> число <tex>m</tex>, мы свели задачу к <tex>1 \mid p_i = 1 \mid \sum w_i U_i</tex>. <br />
<br />
Построив оптимальное расписание для <tex>1 \mid p_i = 1 \mid \sum w_i U_i</tex>, мы найдем времена, в которые нужно начинать выполнять работы. По утверждению выше, работы можно выполнять непрерывно.<br />
<br />
==Сложность алгоритма==<br />
Задача <tex>F \mid p_{ij} = 1 \mid \sum w_iu_i</tex> за <tex>O(n)</tex> сводится к задаче <tex>1 \mid p_i = 1 \mid \sum w_iu_i</tex>. Задача <tex>1 \mid p_i = 1 \mid \sum u_iw_i</tex> решается за <tex>O(n \log n)</tex>. После решения этой задачи, нужно вывести ответ, имеющий размер <tex>O(nm)</tex>. Значит, итоговая сложность алгоритма {{---}} <tex>O(n \log n + nm)</tex>.<br />
<br />
==См. также.==<br />
* [[Классификация задач]]<br />
* [[Flow shop]]<br />
<br />
==Источники информации==<br />
* Лазарев А.А., Мусатова Е.Г., Кварацхелия А.Г., Гафаров Е.Р. Пособие по теории расписаний.<br />
* Vladimír Modrák, R. Sudhakara Pandian. FLOW SHOP SCHEDULING ALGORITHM TO MINIMIZE COMPLETION TIME FOR -JOBS -MACHINES PROBLEM<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Теория расписаний]]</div>Sergej Arkhipovhttp://neerc.ifmo.ru/wiki/index.php?title=Fpij1sumwu&diff=47305Fpij1sumwu2015-06-03T11:21:15Z<p>Sergej Arkhipov: </p>
<hr />
<div><tex dpi = "200">F \mid p_{ij} = 1 \mid \sum w_iu_i</tex><br />
{{Задача<br />
|definition=<br />
Дано <tex>m</tex> станков, на которых нужно обработать <tex>n</tex> деталей. Каждую деталь нужно обработать по очереди на всех станках. Любая работа на любом станке выполняется единицу времени. Для каждой работы есть дедлайн <tex>d_i</tex> {{---}} время, до которого она должна быть закончена, и штраф <tex>w_i</tex>, который нужно будет выплатить в случае, если работа была закончена после <tex>d_i</tex>. Необходимо минимизировать суммарный штраф, который придется выплатить.<br />
}}<br />
==Описание алгоритма==<br />
<br />
{{Утверждение<br />
|statement=Существует оптимальное расписание, в котором каждая работа делается непрерывно.<br />
|proof=<br />
Рассмотрим расписание, в котором есть работы, которые делаются не непрерывно. Рассмотрим самый ранний разрыв: работа <tex>i</tex> делалась в моменты <tex>t(i), t(i)+1, \ldots, t(i)+k</tex>, где <tex>k<m</tex>, но не делалась в момент времени <tex>t(i)+k+1</tex>. Докажем, что в момент времени <tex>t(i)+k+1</tex>, <tex>k+1</tex>-й станок простаивает и можно продолжить делать <tex>i</tex>-ю работу. <br />
<br />
Пусть в момент времени <tex>t(i)+k+1</tex> на <tex>k+1</tex>-м станке делается работа <tex>j</tex>. <br />
В <tex>t(i)+k</tex>-й момент времени <tex>k</tex>-й станок был занят выполнением <tex>i</tex>-й работы, а значит, не мог выполнять <tex>j</tex>-ю. Значит, разрыв был раньше, что противоречит тому, что был выбран самый ранний разрыв. Значит, в <tex>t(i)+k+1</tex>-й момент <tex>k+1</tex>-й станок свободен и туда можно поставить <tex>i</tex>-ю работу, устранив разрыв. <br />
<br />
После устранения каждого разрыва получим расписание без разрывов, в котором каждая работа заканчивает выполняться не позже, чем в изначальном.<br />
}}<br />
<br />
По этому утверждению, если работу <tex>i</tex> начали делать в <tex>t(i)</tex>, то закончена она будет в <tex>t(i)+m</tex>. Найдем время <tex>d'_i</tex> такое, что начав выполнять в него работу <tex>i</tex>, мы успеем выполнить ее до <tex>d_i</tex>: <tex>d'_i = d_i - m</tex>. Таким образом, вычтя из всех <tex>d_i</tex> число <tex>m</tex>, мы свели задачу к <tex>1 \mid p_i = 1 \mid \sum w_i U_i</tex>. <br />
<br />
Построив оптимальное расписание для <tex>1 \mid p_i = 1 \mid \sum w_i U_i</tex>, мы найдем времена, в которые нужно начинать выполнять работы. По утверждению выше, работы можно выполнять непрерывно.<br />
<br />
==Сложность алгоритма==<br />
Задача <tex>F \mid p_{ij} = 1 \mid \sum w_iu_i</tex> за <tex>O(n)</tex> сводится к задаче <tex>1 \mid p_i = 1 \mid \sum w_iu_i</tex>. Задача <tex>1 \mid p_i = 1 \mid \sum u_iw_i</tex> решается за <tex>O(n \log n)</tex>. После решения этой задачи, нужно вывести ответ, имеющий размер <tex>O(nm)</tex>. Значит, итоговая сложность алгоритма {{---}} <tex>O(n \log n + nm)</tex>.<br />
<br />
==См. также.==<br />
* [[Классификация задач]]<br />
* [[Flow shop]]<br />
<br />
==Источники информации==<br />
* Лазарев А.А., Мусатова Е.Г., Кварацхелия А.Г., Гафаров Е.Р. Пособие по теории расписаний.<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Теория расписаний]]</div>Sergej Arkhipovhttp://neerc.ifmo.ru/wiki/index.php?title=1ripi1sumwc&diff=473041ripi1sumwc2015-06-03T11:19:13Z<p>Sergej Arkhipov: </p>
<hr />
<div><tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum w_i C_i</tex><br />
<br />
{{Задача<br />
|definition=<br />
Дано <tex>n</tex> работ и один станок. Для каждой работы известно её время появления <tex>r_{i}</tex> и вес <tex>w_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>. Требуется выполнить все работы, чтобы значение <tex>\sum w_{i} C_{i}</tex> было минимальным, где <tex>C_{i}</tex> {{---}} время окончания работы.<br />
}}<br />
<br />
==Простые задачи==<br />
<br />
Перед решением основной задачи рассмотрим более простые.<br />
<br />
===Задача 1===<br />
<tex dpi = "200"> 1 \mid p_i = 1\mid \sum C_i</tex><br />
<br />
Этот случай простейший. Ответом будет <tex>\sum_{k = 1}^n(k)</tex>, так как мы <tex>n</tex> раз сложим время окончания выполнения одной работы. В этом случае алгоритм работает за <tex>O(n)</tex>.<br />
<br />
===Задача 2===<br />
<tex dpi = "200"> 1 \mid p_i = 1\mid \sum w_i C_i</tex><br />
<br />
Входные данные для этой задачи: число работ <tex>n</tex> и вес каждой работы <tex>w_i</tex> <br />
<br />
Для верного выполнения просто выставим работы по порядку невозрастанию весов, тогда ответом будет <tex> \sum_{i = 1}^n(w_i C_i)</tex>, так как мы <tex>n</tex> раз сложим время окончания выполнения одной работы (которое в нашем случае <tex>C_{i-1}+1</tex>) домноженное на вес этой работы. Если вес работ отсортировали за <tex>O(n \log n)</tex> то алгоритм работает за <tex>O(n + n \log n)</tex> <br />
<br />
===Задача 3===<br />
<tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum f_i</tex><br />
<br />
<tex>f_{i}</tex> {{---}} монотонная функция времени окончания работы <tex>C_{i}</tex> для работ <tex>i = 1, 2, \ldots , n</tex>.<br />
<br />
<br />
Нам нужно распределить <tex>n</tex> работ в разное время. Если мы назначим время <tex>t</tex> для работы <tex>i</tex> то цена будет <tex>f_i(t + 1)</tex>. Так как нужно заполнить <tex>n</tex> временных промежутков, задача может быть решена за <tex>O(n^3)</tex>. Функция <tex>f_i</tex> монотонно неубывающая, тогда работы в расписании надо располагать как можно раньше для получения верного решения. <tex>n</tex> временных интервалов <tex>t_i</tex> для <tex>n</tex> работ могут быть получены с помощью следующего алгоритма, где предполагается что работы нумеруются так:<br />
<br />
<tex> r_1 \leqslant r_2 \leqslant \ldots \leqslant r_n</tex> <br />
<br />
'''Псевдокод'''<br />
<br />
<tex>t_1 \leftarrow r_1 </tex><br />
'''for''' <tex> i \leftarrow 2</tex> '''to''' <tex>n</tex> '''do'''<br />
<tex> t_i \leftarrow </tex> '''max'''<tex>(r_i, \ t_{i-1} - 1)</tex><br />
<br />
==Основная задача== <br />
===Описание алгоритма===<br />
Пусть <tex>time</tex> {{---}} текущий момент времени.<br/><br />
Для каждого очередного значения <tex>time</tex>, которое изменяется от <tex>0</tex> до времени окончания последней работы, будем:<br />
<ol><br />
<li> Выбирать работу <tex>j</tex> из множества невыполненных работ, у которой <tex>r_{i} \leqslant time</tex>, а значение <tex>w_{i}</tex> максимально.</li><br />
<li> Если мы смогли найти работу <tex>j</tex>, то выполняем её в момент времени <tex>time</tex> и удаляем из множества невыполненных работ.</li><br />
<li> Увеличиваем <tex>time</tex> на один.</li><br />
</ol><br />
<br />
===Доказательство корректности алгоритма===<br />
{{Теорема<br />
|statement=<br />
Расписание, построенное данным алгоритмом, является корректным и оптимальным.<br />
|proof=<br />
Доказательство будем вести от противного.<br/><br />
Рассмотрим расписание <tex>S_{1}</tex>, полученное после выполнения нашего алгоритма, и оптимальное расписание <tex>S_{2}</tex>.<br/><br />
Возьмём первый момент времени <tex>t_{1}</tex>, когда расписания различаются. Пусть в этот момент времени в <tex>S_{1}</tex>, будет выполняться работа с весом <tex>w_{1}</tex>, а в <tex>S_{2}</tex> {{---}} работа с весом <tex>w_{2}</tex>.<br/><br />
Это первый момент, в котором расписания отличаются, значит в <tex>S_{2}</tex> работа с весом <tex>w_{1}</tex> выполнится в момент времени <tex>t_{2} > t_{1}</tex>.<br/><br />
Поменяем местами работы с весами <tex>w_{1}</tex> и <tex>w_{2}</tex> в <tex>S_{2}</tex> и полуим расписание <tex>S_{3}</tex>. Это возможно, потому что время появления этих работ не меньше <tex>t_{1}</tex>.<br/><br />
При такой перестановке ответы на задачу для <tex>S_{2}</tex> и <tex>S_{3}</tex> будут отличаться на <br />
<ul><tex>t_{1}w_{2} + t_{2}w_{1} - t_{1}w_{1} + t_{2}w_{2} = t_{1}(w_{2} - w_{1}) + t_{2}(w_{1} - w_{2}) = (t_{1} - t_{2})(w_{2} - w_{1})</tex></ul><br />
Первая скобка отрицательная: <tex>t_{1} < t_{2}</tex>. Вторая скобка тоже отрицательная из того, что в <tex>S_{1}</tex> работа с весом <tex>w_1</tex> выполняется раньше, значит её вес должен быть больше <tex>w_2</tex>.<br/><br />
Итого имеем, что ответ для <tex>S_{2}</tex> больше, чем ответ для <tex>S_{3}</tex>. Следовательно расписание <tex>S_2</tex> неоптимальное. Получили противоречие. Значит не существует такого момента времени, когда расписание <tex>S_{1}</tex> отличается от оптимального. Следовательно мы доказали, что оно оптимальное.<br />
}}<br />
<br />
===Псевдокод===<br />
<tex> S \leftarrow \{1 \ldots n\}</tex><br />
<tex> \mathtt{time} \leftarrow 0</tex><br />
<tex> \mathtt{answer} \leftarrow 0</tex><br />
'''while''' <tex> S \neq \varnothing </tex><br />
<tex> j \leftarrow null </tex><br />
'''if''' <tex> i \in S</tex> '''and''' <tex> r_{i} \leqslant \mathtt{time}</tex> '''and''' <tex>w_i \geqslant \max\limits_{j = 1 \ldots n} w_j</tex><br />
<tex> j \leftarrow i </tex><br />
'''if''' <tex>j \neq null </tex><br />
<tex> S \leftarrow S \setminus j</tex><br />
<tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot w_{j}</tex><br />
<tex> \mathtt{time++}</tex><br />
<br />
===Сложность алгоритма===<br />
Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \max\limits_{i = 1 \ldots n} r_{i}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, [[:Категория:Приоритетные_очереди|очередь с приоритетами]]. Значит общее время работы алгоритма <tex>O((n + \max\limits_{i = 1 \ldots n} r_{i})\log n)</tex><br />
<br />
==См. также==<br />
* [[Классификация задач]]<br />
* [[1ridipi1|<tex>1 \mid outtree \mid \sum w_i C_i</tex>]]<br />
* [[1ridipi1|<tex>1 | r_{i}, d_{i}, p_{i}=1 | -</tex>]]<br />
<br />
==Источники информации==<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 19-20<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 38-39<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 84-85<br />
* Лазарев А.А., Мусатова Е.Г., Кварацхелия А.Г., Гафаров Е.Р. Пособие по теории расписаний.<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Теория расписаний]]</div>Sergej Arkhipovhttp://neerc.ifmo.ru/wiki/index.php?title=1ripi1sumwc&diff=472901ripi1sumwc2015-06-02T21:33:20Z<p>Sergej Arkhipov: </p>
<hr />
<div><tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum w_i C_i</tex><br />
<br />
{{Задача<br />
|definition=<br />
Дано <tex>n</tex> работ и один станок. Для каждой работы известно её время появления <tex>r_{i}</tex> и вес <tex>w_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>. Требуется выполнить все работы, чтобы значение <tex>\sum w_{i} C_{i}</tex> было минимальным, где <tex>C_{i}</tex> {{---}} время окончания работы.<br />
}}<br />
<br />
Перед решением основной задачи рассмотрим более простые.<br />
<br />
==Просты задачи==<br />
<br />
===Задача 1===<br />
<tex dpi = "200"> 1 \mid p_i = 1\mid \sum C_i</tex><br />
<br />
'''Описание алгоритма'''<br />
<br />
Входные данные для этой задачи: число работ <tex>n</tex> <br />
<br />
Этот случай простейший. Для верного выполнения просто выставим работы по порядку, тогда ответом будет <tex>n</tex>, так как мы <tex>n</tex> раз сложим время выполнения одной работы, которое в нашем случае единица.<br />
<br />
===Задача 2===<br />
<tex dpi = "200"> 1 \mid p_i = 1\mid \sum w_i C_i</tex><br />
<br />
'''Описание алгоритма'''<br />
<br />
Входные данные для этой задачи: число работ <tex>n</tex> и вес каждой работы <tex>w_i</tex> <br />
<br />
Для верного выполнения просто выставим работы по порядку убывания весов, тогда ответом будет <tex> \sum_{i = 1}^n(w_i C_i)</tex>, так как мы <tex>n</tex> раз сложим время выполнения одной работы (которое в нашем случае единица) домноженное на вес этой работы.<br />
<br />
===Задача 3===<br />
<tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum f_i</tex><br />
{{Задача<br />
|definition=<br />
Дано <tex>n</tex> работ и один станок. Для каждой работы известно её время появления <tex>r_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>. Требуется выполнить все работы, чтобы значение <tex>\sum f_{i}</tex> было минимальным, где <tex>f_{i}</tex> {{---}} монотонная функция времени окончания работы <tex>C_{i}</tex> для работ <tex>i = 1, 2, ..., n</tex>.<br />
}}<br />
<br />
'''Описание алгоритма'''<br />
<br />
Нам нужно распределить <tex>n</tex> работ в разное время. Если мы назначим время <tex>t</tex> для работы <tex>i</tex> то цена будет <tex>f_i(t + 1)</tex>. Так как нужно заполнить <tex>n</tex> временных промежутков, задача может быть решена за <tex>O(n^3)</tex>. Функция <tex>f_i</tex> монотонно неубывающая, тогда работы в расписании надо располагать как можно раньше для получения верного решения. <tex>n</tex> временных интервалов <tex>t_i</tex> для <tex>n</tex> работ могут быть получены с помощью следующего алгоритма, где предполагается что работы нумеруются так:<br />
<br />
<tex> r_1 \leqslant r_2 \leqslant \ldots \leqslant r_n</tex> <br />
<br />
'''Псевдокод'''<br />
<br />
<tex>t_1 \leftarrow r_1 </tex><br />
'''for''' <tex> i \leftarrow 2</tex> '''to''' <tex>n</tex> '''do'''<br />
<tex> t_i \leftarrow </tex> '''max'''<tex>(r_i, \ t_{i-1} - 1)</tex><br />
<br />
==Описание алгоритма==<br />
Пусть <tex>time</tex> {{---}} текущий момент времени.<br/><br />
Для каждого очередного значения <tex>time</tex>, которое изменяется от <tex>0</tex> до времени окончания последней работы, будем:<br />
<ol><br />
<li> Выбирать работу <tex>j</tex> из множества невыполненных работ, у которой <tex>r_{i} \le time</tex>, а значение <tex>w_{i}</tex> максимально.</li><br />
<li> Если мы смогли найти работу <tex>j</tex>, то выполняем её в момент времени <tex>time</tex> и удаляем из множества невыполненных работ.</li><br />
<li> Увеличиваем <tex>time</tex> на один.</li><br />
</ol><br />
<br />
==Доказательство корректности алгоритма==<br />
{{Теорема<br />
|statement=<br />
Расписание, построенное данным алгоритмом, является корректным и оптимальным.<br />
|proof=<br />
Доказательство будем вести от противного.<br/><br />
Рассмотрим расписание <tex>S_{1}</tex>, полученное после выполнения нашего алгоритма, и оптимальное расписание <tex>S_{2}</tex>.<br/><br />
Возьмём первый момент времени <tex>t_{1}</tex>, когда расписания различаются. Пусть в этот момент времени в <tex>S_{1}</tex>, будет выполняться работа с весом <tex>w_{1}</tex>, а в <tex>S_{2}</tex> {{---}} работа с весом <tex>w_{2}</tex>.<br/><br />
Это первый момент, в котором расписания отличаются, значит в <tex>S_{2}</tex> работа с весом <tex>w_{1}</tex> выполнится в момент времени <tex>t_{2} > t_{1}</tex>.<br/><br />
Поменяем местами работы с весами <tex>w_{1}</tex> и <tex>w_{2}</tex> в <tex>S_{2}</tex> и полуим расписание <tex>S_{3}</tex>. Это возможно, потому что время появления этих работ не меньше <tex>t_{1}</tex>.<br/><br />
При такой перестановке ответы на задачу для <tex>S_{2}</tex> и <tex>S_{3}</tex> будут отличаться на <br />
<ul><tex>t_{1}w_{2} + t_{2}w_{1} - t_{1}w_{1} + t_{2}w_{2} = t_{1}(w_{2} - w_{1}) + t_{2}(w_{1} - w_{2}) = (t_{1} - t_{2})(w_{2} - w_{1})</tex></ul><br />
Первая скобка отрицательная: <tex>t_{1} < t_{2}</tex>. Вторая скобка тоже отрицательная из того, что в <tex>S_{1}</tex> работа с весом <tex>w_1</tex> выполняется раньше, значит её вес должен быть больше <tex>w_2</tex>.<br/><br />
Итого имеем, что ответ для <tex>S_{2}</tex> больше, чем ответ для <tex>S_{3}</tex>. Следовательно расписание <tex>S_2</tex> неоптимальное. Получили противоречие. Значит не существует такого момента времени, когда расписание <tex>S_{1}</tex> отличается от оптимального. Следовательно мы доказали, что оно оптимальное.<br />
}}<br />
<br />
==Псевдокод==<br />
<tex> S \leftarrow \{1 \dots n\}</tex><br />
<tex> \mathtt{time} \leftarrow 0</tex><br />
<tex> \mathtt{answer} \leftarrow 0</tex><br />
'''while''' <tex> S \neq \varnothing </tex><br />
<tex> j \leftarrow null </tex><br />
'''if''' <tex> i \in S</tex> '''and''' <tex> r_{i} \leqslant \mathtt{time}</tex> '''and''' <tex>w_i \geqslant max_{j = 1}^n w_j</tex><br />
<tex> j \leftarrow i </tex><br />
'''if''' <tex>j \neq null </tex><br />
<tex> S \leftarrow S \setminus j</tex><br />
<tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot w_{j}</tex><br />
<tex> \mathtt{time++}</tex><br />
<br />
==Сложность алгоритма==<br />
Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \max_{i = 1}^n r_{i}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, [[Wikipedia:ru:Очередь с приоритетом (программирование)|очередь с приоритетами]]. Значит общее время работы алгоритма <tex>O((n + \max_{i = 1}^n r_{i})\log n)</tex><br />
<br />
<br />
== Источники информации ==<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 19 - 20<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 38 - 39<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 84 - 85<br />
* Лазарев А.А., Мусатова Е.Г., Кварацхелия А.Г., Гафаров Е.Р. Пособие по теории расписаний.<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Теория расписаний]]</div>Sergej Arkhipovhttp://neerc.ifmo.ru/wiki/index.php?title=Flow_shop&diff=47289Flow shop2015-06-02T21:30:04Z<p>Sergej Arkhipov: </p>
<hr />
<div>== Описание ==<br />
{{Определение<br />
|definition =<br />
'''Flow shop''' ('''<tex>F_{m}</tex>''' в нотации Грэхема): В системе находится <tex> m </tex> машин, работающих параллельно. Машины упорядочены. Каждая работа должна быть выполнена последовательно на всех машинах с первой по последнюю.}}<br />
<br />
Рассмотрим пример: <tex>F \mid p_{ij} = 1 \mid C_{max}</tex><br />
<br />
Допустим, у нас <tex>n</tex> работ и <tex>m</tex> машин. В начальный момент времени мы можем начать обрабатывать любую работу на первой машине. В следующий момент на первой машине можно обрабатывать следующую работу, а на второй перейдёт предыдущая работа с первой машины, и так далее. Таким образом, на выполнение всех работ у нас уйдёт <tex>n + m - 1</tex> единиц времени. Проиллюстрируем это диаграммой Гантта для случая <tex>n = 6, m = 5</tex>:<br />
'''0 1 2 3 4 5 6 7 8 9 10'''<br />
-------------------------------------------<br />
'''M_1''' | 1 2 3 4 5 6 - - - -<br />
'''M_2''' | - 1 2 3 4 5 6 - - -<br />
'''M_3''' | - - 1 2 3 4 5 6 - -<br />
'''M_4''' | - - - 1 2 3 4 5 6 -<br />
'''M_5''' | - - - - 1 2 3 4 5 6<br />
<br />
Заметим, что в данном случае <tex>p_{ij}</tex> может быть равно не только единице, но и любой константе.<br />
<br />
{{Утверждение<br />
|statement = Любая задача вида <tex>F \mid p_{ij} = 1 \mid ? </tex> сводится к соответствующей задаче вида <tex>1 \mid p_{ij} = 1 \mid ?</tex>. <br />
|proof = <br />
Поскольку работа всегда заканчивает выполняться на последней машине, нас интересуют только времена завершения работ на последней машине. Также очевидно, что последняя машина может начать работать только в момент времени <tex> m - 1 </tex>. Оказывается, что любое решение задачи <tex> 1 \mid p_{ij} = 1 \mid ? </tex> с дедлайнами, уменьшенными на <tex> m - 1 </tex> можно преобразовать в оптимальное расписание для задачи <tex>F \mid p_{ij} = 1 \mid ? </tex>. Докажем это.<br />
<br />
Возьмем оптимальное расписание для соответствующей задачи с одним станком, выполним работы в этом порядке на первой машине, затем на второй машине, начиная с момента времени <tex> 1 </tex>, и так далее, до выполнения на последней машине, начиная с <tex> m - 1 </tex>. Это расписание корректно и соблюдает все дедлайны. Поскольку целевая функция совпадает с соответствующей функцией для задачи на одном станке, оно оптимально и для данной задачи.<br />
}}<br />
<br />
Примером применения этого утверждения может служить [[Fpij1sumwu|задача]] <br />
<br />
Задачи с произвольными временами выполнения работ почти все являются NP-трудными.<br />
<br />
== Задача Джонсона о двух станках <tex>F_2 \mid \mid C_{max}</tex> ==<br />
<br />
Это единственная из flow shop задач с произвольными временами выполнения работ, которая решается за полиномиальное время.<br />
<br />
Приведём здесь решение задачи без доказательства, его можно посмотреть в [1].<br />
<br />
Оптимальное расписание для первой и второй машины будет совпадать. Таким образом, нам требуется найти порядок, в котором будут выполняться работы на каждой машине.<br />
<br />
Алгоритм такой: возьмём два пустых списка. Будем рассматривать работы в порядке возрастания <tex>min(p_1, p_2)</tex>, то есть, минимума из времён выполнения данной работы на первой и второй машине. Если у работы <tex>p_1 \le p_2</tex>, то добавим её в конец первого списка. В противном случае, добавим её в начало второго списка. Итоговое расписание — это конкатенация первого и второго списков.<br />
<br />
Псевдокод:<br />
J - множество работ<br />
Head <tex> \leftarrow \emptyset </tex><br />
Tail <tex> \leftarrow \emptyset </tex><br />
'''while''' J <tex> \ne \emptyset </tex> <br />
'''do'''<br />
I <tex> \leftarrow </tex> работа с минимальным значением <tex>min(p_1, p_2)</tex><br />
'''if''' <tex>p_1 <= p_2</tex> Head <tex> \leftarrow </tex> Head <tex>\circ</tex> I<br />
'''else''' Tail <tex> \leftarrow </tex> I <tex>\circ</tex> Tail<br />
J <tex> \leftarrow </tex> J <tex> \backslash </tex> I<br />
Result <tex> \leftarrow </tex> Head <tex>\circ</tex> Tail<br />
<br />
== Задача Джонсона о двух станках с прерываниями <tex>F_2 \mid pmtn \mid C_{max}</tex> ==<br />
<br />
Оптимальное решение этой задачи совпадает с решением задачи <tex>F_2 \mid \mid C_{max}</tex>, приведённой выше. Докажем это.<br />
<br />
Пусть у нас есть оптимальное расписание для задачи <tex>F_2 \mid pmtn \mid C_{max}</tex>. Покажем, что его за конечное число шагов можно преобразовать к расписанию без прерываний, не изменив при это значение <tex>C_{max}</tex> .<br />
<br />
Рассмотрим первую машину. Допустим, что некоторая работа <tex> J </tex> выполняется в <tex> 2 </tex> или более разных промежутка времени. Тогда передвинем более ранний промежуток вправо по оси времени так, чтоб он заканчивался в тот момент, когда начинается второй промежуток, при этом работы, которые были между этими двумя промежутками, сдвинем влево на длину первого промежутка. Расписание при этом осталось корректным, так как работы на машинах по-прежнему не пересекаются, и каждая работа на второй машине делается после того, как она сделана на первой: работа <tex> J </tex> может начать выполняться на второй машине только после того, как она целиком выполнится на первой, то есть уже после конца второго промежутка; а время окончания выполнения остальных работ на первой машине неувеличилось.<br />
Важно, что подобная операция не увеличивает <tex> C_{max} </tex>.<br />
<br />
Будем повторять эту операцию до тех пор, пока на первой машине все работы не станут выполняться без прерываний. Так как количество прерываний конечно, а такая операция уменьшает их количество на один, этот процесс конечен.<br />
<br />
Теперь избавимся от прерываний на второй машине. Точно так же рассмотрим работу, разбитую на два или более промежутка. Передвинем более поздний промежуток к концу более раннего, а работы между ними сдвинем вправо. Доказательство корректности измененного расписания аналогично доказательству для первой машины. Будем повторять данную операцию, пока на второй машине присутствуют прерывания.<br />
<br />
Таким образом, мы получили корректное расписание без прерываний, не изменив при этом значение <tex>C_{max}</tex>, что и требовалось доказать.<br />
<br />
== См. также ==<br />
* [[Классификация задач]]<br />
* [[Fpij1sumwu|<tex>F \mid p_{ij} = 1 \mid \sum w_i u_i</tex>]]<br />
<br />
== Литература ==<br />
*[1][http://books.google.ru/books?id=FrUytMqlCv8C&printsec=frontcover&dq=scheduling+algorithms&hl=ru&sa=X&ei=0MPMT4HqKYSk4gSBm6gp&sqi=2&ved=0CDEQ6AEwAA#v=onepage&q=scheduling%20algorithms&f=false Scheduling Algorithms, Peter Brucker]</div>Sergej Arkhipovhttp://neerc.ifmo.ru/wiki/index.php?title=1ripi1sumwc&diff=472881ripi1sumwc2015-06-02T21:27:38Z<p>Sergej Arkhipov: </p>
<hr />
<div><tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum w_i C_i</tex><br />
<br />
{{Задача<br />
|definition=<br />
Дано <tex>n</tex> работ и один станок. Для каждой работы известно её время появления <tex>r_{i}</tex> и вес <tex>w_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>. Требуется выполнить все работы, чтобы значение <tex>\sum w_{i} C_{i}</tex> было минимальным, где <tex>C_{i}</tex> {{---}} время окончания работы.<br />
}}<br />
<br />
Перед решением основной задачи рассмотрим более простые.<br />
<br />
==Просты задачи==<br />
<br />
===Задача 1===<br />
<tex dpi = "200"> 1 \mid p_i = 1\mid \sum C_i</tex><br />
<br />
'''Описание алгоритма'''<br />
<br />
Входные данные для этой задачи: число работ <tex>n</tex> <br />
<br />
Этот случай простейший. Для верного выполнения просто выставим работы по порядку, тогда ответом будет <tex>n</tex>, так как мы <tex>n</tex> раз сложим время выполнения одной работы, которое в нашем случае единица.<br />
<br />
===Задача 2===<br />
<tex dpi = "200"> 1 \mid p_i = 1\mid \sum w_i C_i</tex><br />
<br />
'''Описание алгоритма'''<br />
<br />
Входные данные для этой задачи: число работ <tex>n</tex> и вес каждой работы <tex>w_i</tex> <br />
<br />
Для верного выполнения просто выставим работы по порядку убывания весов, тогда ответом будет <tex> \sum_{i = 1}^n(w_i C_i)</tex>, так как мы <tex>n</tex> раз сложим время выполнения одной работы (которое в нашем случае единица) домноженное на вес этой работы.<br />
<br />
===Задача 3===<br />
<tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum f_i</tex><br />
{{Задача<br />
|definition=<br />
Дано <tex>n</tex> работ и один станок. Для каждой работы известно её время появления <tex>r_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>. Требуется выполнить все работы, чтобы значение <tex>\sum f_{i}</tex> было минимальным, где <tex>f_{i}</tex> {{---}} монотонная функция времени окончания работы <tex>C_{i}</tex> для работ <tex>i = 1, 2, ..., n</tex>.<br />
}}<br />
<br />
'''Описание алгоритма'''<br />
<br />
Нам нужно распределить <tex>n</tex> работ в разное время. Если мы назначим время <tex>t</tex> для работы <tex>i</tex> то цена будет <tex>f_i(t + 1)</tex>. Так как нужно заполнить <tex>n</tex> временных промежутков, задача может быть решена за <tex>O(n^3)</tex>. Функция <tex>f_i</tex> монотонно неубывающая, тогда работы в расписании надо располагать как можно раньше для получения верного решения. <tex>n</tex> временных интервалов <tex>t_i</tex> для <tex>n</tex> работ могут быть получены с помощью следующего алгоритма, где предполагается что работы нумеруются так:<br />
<br />
<tex> r_1 \leqslant r_2 \leqslant \ldots \leqslant r_n</tex> <br />
<br />
'''Псевдокод'''<br />
<br />
<tex>t_1 \leftarrow r_1 </tex><br />
'''for''' <tex> i \leftarrow 2</tex> '''to''' <tex>n</tex> '''do'''<br />
<tex> t_i \leftarrow </tex> '''max'''<tex>(r_i, \ t_{i-1} - 1)</tex><br />
<br />
==Описание алгоритма==<br />
Пусть <tex>time</tex> {{---}} текущий момент времени.<br/><br />
Для каждого очередного значения <tex>time</tex>, которое изменяется от <tex>0</tex> до времени окончания последней работы, будем:<br />
<ol><br />
<li> Выбирать работу <tex>j</tex> из множества невыполненных работ, у которой <tex>r_{i} \le time</tex>, а значение <tex>w_{i}</tex> максимально.</li><br />
<li> Если мы смогли найти работу <tex>j</tex>, то выполняем её в момент времени <tex>time</tex> и удаляем из множества невыполненных работ.</li><br />
<li> Увеличиваем <tex>time</tex> на один.</li><br />
</ol><br />
<br />
==Доказательство корректности алгоритма==<br />
{{Теорема<br />
|statement=<br />
Расписание, построенное данным алгоритмом, является корректным и оптимальным.<br />
|proof=<br />
Доказательство будем вести от противного.<br/><br />
Рассмотрим расписание <tex>S_{1}</tex>, полученное после выполнения нашего алгоритма, и оптимальное расписание <tex>S_{2}</tex>.<br/><br />
Возьмём первый момент времени <tex>t_{1}</tex>, когда расписания различаются. Пусть в этот момент времени в <tex>S_{1}</tex>, будет выполняться работа с весом <tex>w_{1}</tex>, а в <tex>S_{2}</tex> {{---}} работа с весом <tex>w_{2}</tex>.<br/><br />
Это первый момент, в котором расписания отличаются, значит в <tex>S_{2}</tex> работа с весом <tex>w_{1}</tex> выполнится в момент времени <tex>t_{2} > t_{1}</tex>.<br/><br />
Поменяем местами работы с весами <tex>w_{1}</tex> и <tex>w_{2}</tex> в <tex>S_{2}</tex> и полуим расписание <tex>S_{3}</tex>. Это возможно, потому что время появления этих работ не меньше <tex>t_{1}</tex>.<br/><br />
При такой перестановке ответы на задачу для <tex>S_{2}</tex> и <tex>S_{3}</tex> будут отличаться на <br />
<ul><tex>t_{1}w_{2} + t_{2}w_{1} - t_{1}w_{1} + t_{2}w_{2} = t_{1}(w_{2} - w_{1}) + t_{2}(w_{1} - w_{2}) = (t_{1} - t_{2})(w_{2} - w_{1})</tex></ul><br />
Первая скобка отрицательная: <tex>t_{1} < t_{2}</tex>. Вторая скобка тоже отрицательная из того, что в <tex>S_{1}</tex> работа с весом <tex>w_1</tex> выполняется раньше, значит её вес должен быть больше <tex>w_2</tex>.<br/><br />
Итого имеем, что ответ для <tex>S_{2}</tex> больше, чем ответ для <tex>S_{3}</tex>. Следовательно расписание <tex>S_2</tex> неоптимальное. Получили противоречие. Значит не существует такого момента времени, когда расписание <tex>S_{1}</tex> отличается от оптимального. Следовательно мы доказали, что оно оптимальное.<br />
}}<br />
<br />
==Псевдокод==<br />
<tex> S \leftarrow \{1 \dots n\}</tex><br />
<tex> \mathtt{time} \leftarrow 0</tex><br />
<tex> \mathtt{answer} \leftarrow 0</tex><br />
'''while''' <tex> S \neq \varnothing </tex><br />
<tex> j \leftarrow null </tex><br />
'''if''' <tex> i \in S</tex> '''and''' <tex> r_{i} \leqslant \mathtt{time}</tex> '''and''' <tex>w_i \geqslant max_{j = 1}^n w_j</tex><br />
<tex> j \leftarrow i </tex><br />
'''if''' <tex>j \neq null </tex><br />
<tex> S \leftarrow S \setminus j</tex><br />
<tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot w_{j}</tex><br />
<tex> \mathtt{time++}</tex><br />
<br />
==Сложность алгоритма==<br />
Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \max_{i = 1}^n r_{i}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, [[Wikipedia:ru:Очередь с приоритетом (программирование)|очередь с приоритетами]]. Значит общее время работы алгоритма <tex>O((n + \max_{i = 1}^n r_{i})\log n)</tex><br />
<br />
<br />
== Источники информации ==<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 19 - 20<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 38 - 39<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 84 - 85<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Теория расписаний]]</div>Sergej Arkhipovhttp://neerc.ifmo.ru/wiki/index.php?title=1ripi1sumwc&diff=472871ripi1sumwc2015-06-02T21:14:00Z<p>Sergej Arkhipov: </p>
<hr />
<div><tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum w_i C_i</tex><br />
<br />
{{Задача<br />
|definition=<br />
Дано <tex>n</tex> работ и один станок. Для каждой работы известно её время появления <tex>r_{i}</tex> и вес <tex>w_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>. Требуется выполнить все работы, чтобы значение <tex>\sum w_{i} C_{i}</tex> было минимальным, где <tex>C_{i}</tex> {{---}} время окончания работы.<br />
}}<br />
<br />
Перед решением основной задачи рассмотрим более простые.<br />
<br />
==Просты задачи==<br />
<br />
===Задача 1===<br />
<tex dpi = "200"> 1 \mid p_i = 1\mid \sum C_i</tex><br />
<br />
'''Описание алгоритма'''<br />
<br />
Входные данные для этой задачи: число работ <tex>n</tex> <br />
<br />
Этот случай простейший. Для верного выполнения просто выставим работы по порядку, тогда ответом будет <tex>n</tex>, так как мы <tex>n</tex> раз сложим время выполнения одной работы, которое в нашем случае единица.<br />
<br />
===Задача 2===<br />
<tex dpi = "200"> 1 \mid p_i = 1\mid \sum w_i C_i</tex><br />
<br />
'''Описание алгоритма'''<br />
<br />
Входные данные для этой задачи: число работ <tex>n</tex> и вес каждой работы <tex>w_i</tex> <br />
<br />
Для верного выполнения просто выставим работы по порядку убывания весов, тогда ответом будет <tex> \sum_{i = 1}^n(w_i C_i)</tex>, так как мы <tex>n</tex> раз сложим время выполнения одной работы (которое в нашем случае единица) домноженное на вес этой работы.<br />
<br />
===Задача 3===<br />
<tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum f_i</tex><br />
{{Задача<br />
|definition=<br />
Дано <tex>n</tex> работ и один станок. Для каждой работы известно её время появления <tex>r_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>. Требуется выполнить все работы, чтобы значение <tex>\sum f_{i}</tex> было минимальным, где <tex>f_{i}</tex> {{---}} монотонная функция времени окончания работы <tex>C_{i}</tex> для работ <tex>i = 1, 2, ..., n</tex>.<br />
}}<br />
<br />
'''Описание алгоритма'''<br />
<br />
Нам нужно распределить <tex>n</tex> работ в разное время. Если мы назначим время <tex>t</tex> для работы <tex>i</tex> то цена будет <tex>f_i(t + 1)</tex>. Так как нужно рассмотреть <tex>n</tex> временных промежутков, задача может быть решена за <tex>O(n^3)</tex>. Функция <tex>f_i</tex> монотонно неубывающая, тогда работы в расписании надо располагать как можно раньше для получения верного решения. <tex>n</tex> временных интервалов <tex>t_i</tex> для <tex>n</tex> работ могут быть получены с помощью следующего алгоритма, где предполагается что работы нумеруются так:<br />
<br />
<tex> r_1 \leqslant r_2 \leqslant \ldots \leqslant r_n</tex> <br />
<br />
'''Псевдокод'''<br />
<br />
<tex>t_1 \leftarrow r_1 </tex><br />
'''for''' <tex> i \leftarrow 2</tex> '''to''' <tex>n</tex> '''do'''<br />
<tex> t_i \leftarrow </tex> '''max'''<tex>(r_i, \ t_{i-1} - 1)</tex><br />
<br />
==Описание алгоритма==<br />
Пусть <tex>time</tex> {{---}} текущий момент времени.<br/><br />
Для каждого очередного значения <tex>time</tex>, которое изменяется от <tex>0</tex> до времени окончания последней работы, будем:<br />
<ol><br />
<li> Выбирать работу <tex>j</tex> из множества невыполненных работ, у которой <tex>r_{i} \le time</tex>, а значение <tex>w_{i}</tex> максимально.</li><br />
<li> Если мы смогли найти работу <tex>j</tex>, то выполняем её в момент времени <tex>time</tex> и удаляем из множества невыполненных работ.</li><br />
<li> Увеличиваем <tex>time</tex> на один.</li><br />
</ol><br />
<br />
==Доказательство корректности алгоритма==<br />
{{Теорема<br />
|statement=<br />
Расписание, построенное данным алгоритмом, является корректным и оптимальным.<br />
|proof=<br />
Доказательство будем вести от противного.<br/><br />
Рассмотрим расписание <tex>S_{1}</tex>, полученное после выполнения нашего алгоритма, и оптимальное расписание <tex>S_{2}</tex>.<br/><br />
Возьмём первый момент времени <tex>t_{1}</tex>, когда расписания различаются. Пусть в этот момент времени в <tex>S_{1}</tex>, будет выполняться работа с весом <tex>w_{1}</tex>, а в <tex>S_{2}</tex> {{---}} работа с весом <tex>w_{2}</tex>.<br/><br />
Это первый момент, в котором расписания отличаются, значит в <tex>S_{2}</tex> работа с весом <tex>w_{1}</tex> выполнится в момент времени <tex>t_{2} > t_{1}</tex>.<br/><br />
Поменяем местами работы с весами <tex>w_{1}</tex> и <tex>w_{2}</tex> в <tex>S_{2}</tex> и полуим расписание <tex>S_{3}</tex>. Это возможно, потому что время появления этих работ не меньше <tex>t_{1}</tex>.<br/><br />
При такой перестановке ответы на задачу для <tex>S_{2}</tex> и <tex>S_{3}</tex> будут отличаться на <br />
<ul><tex>t_{1}w_{2} + t_{2}w_{1} - t_{1}w_{1} + t_{2}w_{2} = t_{1}(w_{2} - w_{1}) + t_{2}(w_{1} - w_{2}) = (t_{1} - t_{2})(w_{2} - w_{1})</tex></ul><br />
Первая скобка отрицательная: <tex>t_{1} < t_{2}</tex>. Вторая скобка тоже отрицательная из того, что в <tex>S_{1}</tex> работа с весом <tex>w_1</tex> выполняется раньше, значит её вес должен быть больше <tex>w_2</tex>.<br/><br />
Итого имеем, что ответ для <tex>S_{2}</tex> больше, чем ответ для <tex>S_{3}</tex>. Следовательно расписание <tex>S_2</tex> неоптимальное. Получили противоречие. Значит не существует такого момента времени, когда расписание <tex>S_{1}</tex> отличается от оптимального. Следовательно мы доказали, что оно оптимальное.<br />
}}<br />
<br />
==Псевдокод==<br />
<tex> S \leftarrow \{1 \dots n\}</tex><br />
<tex> \mathtt{time} \leftarrow 0</tex><br />
<tex> \mathtt{answer} \leftarrow 0</tex><br />
'''while''' <tex> S \neq \varnothing </tex><br />
<tex> j \leftarrow null </tex><br />
'''if''' <tex> i \in S</tex> '''and''' <tex> r_{i} \leqslant \mathtt{time}</tex> '''and''' <tex>\max w_{i} </tex><br />
<tex> j \leftarrow i </tex><br />
'''if''' <tex>j \neq null </tex><br />
<tex> S \leftarrow S \setminus j</tex><br />
<tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot w_{j}</tex><br />
<tex> \mathtt{time++}</tex><br />
<br />
==Сложность алгоритма==<br />
Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \max r_{i}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, [[Wikipedia:ru:Очередь с приоритетом (программирование)|очередь с приоритетами]]. Значит общее время работы алгоритма <tex>O((n + \max r_{i})\log n)</tex><br />
<br />
<br />
== Источники информации ==<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 19 - 20<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 38 - 39<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 84 - 85<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Теория расписаний]]</div>Sergej Arkhipovhttp://neerc.ifmo.ru/wiki/index.php?title=1ripi1sumwc&diff=472841ripi1sumwc2015-06-02T19:45:20Z<p>Sergej Arkhipov: </p>
<hr />
<div><tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum w_i C_i</tex><br />
<br />
{{Задача<br />
|definition=<br />
Дано <tex>n</tex> работ и один станок. Для каждой работы известно её время появления <tex>r_{i}</tex> и вес <tex>w_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>. Требуется выполнить все работы, чтобы значение <tex>\sum w_{i} C_{i}</tex> было минимальным, где <tex>C_{i}</tex> {{---}} время окончания работы.<br />
}}<br />
<br />
Перед решением основной задачи рассмотрим более простые.<br />
<br />
<br />
==Задача 1==<br />
<tex dpi = "200"> 1 \mid p_i = 1\mid \sum C_i</tex><br />
<br />
'''Описание алгоритма'''<br />
<br />
Входные данные для этой задачи: число работ <tex>n</tex> <br />
<br />
Этот случай простейший. Для верного выполнения просто выставим работы по порядку, тогда ответом будет <tex>n</tex>, так как мы <tex>n</tex> раз сложим время выполнения одной работы, которое в нашем случае единица.<br />
<br />
==Задача 2==<br />
<tex dpi = "200"> 1 \mid p_i = 1\mid \sum w_i C_i</tex><br />
<br />
'''Описание алгоритма'''<br />
<br />
Входные данные для этой задачи: число работ <tex>n</tex> и вес каждой работы <tex>w_i</tex> <br />
<br />
Для верного выполнения просто выставим работы по порядку, тогда ответом будет <tex> \sum_{i = 1}^n(w_i)</tex>, так как мы <tex>n</tex> раз сложим время выполнения одной работы (которое в нашем случае единица) домноженное на вес этой работы.<br />
<br />
==Задача 3==<br />
<tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum f_i</tex><br />
{{Задача<br />
|definition=<br />
Дано <tex>n</tex> работ и один станок. Для каждой работы известно её время появления <tex>r_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>. Требуется выполнить все работы, чтобы значение <tex>\sum f_{i}</tex> было минимальным, где <tex>f_{i}</tex> {{---}} монотонная функция времени окончания работы <tex>C_{i}</tex> для работ <tex>i = 1, 2, ..., n</tex>.<br />
}}<br />
<br />
'''Описание алгоритма'''<br />
<br />
Нам нужно распределить <tex>n</tex> работ в разное время. Если мы назначим время <tex>t</tex> для работы <tex>i</tex> то цена будет <tex>f_i(t + 1)</tex>. Так как нужно рассмотреть <tex>n</tex> временных промежутков, задача может быть решена за <tex>O(n^3)</tex>. Функция <tex>f_i</tex> монотонно неубывающая, тогда работы в расписании надо располагать как можно раньше для получения верного решения. <tex>n</tex> временных интервалов <tex>t_i</tex> для <tex>n</tex> работ могут быть получены с помощью следующего алгоритма, где предполагается что работы нумеруются так:<br />
<br />
<tex> r_1 \leqslant r_2 \leqslant \ldots \leqslant r_n</tex> <br />
<br />
'''Псевдокод'''<br />
<br />
<tex>t_1 \leftarrow r_1 </tex><br />
'''for''' <tex> i \leftarrow 2</tex> '''to''' <tex>n</tex> '''do'''<br />
<tex> t_i \leftarrow </tex> '''max'''<tex>(r_i, \ t_{i-1} - 1)</tex><br />
<br />
==Задача 4==<br />
<tex dpi = "200"> 1 \mid r_j,p_j = p \mid \sum f_j</tex><br />
<br />
Вес всех работ <tex>w_i \geqslant 0</tex><br />
Для всех функций <tex>f_1, f_2, \ldots, f_n</tex> выполняются следующие свойства:<br />
<br />
<tex>f_j</tex> неубывающая функция для <tex>j = 1, 2, \ldots, n</tex><br />
<br />
<tex>f_i - f_j</tex> неубывающая функция для <tex>i, j = 1, 2, \ldots, n</tex> при <tex>i < j </tex><br />
<br />
<tex>\sum w_i C_i</tex> являются функцией <tex>f_j(C_j)</tex>, так что по факту решаем задачу <tex>1 \mid r_j,p_j = p \mid \sum w_i C_i </tex><br />
<br />
'''Описание алгоритма'''<br />
<br />
Пусть перед началом алгоритма работы пронумерованы в соответствии с свойствами для функций <tex>f_1, f_2, \ldots, f_n</tex><br />
<br />
Пояснение для псевдокода:<br />
<br />
<tex>T</tex> это множество {<tex>r_j + lp \mid j = 1, 2, \ldots, n; l = 0, 1, \ldots, n-1 </tex>}<br />
<br />
<tex>F_k'(s,e)</tex> это <tex>min(F_{k-1}(s,t_k)+F_{k-1}(t_k + p, e)+f_k(t_k + p) \mid t_k \in T, max(s, r_k) \leqslant t_k \leqslant e-p)</tex><br />
<br />
'''Псевдокод'''<br />
<br />
'''for''' <tex> \forall s, e \in T \ with \ s \leqslant e</tex> '''do'''<br />
<tex>F_0(s,e) \leftarrow 0</tex><br />
'''for''' <tex>k \leftarrow 1</tex> '''to''' <tex>n</tex> '''do'''<br />
'''for''' <tex> \forall s, e \in T \ with \ s \leqslant e</tex> '''do'''<br />
<tex><br />
F_k(s,e) \leftarrow<br />
\begin{cases}<br />
F_{k-1}(s,e) \ if\ r_k \notin [s - p,e);\\<br />
F_k'(s,e) \ overwise; <br />
\end{cases}<br />
</tex><br />
'''Вычислить''' <tex>F_n($$ \min_{i=1}^n (r_i) $$, max_{t \in T}(t+p) )</tex><br />
==Описание алгоритма==<br />
Пусть <tex>time</tex> {{---}} текущий момент времени.<br/><br />
Для каждого очередного значения <tex>time</tex>, которое изменяется от <tex>0</tex> до времени окончания последней работы, будем:<br />
<ol><br />
<li> Выбирать работу <tex>j</tex> из множества невыполненных работ, у которой <tex>r_{i} \le time</tex>, а значение <tex>w_{i}</tex> максимально.</li><br />
<li> Если мы смогли найти работу <tex>j</tex>, то выполняем её в момент времени <tex>time</tex> и удаляем из множества невыполненных работ.</li><br />
<li> Увеличиваем <tex>time</tex> на один.</li><br />
</ol><br />
<br />
==Доказательство корректности алгоритма==<br />
{{Теорема<br />
|statement=<br />
Расписание, построенное данным алгоритмом, является корректным и оптимальным.<br />
|proof=<br />
Доказательство будем вести от противного.<br/><br />
Рассмотрим расписание <tex>S_{1}</tex>, полученное после выполнения нашего алгоритма, и оптимальное расписание <tex>S_{2}</tex>.<br/><br />
Возьмём первый момент времени <tex>t_{1}</tex>, когда расписания различаются. Пусть в этот момент времени в <tex>S_{1}</tex>, будет выполняться работа с весом <tex>w_{1}</tex>, а в <tex>S_{2}</tex> {{---}} работа с весом <tex>w_{2}</tex>.<br/><br />
Это первый момент, в котором расписания отличаются, значит в <tex>S_{2}</tex> работа с весом <tex>w_{1}</tex> выполнится в момент времени <tex>t_{2} > t_{1}</tex>.<br/><br />
Поменяем местами работы с весами <tex>w_{1}</tex> и <tex>w_{2}</tex> в <tex>S_{2}</tex> и полуим расписание <tex>S_{3}</tex>. Это возможно, потому что время появления этих работ не меньше <tex>t_{1}</tex>.<br/><br />
При такой перестановке ответы на задачу для <tex>S_{2}</tex> и <tex>S_{3}</tex> будут отличаться на <br />
<ul><tex>t_{1}w_{2} + t_{2}w_{1} - t_{1}w_{1} + t_{2}w_{2} = t_{1}(w_{2} - w_{1}) + t_{2}(w_{1} - w_{2}) = (t_{1} - t_{2})(w_{2} - w_{1})</tex></ul><br />
Первая скобка отрицательная: <tex>t_{1} < t_{2}</tex>. Вторая скобка тоже отрицательная из того, что в <tex>S_{1}</tex> работа с весом <tex>w_1</tex> выполняется раньше, значит её вес должен быть больше <tex>w_2</tex>.<br/><br />
Итого имеем, что ответ для <tex>S_{2}</tex> больше, чем ответ для <tex>S_{3}</tex>. Следовательно расписание <tex>S_2</tex> неоптимальное. Получили противоречие. Значит не существует такого момента времени, когда расписание <tex>S_{1}</tex> отличается от оптимального. Следовательно мы доказали, что оно оптимальное.<br />
}}<br />
<br />
==Псевдокод==<br />
<tex> S \leftarrow \{1 \dots n\}</tex><br />
<tex> \mathtt{time} \leftarrow 0</tex><br />
<tex> \mathtt{answer} \leftarrow 0</tex><br />
'''while''' <tex> S \neq \varnothing </tex><br />
<tex> j \leftarrow null </tex><br />
'''if''' <tex> i \in S</tex> '''and''' <tex> r_{i} \leq \mathtt{time}</tex> '''and''' <tex>\max w_{i} </tex><br />
<tex> j \leftarrow i </tex><br />
'''if''' <tex>j \neq null </tex><br />
<tex> S \leftarrow S \setminus j</tex><br />
<tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot w_{j}</tex><br />
<tex> \mathtt{time++}</tex><br />
<br />
==Сложность алгоритма==<br />
Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \max r_{i}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, очередь с приоритетами. Значит общее время работы алгоритма <tex>O((n + \max r_{i})\log n)</tex><br />
<br />
<br />
== Источники информации ==<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 19 - 20<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 38 - 39<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 84 - 85<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 101 - 102<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Теория расписаний]]</div>Sergej Arkhipovhttp://neerc.ifmo.ru/wiki/index.php?title=Fpij1sumwu&diff=47280Fpij1sumwu2015-06-02T19:26:44Z<p>Sergej Arkhipov: </p>
<hr />
<div><tex dpi = "200">F \mid p_{ij} = 1 \mid \sum w_iu_i</tex><br />
{{Задача<br />
|definition=<br />
Дано <tex>m</tex> станков, на которых нужно обработать <tex>n</tex> деталей. Каждую деталь нужно обработать по очереди на всех станках. Любая работа на любом станке выполняется единицу времени. Для каждой работы есть дедлайн <tex>d_i</tex> {{---}} время, до которого она должна быть закончена, и штраф <tex>w_i</tex>, который нужно будет выплатить в случае, если работа была закончена после <tex>d_i</tex>. Необходимо минимизировать суммарный штраф, который придется выплатить.<br />
}}<br />
==Описание алгоритма==<br />
<br />
{{Утверждение<br />
|statement=Существует оптимальное расписание, в котором каждая работа делается непрерывно.<br />
|proof=<br />
Рассмотрим расписание, в котором есть работы, которые делаются не непрерывно. Рассмотрим самый ранний разрыв: работа <tex>i</tex> делалась в моменты <tex>t(i), t(i)+1, \ldots, t(i)+k</tex>, где <tex>k<m</tex>, но не делалась в момент времени <tex>t(i)+k+1</tex>. Докажем, что в момент времени <tex>t(i)+k+1</tex>, <tex>k+1</tex>-й станок простаивает и можно продолжить делать <tex>i</tex>-ю работу. <br />
<br />
Пусть в момент времени <tex>t(i)+k+1</tex> на <tex>k+1</tex>-м станке делается работа <tex>j</tex>. <br />
В <tex>t(i)+k</tex>-й момент времени <tex>k</tex>-й станок был занят выполнением <tex>i</tex>-й работы, а значит, не мог выполнять <tex>j</tex>-ю. Значит, разрыв был раньше, что противоречит тому, что был выбран самый ранний разрыв. Значит, в <tex>t(i)+k+1</tex>-й момент <tex>k+1</tex>-й станок свободен и туда можно поставить <tex>i</tex>-ю работу, устранив разрыв. <br />
<br />
После устранения каждого разрыва получим расписание без разрывов, в котором каждая работа заканчивает выполняться не позже, чем в изначальном.<br />
}}<br />
<br />
По этому утверждению, если работу <tex>i</tex> начали делать в <tex>t(i)</tex>, то закончена она будет в <tex>t(i)+m</tex>. Найдем время <tex>d'_i</tex> такое, что начав выполнять в него работу <tex>i</tex>, мы успеем выполнить ее до <tex>d_i</tex>: <tex>d'_i = d_i - m</tex>. Таким образом, вычтя из всех <tex>d_i</tex> число <tex>m</tex>, мы свели задачу к <tex>1 \mid p_i = 1 \mid \sum w_i U_i</tex>. <br />
<br />
Построив оптимальное расписание для <tex>1 \mid p_i = 1 \mid \sum w_i U_i</tex>, мы найдем времена, в которые нужно начинать выполнять работы. По утверждению выше, работы можно выполнять непрерывно.<br />
<br />
==Сложность алгоритма==<br />
Задача <tex>F \mid p_{ij} = 1 \mid \sum w_iu_i</tex> за <tex>O(n)</tex> сводится к задаче <tex>1 \mid p_i = 1 \mid \sum w_iu_i</tex>. Задача <tex>1 \mid p_i = 1 \mid \sum u_iw_i</tex> решается за <tex>O(n \log n)</tex>. После решения этой задачи, нужно вывести ответ, имеющий размер <tex>O(nm)</tex>. Значит, итоговая сложность алгоритма {{---}} <tex>O(n \log n + nm)</tex>.</div>Sergej Arkhipovhttp://neerc.ifmo.ru/wiki/index.php?title=Flow_shop&diff=47278Flow shop2015-06-02T19:17:55Z<p>Sergej Arkhipov: </p>
<hr />
<div>== Описание ==<br />
{{Определение<br />
|definition =<br />
'''Flow shop''' ('''<tex>F_{m}</tex>''' в нотации Грэхема): В системе находится <tex> m </tex> машин, работающих параллельно. Машины упорядочены. Каждая работа должна быть выполнена последовательно на всех машинах с первой по последнюю.}}<br />
<br />
Рассмотрим пример: <tex>F \mid p_{ij} = 1 \mid C_{max}</tex><br />
<br />
Допустим, у нас <tex>n</tex> работ и <tex>m</tex> машин. В начальный момент времени мы можем начать обрабатывать любую работу на первой машине. В следующий момент на первой машине можно обрабатывать следующую работу, а на второй перейдёт предыдущая работа с первой машины, и так далее. Таким образом, на выполнение всех работ у нас уйдёт <tex>n + m - 1</tex> единиц времени. Проиллюстрируем это диаграммой Гантта для случая <tex>n = 6, m = 5</tex>:<br />
'''0 1 2 3 4 5 6 7 8 9 10'''<br />
-------------------------------------------<br />
'''M_1''' | 1 2 3 4 5 6 - - - -<br />
'''M_2''' | - 1 2 3 4 5 6 - - -<br />
'''M_3''' | - - 1 2 3 4 5 6 - -<br />
'''M_4''' | - - - 1 2 3 4 5 6 -<br />
'''M_5''' | - - - - 1 2 3 4 5 6<br />
<br />
Заметим, что в данном случае <tex>p_{ij}</tex> может быть равно не только единице, но и любой константе.<br />
<br />
{{Утверждение<br />
|statement = Любая задача вида <tex>F \mid p_{ij} = 1 \mid ? </tex> сводится к соответствующей задаче вида <tex>1 \mid p_{ij} = 1 \mid ?</tex>. <br />
|proof = <br />
Поскольку работа всегда заканчивает выполняться на последней машине, нас интересуют только времена завершения работ на последней машине. Также очевидно, что последняя машина может начать работать только в момент времени <tex> m - 1 </tex>. Оказывается, что любое решение задачи <tex> 1 \mid p_{ij} = 1 \mid ? </tex> с дедлайнами, уменьшенными на <tex> m - 1 </tex> можно преобразовать в оптимальное расписание для задачи <tex>F \mid p_{ij} = 1 \mid ? </tex>. Докажем это.<br />
<br />
Возьмем оптимальное расписание для соответствующей задачи с одним станком, выполним работы в этом порядке на первой машине, затем на второй машине, начиная с момента времени <tex> 1 </tex>, и так далее, до выполнения на последней машине, начиная с <tex> m - 1 </tex>. Это расписание корректно и соблюдает все дедлайны. Поскольку целевая функция совпадает с соответствующей функцией для задачи на одном станке, оно оптимально и для данной задачи.<br />
}}<br />
<br />
Примером применения этого утверждения может служить задача [http://neerc.ifmo.ru/wiki/index.php?title=Fpij1sumwu]<br />
<br />
Задачи с произвольными временами выполнения работ почти все являются NP-трудными.<br />
<br />
== Задача Джонсона о двух станках <tex>F_2 \mid \mid C_{max}</tex> ==<br />
<br />
Это единственная из flow shop задач с произвольными временами выполнения работ, которая решается за полиномиальное время.<br />
<br />
Приведём здесь решение задачи без доказательства, его можно посмотреть в [1].<br />
<br />
Оптимальное расписание для первой и второй машины будет совпадать. Таким образом, нам требуется найти порядок, в котором будут выполняться работы на каждой машине.<br />
<br />
Алгоритм такой: возьмём два пустых списка. Будем рассматривать работы в порядке возрастания <tex>min(p_1, p_2)</tex>, то есть, минимума из времён выполнения данной работы на первой и второй машине. Если у работы <tex>p_1 \le p_2</tex>, то добавим её в конец первого списка. В противном случае, добавим её в начало второго списка. Итоговое расписание — это конкатенация первого и второго списков.<br />
<br />
Псевдокод:<br />
J - множество работ<br />
Head <tex> \leftarrow \emptyset </tex><br />
Tail <tex> \leftarrow \emptyset </tex><br />
'''while''' J <tex> \ne \emptyset </tex> <br />
'''do'''<br />
I <tex> \leftarrow </tex> работа с минимальным значением <tex>min(p_1, p_2)</tex><br />
'''if''' <tex>p_1 <= p_2</tex> Head <tex> \leftarrow </tex> Head <tex>\circ</tex> I<br />
'''else''' Tail <tex> \leftarrow </tex> I <tex>\circ</tex> Tail<br />
J <tex> \leftarrow </tex> J <tex> \backslash </tex> I<br />
Result <tex> \leftarrow </tex> Head <tex>\circ</tex> Tail<br />
<br />
== Задача Джонсона о двух станках с прерываниями <tex>F_2 \mid pmtn \mid C_{max}</tex> ==<br />
<br />
Оптимальное решение этой задачи совпадает с решением задачи <tex>F_2 \mid \mid C_{max}</tex>, приведённой выше. Докажем это.<br />
<br />
Пусть у нас есть оптимальное расписание для задачи <tex>F_2 \mid pmtn \mid C_{max}</tex>. Покажем, что его за конечное число шагов можно преобразовать к расписанию без прерываний, не изменив при это значение <tex>C_{max}</tex> .<br />
<br />
Рассмотрим первую машину. Допустим, что некоторая работа <tex> J </tex> выполняется в <tex> 2 </tex> или более разных промежутка времени. Тогда передвинем более ранний промежуток вправо по оси времени так, чтоб он заканчивался в тот момент, когда начинается второй промежуток, при этом работы, которые были между этими двумя промежутками, сдвинем влево на длину первого промежутка. Расписание при этом осталось корректным, так как работы на машинах по-прежнему не пересекаются, и каждая работа на второй машине делается после того, как она сделана на первой: работа <tex> J </tex> может начать выполняться на второй машине только после того, как она целиком выполнится на первой, то есть уже после конца второго промежутка; а время окончания выполнения остальных работ на первой машине неувеличилось.<br />
Важно, что подобная операция не увеличивает <tex> C_{max} </tex>.<br />
<br />
Будем повторять эту операцию до тех пор, пока на первой машине все работы не станут выполняться без прерываний. Так как количество прерываний конечно, а такая операция уменьшает их количество на один, этот процесс конечен.<br />
<br />
Теперь избавимся от прерываний на второй машине. Точно так же рассмотрим работу, разбитую на два или более промежутка. Передвинем более поздний промежуток к концу более раннего, а работы между ними сдвинем вправо. Доказательство корректности измененного расписания аналогично доказательству для первой машины. Будем повторять данную операцию, пока на второй машине присутствуют прерывания.<br />
<br />
Таким образом, мы получили корректное расписание без прерываний, не изменив при этом значение <tex>C_{max}</tex>, что и требовалось доказать.<br />
<br />
== См. также ==<br />
* [[Классификация задач]]<br />
* [[Fpij1sumwu|<tex>F \mid p_{ij} = 1 \mid \sum w_i u_i</tex>]]<br />
<br />
== Литература ==<br />
*[1][http://books.google.ru/books?id=FrUytMqlCv8C&printsec=frontcover&dq=scheduling+algorithms&hl=ru&sa=X&ei=0MPMT4HqKYSk4gSBm6gp&sqi=2&ved=0CDEQ6AEwAA#v=onepage&q=scheduling%20algorithms&f=false Scheduling Algorithms, Peter Brucker]</div>Sergej Arkhipovhttp://neerc.ifmo.ru/wiki/index.php?title=1ripi1sumwc&diff=472771ripi1sumwc2015-06-02T19:11:23Z<p>Sergej Arkhipov: </p>
<hr />
<div><tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum w_i C_i</tex><br />
<br />
{{Задача<br />
|definition=<br />
Дано <tex>n</tex> работ и один станок. Для каждой работы известно её время появления <tex>r_{i}</tex> и вес <tex>w_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>. Требуется выполнить все работы, чтобы значение <tex>\sum w_{i} C_{i}</tex> было минимальным, где <tex>C_{i}</tex> {{---}} время окончания работы.<br />
}}<br />
<br />
Перед решением основной задачи рассмотрим более простые.<br />
<br />
<br />
==Задача 1==<br />
<tex dpi = "200"> 1 \mid p_i = 1\mid \sum C_i</tex><br />
<br />
'''Описание алгоритма'''<br />
<br />
Входные данные для этой задачи: число работ <tex>n</tex> <br />
<br />
Этот случай простейший. Для верного выполнения просто выставим работы по порядку, тогда ответом будет <tex>n</tex>, так как мы <tex>n</tex> раз сложим время выполнения одной работы, которое в нашем случае единица.<br />
<br />
==Задача 2==<br />
<tex dpi = "200"> 1 \mid p_i = 1\mid \sum w_i C_i</tex><br />
<br />
'''Описание алгоритма'''<br />
<br />
Входные данные для этой задачи: число работ <tex>n</tex> и вес каждой работы <tex>w_i</tex> <br />
<br />
Для верного выполнения просто выставим работы по порядку, тогда ответом будет <tex> \sum_{i = 1}^n(w_i)</tex>, так как мы <tex>n</tex> раз сложим время выполнения одной работы (которое в нашем случае единица) домноженное на вес этой работы.<br />
<br />
==Задача 3==<br />
<tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum f_i</tex><br />
{{Задача<br />
|definition=<br />
Дано <tex>n</tex> работ и один станок. Для каждой работы известно её время появления <tex>r_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>. Требуется выполнить все работы, чтобы значение <tex>\sum f_{i}</tex> было минимальным, где <tex>f_{i}</tex> {{---}} монотонная функция времени окончания работы <tex>C_{i}</tex> для работ <tex>i = 1, 2, ..., n</tex>.<br />
}}<br />
<br />
'''Описание алгоритма'''<br />
<br />
Нам нужно распределить <tex>n</tex> работ в разное время. Если мы назначим время <tex>t</tex> для работы <tex>i</tex> то цена будет <tex>f_i(t + 1)</tex>. Так как нужно рассмотреть <tex>n</tex> временных промежутков, задача может быть решена за <tex>O(n^3)</tex>. Функция <tex>f_i</tex> монотонно неубывающая, тогда работы в расписании надо располагать как можно раньше для получения верного решения. <tex>n</tex> временных интервалов <tex>t_i</tex> для <tex>n</tex> работ могут быть получены с помощью следующего алгоритма, где предполагается что работы нумеруются так:<br />
<br />
<tex> r_1 \leqslant r_2 \leqslant \ldots \leqslant r_n</tex> <br />
<br />
'''Псевдокод'''<br />
<br />
<tex>t_1 \leftarrow r_1 </tex><br />
'''for''' <tex> i \leftarrow 2</tex> '''to''' <tex>n</tex> '''do'''<br />
<tex> t_i \leftarrow </tex> '''max'''<tex>(r_i, \ t_{i-1} - 1)</tex><br />
<br />
==Задача 4==<br />
<tex dpi = "200"> 1 \mid r_j,p_j = p \mid \sum f_j</tex><br />
<br />
Вес всех работ <tex>w_i \geqslant 0</tex><br />
Для всех функций <tex>f_1, f_2, \ldots, f_n</tex> выполняются следующие свойства:<br />
<br />
<tex>f_j</tex> неубывающая функция для <tex>j = 1, 2, \ldots, n</tex><br />
<br />
<tex>f_i - f_j</tex> неубывающая функция для <tex>i, j = 1, 2, \ldots, n</tex> при <tex>i < j </tex><br />
<br />
<tex>\sum w_i C_i</tex> являются функцией <tex>f_j(C_j)</tex>, так что по факту решаем задачу <tex>1 \mid r_j,p_j = p \mid \sum w_i C_i </tex><br />
<br />
'''Описание алгоритма'''<br />
<br />
Пусть перед началом алгоритма работы пронумерованы в соответствии с свойствами для функций <tex>f_1, f_2, \ldots, f_n</tex><br />
<br />
Пояснение для псевдокода:<br />
<br />
<tex>T</tex> это множество {<tex>r_j + lp \mid j = 1, 2, \ldots, n; l = 0, 1, \ldots, n-1 </tex>}<br />
<br />
<tex>F_k'(s,e)</tex> это <tex>min(F_{k-1}(s,t_k)+F_{k-1}(t_k + p, e)+f_k(t_k + p) \mid t_k \in T, max(s, r_k) \leqslant t_k \leqslant e-p)</tex><br />
<br />
'''Псевдокод'''<br />
<br />
'''for all''' <tex>s, e \in T \ with \ s \leqslant e</tex> '''do'''<br />
<tex>F_0(s,e) \leftarrow 0</tex><br />
'''for''' <tex>k \leftarrow 1</tex> '''to''' <tex>n</tex> '''do'''<br />
'''for all''' <tex>s, e \in T \ with \ s \leqslant e</tex> '''do'''<br />
<tex><br />
F_k(s,e) \leftarrow<br />
\begin{cases}<br />
F_{k-1}(s,e) \ if\ r_k \notin [s - p,e);\\<br />
F_k'(s,e) \ overwise; <br />
\end{cases}<br />
</tex><br />
'''Вычислить''' <tex>F_n($$ \min_{i=1}^n (r_i) $$, max_{t \in T}(t+p) )</tex><br />
==Описание алгоритма==<br />
Пусть <tex>time</tex> {{---}} текущий момент времени.<br/><br />
Для каждого очередного значения <tex>time</tex>, которое изменяется от <tex>0</tex> до времени окончания последней работы, будем:<br />
<ol><br />
<li> Выбирать работу <tex>j</tex> из множества невыполненных работ, у которой <tex>r_{i} \le time</tex>, а значение <tex>w_{i}</tex> максимально.</li><br />
<li> Если мы смогли найти работу <tex>j</tex>, то выполняем её в момент времени <tex>time</tex> и удаляем из множества невыполненных работ.</li><br />
<li> Увеличиваем <tex>time</tex> на один.</li><br />
</ol><br />
<br />
==Доказательство корректности алгоритма==<br />
{{Теорема<br />
|statement=<br />
Расписание, построенное данным алгоритмом, является корректным и оптимальным.<br />
|proof=<br />
Доказательство будем вести от противного.<br/><br />
Рассмотрим расписание <tex>S_{1}</tex>, полученное после выполнения нашего алгоритма, и оптимальное расписание <tex>S_{2}</tex>.<br/><br />
Возьмём первый момент времени <tex>t_{1}</tex>, когда расписания различаются. Пусть в этот момент времени в <tex>S_{1}</tex>, будет выполняться работа с весом <tex>w_{1}</tex>, а в <tex>S_{2}</tex> {{---}} работа с весом <tex>w_{2}</tex>.<br/><br />
Это первый момент, в котором расписания отличаются, значит в <tex>S_{2}</tex> работа с весом <tex>w_{1}</tex> выполнится в момент времени <tex>t_{2} > t_{1}</tex>.<br/><br />
Поменяем местами работы с весами <tex>w_{1}</tex> и <tex>w_{2}</tex> в <tex>S_{2}</tex> и полуим расписание <tex>S_{3}</tex>. Это возможно, потому что время появления этих работ не меньше <tex>t_{1}</tex>.<br/><br />
При такой перестановке ответы на задачу для <tex>S_{2}</tex> и <tex>S_{3}</tex> будут отличаться на <br />
<ul><tex>t_{1}w_{2} + t_{2}w_{1} - t_{1}w_{1} + t_{2}w_{2} = t_{1}(w_{2} - w_{1}) + t_{2}(w_{1} - w_{2}) = (t_{1} - t_{2})(w_{2} - w_{1})</tex></ul><br />
Первая скобка отрицательная: <tex>t_{1} < t_{2}</tex>. Вторая скобка тоже отрицательная из того, что в <tex>S_{1}</tex> работа с весом <tex>w_1</tex> выполняется раньше, значит её вес должен быть больше <tex>w_2</tex>.<br/><br />
Итого имеем, что ответ для <tex>S_{2}</tex> больше, чем ответ для <tex>S_{3}</tex>. Следовательно расписание <tex>S_2</tex> неоптимальное. Получили противоречие. Значит не существует такого момента времени, когда расписание <tex>S_{1}</tex> отличается от оптимального. Следовательно мы доказали, что оно оптимальное.<br />
}}<br />
<br />
==Псевдокод==<br />
<tex> S \leftarrow \{1 \dots n\}</tex><br />
<tex> \mathtt{time} \leftarrow 0</tex><br />
<tex> \mathtt{answer} \leftarrow 0</tex><br />
'''while''' <tex> S \neq \varnothing </tex><br />
<tex> j \leftarrow null </tex><br />
'''if''' <tex> i \in S</tex> '''and''' <tex> r_{i} \leq \mathtt{time}</tex> '''and''' <tex>\max w_{i} </tex><br />
<tex> j \leftarrow i </tex><br />
'''if''' <tex>j \neq null </tex><br />
<tex> S \leftarrow S \setminus j</tex><br />
<tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot w_{j}</tex><br />
<tex> \mathtt{time++}</tex><br />
<br />
==Сложность алгоритма==<br />
Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \max r_{i}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, очередь с приоритетами. Значит общее время работы алгоритма <tex>O((n + \max r_{i})\log n)</tex><br />
<br />
<br />
== Источники информации ==<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 19 - 20<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 38 - 39<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 84 - 85<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 101 - 102<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Теория расписаний]]</div>Sergej Arkhipovhttp://neerc.ifmo.ru/wiki/index.php?title=1ripi1sumwc&diff=472761ripi1sumwc2015-06-02T19:00:27Z<p>Sergej Arkhipov: </p>
<hr />
<div><tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum w_i C_i</tex><br />
<br />
{{Задача<br />
|definition=<br />
Дано <tex>n</tex> работ и один станок. Для каждой работы известно её время появления <tex>r_{i}</tex> и вес <tex>w_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>. Требуется выполнить все работы, чтобы значение <tex>\sum w_{i} C_{i}</tex> было минимальным, где <tex>C_{i}</tex> {{---}} время окончания работы.<br />
}}<br />
<br />
Перед решением основной задачи рассмотрим более простые.<br />
<br />
<br />
==Задача 1==<br />
<tex dpi = "200"> 1 \mid p_i = 1\mid \sum C_i</tex><br />
<br />
'''Описание алгоритма'''<br />
<br />
Входные данные для этой задачи: число работ <tex>n</tex> <br />
<br />
Этот случай простейший. Для верного выполнения просто выставим работы по порядку, тогда ответом будет <tex>n</tex>, так как мы <tex>n</tex> раз сложим время выполнения одной работы, которое в нашем случае единица.<br />
<br />
<br />
==Задача 2==<br />
<tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum f_i</tex><br />
{{Задача<br />
|definition=<br />
Дано <tex>n</tex> работ и один станок. Для каждой работы известно её время появления <tex>r_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>. Требуется выполнить все работы, чтобы значение <tex>\sum f_{i}</tex> было минимальным, где <tex>f_{i}</tex> {{---}} монотонная функция времени окончания работы <tex>C_{i}</tex> для работ <tex>i = 1, 2, ..., n</tex>.<br />
}}<br />
<br />
'''Описание алгоритма'''<br />
<br />
Нам нужно распределить <tex>n</tex> работ в разное время. Если мы назначим время <tex>t</tex> для работы <tex>i</tex> то цена будет <tex>f_i(t + 1)</tex>. Так как нужно рассмотреть <tex>n</tex> временных промежутков, задача может быть решена за <tex>O(n^3)</tex>. Функция <tex>f_i</tex> монотонно неубывающая, тогда работы в расписании надо располагать как можно раньше для получения верного решения. <tex>n</tex> временных интервалов <tex>t_i</tex> для <tex>n</tex> работ могут быть получены с помощью следующего алгоритма, где предполагается что работы нумеруются так:<br />
<br />
<tex> r_1 \leqslant r_2 \leqslant \ldots \leqslant r_n</tex> <br />
<br />
'''Псевдокод'''<br />
<br />
<tex>t_1 \leftarrow r_1 </tex><br />
'''for''' <tex> i \leftarrow 2</tex> '''to''' <tex>n</tex> '''do'''<br />
<tex> t_i \leftarrow </tex> '''max'''<tex>(r_i, \ t_{i-1} - 1)</tex><br />
<br />
==Задача 3==<br />
<tex dpi = "200"> 1 \mid r_j,p_j = p \mid \sum f_j</tex><br />
<br />
Вес всех работ <tex>w_i \geqslant 0</tex><br />
Для всех функций <tex>f_1, f_2, \ldots, f_n</tex> выполняются следующие свойства:<br />
<br />
<tex>f_j</tex> неубывающая функция для <tex>j = 1, 2, \ldots, n</tex><br />
<br />
<tex>f_i - f_j</tex> неубывающая функция для <tex>i, j = 1, 2, \ldots, n</tex> при <tex>i < j </tex><br />
<br />
<tex>\sum w_i C_i</tex> являются функцией <tex>f_j(C_j)</tex>, так что по факту решаем задачу <tex>1 \mid r_j,p_j = p \mid \sum w_i C_i </tex><br />
<br />
'''Описание алгоритма'''<br />
<br />
Пусть перед началом алгоритма работы пронумерованы в соответствии с свойствами для функций <tex>f_1, f_2, \ldots, f_n</tex><br />
<br />
Пояснение для псевдокода:<br />
<br />
<tex>T</tex> это множество {<tex>r_j + lp \mid j = 1, 2, \ldots, n; l = 0, 1, \ldots, n-1 </tex>}<br />
<br />
<tex>F_k'(s,e)</tex> это <tex>min(F_{k-1}(s,t_k)+F_{k-1}(t_k + p, e)+f_k(t_k + p) \mid t_k \in T, max(s, r_k) \leqslant t_k \leqslant e-p)</tex><br />
<br />
'''Псевдокод'''<br />
<br />
'''for all''' <tex>s, e \in T \ with \ s \leqslant e</tex> '''do'''<br />
<tex>F_0(s,e) \leftarrow 0</tex><br />
'''for''' <tex>k \leftarrow 1</tex> '''to''' <tex>n</tex> '''do'''<br />
'''for all''' <tex>s, e \in T \ with \ s \leqslant e</tex> '''do'''<br />
<tex><br />
F_k(s,e) \leftarrow<br />
\begin{cases}<br />
F_{k-1}(s,e) \ if\ r_k \notin [s - p,e);\\<br />
F_k'(s,e) \ overwise; <br />
\end{cases}<br />
</tex><br />
'''Вычислить''' <tex>F_n($$ \min_{i=1}^n (r_i) $$, max_{t \in T}(t+p) )</tex><br />
==Описание алгоритма==<br />
Пусть <tex>time</tex> {{---}} текущий момент времени.<br/><br />
Для каждого очередного значения <tex>time</tex>, которое изменяется от <tex>0</tex> до времени окончания последней работы, будем:<br />
<ol><br />
<li> Выбирать работу <tex>j</tex> из множества невыполненных работ, у которой <tex>r_{i} \le time</tex>, а значение <tex>w_{i}</tex> максимально.</li><br />
<li> Если мы смогли найти работу <tex>j</tex>, то выполняем её в момент времени <tex>time</tex> и удаляем из множества невыполненных работ.</li><br />
<li> Увеличиваем <tex>time</tex> на один.</li><br />
</ol><br />
<br />
==Доказательство корректности алгоритма==<br />
{{Теорема<br />
|statement=<br />
Расписание, построенное данным алгоритмом, является корректным и оптимальным.<br />
|proof=<br />
Доказательство будем вести от противного.<br/><br />
Рассмотрим расписание <tex>S_{1}</tex>, полученное после выполнения нашего алгоритма, и оптимальное расписание <tex>S_{2}</tex>.<br/><br />
Возьмём первый момент времени <tex>t_{1}</tex>, когда расписания различаются. Пусть в этот момент времени в <tex>S_{1}</tex>, будет выполняться работа с весом <tex>w_{1}</tex>, а в <tex>S_{2}</tex> {{---}} работа с весом <tex>w_{2}</tex>.<br/><br />
Это первый момент, в котором расписания отличаются, значит в <tex>S_{2}</tex> работа с весом <tex>w_{1}</tex> выполнится в момент времени <tex>t_{2} > t_{1}</tex>.<br/><br />
Поменяем местами работы с весами <tex>w_{1}</tex> и <tex>w_{2}</tex> в <tex>S_{2}</tex> и полуим расписание <tex>S_{3}</tex>. Это возможно, потому что время появления этих работ не меньше <tex>t_{1}</tex>.<br/><br />
При такой перестановке ответы на задачу для <tex>S_{2}</tex> и <tex>S_{3}</tex> будут отличаться на <br />
<ul><tex>t_{1}w_{2} + t_{2}w_{1} - t_{1}w_{1} + t_{2}w_{2} = t_{1}(w_{2} - w_{1}) + t_{2}(w_{1} - w_{2}) = (t_{1} - t_{2})(w_{2} - w_{1})</tex></ul><br />
Первая скобка отрицательная: <tex>t_{1} < t_{2}</tex>. Вторая скобка тоже отрицательная из того, что в <tex>S_{1}</tex> работа с весом <tex>w_1</tex> выполняется раньше, значит её вес должен быть больше <tex>w_2</tex>.<br/><br />
Итого имеем, что ответ для <tex>S_{2}</tex> больше, чем ответ для <tex>S_{3}</tex>. Следовательно расписание <tex>S_2</tex> неоптимальное. Получили противоречие. Значит не существует такого момента времени, когда расписание <tex>S_{1}</tex> отличается от оптимального. Следовательно мы доказали, что оно оптимальное.<br />
}}<br />
<br />
==Псевдокод==<br />
<tex> S \leftarrow \{1 \dots n\}</tex><br />
<tex> \mathtt{time} \leftarrow 0</tex><br />
<tex> \mathtt{answer} \leftarrow 0</tex><br />
'''while''' <tex> S \neq \varnothing </tex><br />
<tex> j \leftarrow null </tex><br />
'''if''' <tex> i \in S</tex> '''and''' <tex> r_{i} \leq \mathtt{time}</tex> '''and''' <tex>\max w_{i} </tex><br />
<tex> j \leftarrow i </tex><br />
'''if''' <tex>j \neq null </tex><br />
<tex> S \leftarrow S \setminus j</tex><br />
<tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot w_{j}</tex><br />
<tex> \mathtt{time++}</tex><br />
<br />
==Сложность алгоритма==<br />
Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \max r_{i}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, очередь с приоритетами. Значит общее время работы алгоритма <tex>O((n + \max r_{i})\log n)</tex><br />
<br />
<br />
== Источники информации ==<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 19 - 20<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 38 - 39<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 84 - 85<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 101 - 102<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Теория расписаний]]</div>Sergej Arkhipovhttp://neerc.ifmo.ru/wiki/index.php?title=Flow_shop&diff=47221Flow shop2015-06-02T09:36:55Z<p>Sergej Arkhipov: </p>
<hr />
<div>== Описание ==<br />
{{Определение<br />
|definition =<br />
'''Flow shop''' ('''<tex>F_{m}</tex>''' в нотации Грэхема): В системе находится <tex> m </tex> машин, работающих параллельно. Машины упорядочены. Каждая работа должна быть выполнена последовательно на всех машинах с первой по последнюю.}}<br />
<br />
Рассмотрим пример: <tex>F \mid p_{ij} = 1 \mid C_{max}</tex><br />
<br />
Допустим, у нас <tex>n</tex> работ и <tex>m</tex> машин. В начальный момент времени мы можем начать обрабатывать любую работу на первой машине. В следующий момент на первой машине можно обрабатывать следующую работу, а на второй перейдёт предыдущая работа с первой машины, и так далее. Таким образом, на выполнение всех работ у нас уйдёт <tex>n + m - 1</tex> единиц времени. Проиллюстрируем это диаграммой Гантта для случая <tex>n = 6, m = 5</tex>:<br />
'''0 1 2 3 4 5 6 7 8 9 10'''<br />
-------------------------------------------<br />
'''M_1''' | 1 2 3 4 5 6 - - - -<br />
'''M_2''' | - 1 2 3 4 5 6 - - -<br />
'''M_3''' | - - 1 2 3 4 5 6 - -<br />
'''M_4''' | - - - 1 2 3 4 5 6 -<br />
'''M_5''' | - - - - 1 2 3 4 5 6<br />
<br />
Заметим, что в данном случае <tex>p_{ij}</tex> может быть равно не только единице, но и любой константе.<br />
<br />
{{Утверждение<br />
|statement = Любая задача вида <tex>F \mid p_{ij} = 1 \mid ? </tex> сводится к соответствующей задаче вида <tex>1 \mid p_{ij} = 1 \mid ?</tex>. <br />
|proof = <br />
Поскольку работа всегда заканчивает выполняться на последней машине, нас интересуют только времена завершения работ на последней машине. Также очевидно, что последняя машина может начать работать только в момент времени <tex> m - 1 </tex>. Оказывается, что любое решение задачи <tex> 1 \mid p_{ij} = 1 \mid ? </tex> с дедлайнами, уменьшенными на <tex> m - 1 </tex> можно преобразовать в оптимальное расписание для задачи <tex>F \mid p_{ij} = 1 \mid ? </tex>. Докажем это.<br />
<br />
Возьмем оптимальное расписание для соответствующей задачи с одним станком, выполним работы в этом порядке на первой машине, затем на второй машине, начиная с момента времени <tex> 1 </tex>, и так далее, до выполнения на последней машине, начиная с <tex> m - 1 </tex>. Это расписание корректно и соблюдает все дедлайны. Поскольку целевая функция совпадает с соответствующей функцией для задачи на одном станке, оно оптимально и для данной задачи.<br />
}}<br />
<br />
Задачи с произвольными временами выполнения работ почти все являются NP-трудными.<br />
<br />
== Задача Джонсона о двух станках <tex>F_2 \mid \mid C_{max}</tex> ==<br />
<br />
Это единственная из flow shop задач с произвольными временами выполнения работ, которая решается за полиномиальное время.<br />
<br />
Приведём здесь решение задачи без доказательства, его можно посмотреть в [1].<br />
<br />
Оптимальное расписание для первой и второй машины будет совпадать. Таким образом, нам требуется найти порядок, в котором будут выполняться работы на каждой машине.<br />
<br />
Алгоритм такой: возьмём два пустых списка. Будем рассматривать работы в порядке возрастания <tex>min(p_1, p_2)</tex>, то есть, минимума из времён выполнения данной работы на первой и второй машине. Если у работы <tex>p_1 \le p_2</tex>, то добавим её в конец первого списка. В противном случае, добавим её в начало второго списка. Итоговое расписание — это конкатенация первого и второго списков.<br />
<br />
Псевдокод:<br />
J - множество работ<br />
Head <tex> \leftarrow \emptyset </tex><br />
Tail <tex> \leftarrow \emptyset </tex><br />
'''while''' J <tex> \ne \emptyset </tex> <br />
'''do'''<br />
I <tex> \leftarrow </tex> работа с минимальным значением <tex>min(p_1, p_2)</tex><br />
'''if''' <tex>p_1 <= p_2</tex> Head <tex> \leftarrow </tex> Head <tex>\circ</tex> I<br />
'''else''' Tail <tex> \leftarrow </tex> I <tex>\circ</tex> Tail<br />
J <tex> \leftarrow </tex> J <tex> \backslash </tex> I<br />
Result <tex> \leftarrow </tex> Head <tex>\circ</tex> Tail<br />
<br />
== Задача Джонсона о двух станках с прерываниями <tex>F_2 \mid pmtn \mid C_{max}</tex> ==<br />
<br />
Оптимальное решение этой задачи совпадает с решением задачи <tex>F_2 \mid \mid C_{max}</tex>, приведённой выше. Докажем это.<br />
<br />
Пусть у нас есть оптимальное расписание для задачи <tex>F_2 \mid pmtn \mid C_{max}</tex>. Покажем, что его за конечное число шагов можно преобразовать к расписанию без прерываний, не изменив при это значение <tex>C_{max}</tex> .<br />
<br />
Рассмотрим первую машину. Допустим, что некоторая работа <tex> J </tex> выполняется в <tex> 2 </tex> или более разных промежутка времени. Тогда передвинем более ранний промежуток вправо по оси времени так, чтоб он заканчивался в тот момент, когда начинается второй промежуток, при этом работы, которые были между этими двумя промежутками, сдвинем влево на длину первого промежутка. Расписание при этом осталось корректным, так как работы на машинах по-прежнему не пересекаются, и каждая работа на второй машине делается после того, как она сделана на первой: работа <tex> J </tex> может начать выполняться на второй машине только после того, как она целиком выполнится на первой, то есть уже после конца второго промежутка; а время окончания выполнения остальных работ на первой машине неувеличилось.<br />
Важно, что подобная операция не увеличивает <tex> C_{max} </tex>.<br />
<br />
Будем повторять эту операцию до тех пор, пока на первой машине все работы не станут выполняться без прерываний. Так как количество прерываний конечно, а такая операция уменьшает их количество на один, этот процесс конечен.<br />
<br />
Теперь избавимся от прерываний на второй машине. Точно так же рассмотрим работу, разбитую на два или более промежутка. Передвинем более поздний промежуток к концу более раннего, а работы между ними сдвинем вправо. Доказательство корректности измененного расписания аналогично доказательству для первой машины. Будем повторять данную операцию, пока на второй машине присутствуют прерывания.<br />
<br />
Таким образом, мы получили корректное расписание без прерываний, не изменив при этом значение <tex>C_{max}</tex>, что и требовалось доказать.<br />
<br />
== Пример: задача <tex>F \mid p_{ij} = 1 \mid \sum w_iu_i</tex> ==<br />
{{Задача<br />
|definition=<br />
Дано <tex>m</tex> станков, на которых нужно обработать <tex>n</tex> деталей. Каждую деталь нужно обработать по очереди на всех станках. Любая работа на любом станке выполняется единицу времени. Для каждой работы есть дедлайн <tex>d_i</tex> {{---}} время, до которого она должна быть закончена, и штраф <tex>w_i</tex>, который нужно будет выплатить в случае, если работа была закончена после <tex>d_i</tex>. Необходимо минимизировать суммарный штраф, который придется выплатить.<br />
}}<br />
Задача <tex>F \mid p_{ij} = 1 \mid \sum w_iu_i</tex> за <tex>O(n)</tex> сводится к задаче <tex>1 \mid p_i = 1 \mid \sum w_iu_i</tex>. Задача <tex>1 \mid p_i = 1 \mid \sum u_iw_i</tex> решается за <tex>O(n \log n)</tex>. После решения этой задачи, нужно вывести ответ, имеющий размер <tex>O(nm)</tex>. Итоговая сложность алгоритма {{---}} <tex>O(n \log n + nm)</tex><br />
<br />
== См. также ==<br />
* [[Классификация задач]]<br />
* [[Fpij1sumwu|<tex>F \mid p_{ij} = 1 \mid \sum w_i u_i</tex>]]<br />
<br />
== Литература ==<br />
*[1][http://books.google.ru/books?id=FrUytMqlCv8C&printsec=frontcover&dq=scheduling+algorithms&hl=ru&sa=X&ei=0MPMT4HqKYSk4gSBm6gp&sqi=2&ved=0CDEQ6AEwAA#v=onepage&q=scheduling%20algorithms&f=false Scheduling Algorithms, Peter Brucker]</div>Sergej Arkhipovhttp://neerc.ifmo.ru/wiki/index.php?title=1ripi1sumwc&diff=472201ripi1sumwc2015-06-02T09:26:40Z<p>Sergej Arkhipov: </p>
<hr />
<div><tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum w_i C_i</tex><br />
<br />
{{Задача<br />
|definition=<br />
Дано <tex>n</tex> работ и один станок. Для каждой работы известно её время появления <tex>r_{i}</tex> и вес <tex>w_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>. Требуется выполнить все работы, чтобы значение <tex>\sum w_{i} C_{i}</tex> было минимальным, где <tex>C_{i}</tex> {{---}} время окончания работы.<br />
}}<br />
Перед решением этой задачи рассмотрим более простую.<br />
<br />
<tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum f_i</tex><br />
{{Задача<br />
|definition=<br />
Дано <tex>n</tex> работ и один станок. Для каждой работы известно её время появления <tex>r_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>. Требуется выполнить все работы, чтобы значение <tex>\sum f_{i}</tex> было минимальным, где <tex>f_{i}</tex> {{---}} монотонная функция времени окончания работы <tex>C_{i}</tex> для работ <tex>i = 1, 2, ..., n</tex>.<br />
}}<br />
<br />
==Описание алгоритма простой задачи==<br />
Нам нужно распределить <tex>n</tex> работ в разное время. Если мы назначим время <tex>t</tex> для работы <tex>i</tex> то цена будет <tex>f_i(t + 1)</tex>. Так как нужно рассмотреть <tex>n</tex> временных промежутков, задача может быть решена за <tex>O(n^3)</tex>. Функция <tex>f_i</tex> монотонно неубывающая, тогда работы в расписании надо располагать как можно раньше для получения верного решения. <tex>n</tex> временных интервалов <tex>t_i</tex> для <tex>n</tex> работ могут быть получены с помощью следующего алгоритма, где предполагается что работы нумеруются так:<br />
<br />
<tex> r_1 <= r_2 <=... <= r_n</tex> <br />
==Псевдокод простой задачи==<br />
<tex>t_1 \leftarrow r_1 </tex><br />
'''FOR''' <tex> i \leftarrow 2</tex> '''TO''' <tex>n</tex> '''DO'''<br />
<tex> t_i \leftarrow </tex> '''MAX'''<tex>(r_i, \ t_{i-1} - 1)</tex><br />
<br />
==Описание алгоритма основной задачи==<br />
Пусть <tex>time</tex> {{---}} текущий момент времени.<br/><br />
Для каждого очередного значения <tex>time</tex>, которое изменяется от <tex>0</tex> до времени окончания последней работы, будем:<br />
<ol><br />
<li> Выбирать работу <tex>j</tex> из множества невыполненных работ, у которой <tex>r_{i} \le time</tex>, а значение <tex>w_{i}</tex> максимально.</li><br />
<li> Если мы смогли найти работу <tex>j</tex>, то выполняем её в момент времени <tex>time</tex> и удаляем из множества невыполненных работ.</li><br />
<li> Увеличиваем <tex>time</tex> на один.</li><br />
</ol><br />
<br />
==Доказательство корректности алгоритма основной задачи==<br />
{{Теорема<br />
|statement=<br />
Расписание, построенное данным алгоритмом, является корректным и оптимальным.<br />
|proof=<br />
Доказательство будем вести от противного.<br/><br />
Рассмотрим расписание <tex>S_{1}</tex>, полученное после выполнения нашего алгоритма, и оптимальное расписание <tex>S_{2}</tex>.<br/><br />
Возьмём первый момент времени <tex>t_{1}</tex>, когда расписания различаются. Пусть в этот момент времени в <tex>S_{1}</tex>, будет выполняться работа с весом <tex>w_{1}</tex>, а в <tex>S_{2}</tex> {{---}} работа с весом <tex>w_{2}</tex>.<br/><br />
Это первый момент, в котором расписания отличаются, значит в <tex>S_{2}</tex> работа с весом <tex>w_{1}</tex> выполнится в момент времени <tex>t_{2} > t_{1}</tex>.<br/><br />
Поменяем местами работы с весами <tex>w_{1}</tex> и <tex>w_{2}</tex> в <tex>S_{2}</tex> и полуим расписание <tex>S_{3}</tex>. Это возможно, потому что время появления этих работ не меньше <tex>t_{1}</tex>.<br/><br />
При такой перестановке ответы на задачу для <tex>S_{2}</tex> и <tex>S_{3}</tex> будут отличаться на <br />
<ul><tex>t_{1}w_{2} + t_{2}w_{1} - t_{1}w_{1} + t_{2}w_{2} = t_{1}(w_{2} - w_{1}) + t_{2}(w_{1} - w_{2}) = (t_{1} - t_{2})(w_{2} - w_{1})</tex></ul><br />
Первая скобка отрицательная: <tex>t_{1} < t_{2}</tex>. Вторая скобка тоже отрицательная из того, что в <tex>S_{1}</tex> работа с весом <tex>w_1</tex> выполняется раньше, значит её вес должен быть больше <tex>w_2</tex>.<br/><br />
Итого имеем, что ответ для <tex>S_{2}</tex> больше, чем ответ для <tex>S_{3}</tex>. Следовательно расписание <tex>S_2</tex> неоптимальное. Получили противоречие. Значит не существует такого момента времени, когда расписание <tex>S_{1}</tex> отличается от оптимального. Следовательно мы доказали, что оно оптимальное.<br />
}}<br />
<br />
==Псевдокод основной задачи==<br />
<tex> S \leftarrow \{1 \dots n\}</tex><br />
<tex> time \leftarrow 0</tex><br />
<tex> answer \leftarrow 0</tex><br />
'''WHILE''' <tex> S \neq \varnothing </tex><br />
<tex> j \leftarrow null </tex><br />
'''IF''' <tex> i \in S</tex> '''AND''' <tex> r_{i} \leq time</tex> '''AND''' <tex>\max w_{i} </tex><br />
<tex> j \leftarrow i </tex><br />
'''IF''' <tex>j \neq null </tex><br />
<tex> S \leftarrow S \setminus j</tex><br />
<tex> Answer \leftarrow Answer + time \cdot w_{j}</tex><br />
<tex> time++</tex><br />
<br />
==Сложность алгоритма==<br />
Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \max r_{i}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, очередь с приоритетами. Значит общее время работы алгоритма <tex>O((n + \max r_{i})\log n)</tex><br />
<br />
<br />
== Источники информации ==<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 19 - 20<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 84 - 85<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Теория расписаний]]</div>Sergej Arkhipovhttp://neerc.ifmo.ru/wiki/index.php?title=1ripi1sumwc&diff=472191ripi1sumwc2015-06-02T09:14:07Z<p>Sergej Arkhipov: </p>
<hr />
<div><tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum w_i C_i</tex><br />
<br />
{{Задача<br />
|definition=<br />
Дано <tex>n</tex> работ и один станок. Для каждой работы известно её время появления <tex>r_{i}</tex> и вес <tex>w_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>. Требуется выполнить все работы, чтобы значение <tex>\sum w_{i} C_{i}</tex> было минимальным, где <tex>C_{i}</tex> {{---}} время окончания работы.<br />
}}<br />
Перед решением этой задачи рассмотрим более простую.<br />
<br />
<tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum f_i</tex><br />
{{Задача<br />
|definition=<br />
Дано <tex>n</tex> работ и один станок. Для каждой работы известно её время появления <tex>r_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>. Требуется выполнить все работы, чтобы значение <tex>\sum f_{i}</tex> было минимальным, где <tex>f_{i}</tex> {{---}} монотонная функция времени окончания работы <tex>C_{i}</tex>.<br />
}}<br />
<br />
==Описание алгоритма простой задачи==<br />
Нам нужно распределить <tex>n</tex> работ в разное время. Если мы назначим время <tex>t</tex> для работы <tex>i</tex> то цена будет <tex>f_i(t + 1)</tex>. Далее покажем что <tex>n</tex> временных промежутков будут рассмотрены. Таким образом, задача может быть решена за <tex>O(n^3)</tex>. Так как функция <tex>f_i</tex> монотонно неубывающая, то работы в расписании будем располагать как можно раньше. <tex>n</tex> временных интервалов <tex>t_i</tex> для <tex>n</tex> работ могут быть получены с помощью следующего алгоритма, где предполагается что рабочие места нумеруются так:<br />
<br />
<tex> r_1 <= r_2 <=... <= r_n</tex> <br />
==Псевдокод простой задачи==<br />
<tex>t_1 \leftarrow r_1 </tex><br />
'''FOR''' <tex> i \leftarrow 2</tex> '''TO''' <tex>n</tex> '''DO'''<br />
<tex> t_i \leftarrow </tex> '''MAX'''<tex>(r_i, \ t_{i-1} - 1)</tex><br />
<br />
==Описание алгоритма основной задачи==<br />
Пусть <tex>time</tex> {{---}} текущий момент времени.<br/><br />
Для каждого очередного значения <tex>time</tex>, которое изменяется от <tex>0</tex> до времени окончания последней работы, будем:<br />
<ol><br />
<li> Выбирать работу <tex>j</tex> из множества невыполненных работ, у которой <tex>r_{i} \le time</tex>, а значение <tex>w_{i}</tex> максимально.</li><br />
<li> Если мы смогли найти работу <tex>j</tex>, то выполняем её в момент времени <tex>time</tex> и удаляем из множества невыполненных работ.</li><br />
<li> Увеличиваем <tex>time</tex> на один.</li><br />
</ol><br />
<br />
==Доказательство корректности алгоритма основной задачи==<br />
{{Теорема<br />
|statement=<br />
Расписание, построенное данным алгоритмом, является корректным и оптимальным.<br />
|proof=<br />
Доказательство будем вести от противного.<br/><br />
Рассмотрим расписание <tex>S_{1}</tex>, полученное после выполнения нашего алгоритма, и оптимальное расписание <tex>S_{2}</tex>.<br/><br />
Возьмём первый момент времени <tex>t_{1}</tex>, когда расписания различаются. Пусть в этот момент времени в <tex>S_{1}</tex>, будет выполняться работа с весом <tex>w_{1}</tex>, а в <tex>S_{2}</tex> {{---}} работа с весом <tex>w_{2}</tex>.<br/><br />
Это первый момент, в котором расписания отличаются, значит в <tex>S_{2}</tex> работа с весом <tex>w_{1}</tex> выполнится в момент времени <tex>t_{2} > t_{1}</tex>.<br/><br />
Поменяем местами работы с весами <tex>w_{1}</tex> и <tex>w_{2}</tex> в <tex>S_{2}</tex> и полуим расписание <tex>S_{3}</tex>. Это возможно, потому что время появления этих работ не меньше <tex>t_{1}</tex>.<br/><br />
При такой перестановке ответы на задачу для <tex>S_{2}</tex> и <tex>S_{3}</tex> будут отличаться на <br />
<ul><tex>t_{1}w_{2} + t_{2}w_{1} - t_{1}w_{1} + t_{2}w_{2} = t_{1}(w_{2} - w_{1}) + t_{2}(w_{1} - w_{2}) = (t_{1} - t_{2})(w_{2} - w_{1})</tex></ul><br />
Первая скобка отрицательная: <tex>t_{1} < t_{2}</tex>. Вторая скобка тоже отрицательная из того, что в <tex>S_{1}</tex> работа с весом <tex>w_1</tex> выполняется раньше, значит её вес должен быть больше <tex>w_2</tex>.<br/><br />
Итого имеем, что ответ для <tex>S_{2}</tex> больше, чем ответ для <tex>S_{3}</tex>. Следовательно расписание <tex>S_2</tex> неоптимальное. Получили противоречие. Значит не существует такого момента времени, когда расписание <tex>S_{1}</tex> отличается от оптимального. Следовательно мы доказали, что оно оптимальное.<br />
}}<br />
<br />
==Псевдокод основной задачи==<br />
<tex> S \leftarrow \{1 \dots n\}</tex><br />
<tex> time \leftarrow 0</tex><br />
<tex> answer \leftarrow 0</tex><br />
'''WHILE''' <tex> S \neq \varnothing </tex><br />
<tex> j \leftarrow null </tex><br />
'''IF''' <tex> i \in S</tex> '''AND''' <tex> r_{i} \leq time</tex> '''AND''' <tex>\max w_{i} </tex><br />
<tex> j \leftarrow i </tex><br />
'''IF''' <tex>j \neq null </tex><br />
<tex> S \leftarrow S \setminus j</tex><br />
<tex> Answer \leftarrow Answer + time \cdot w_{j}</tex><br />
<tex> time++</tex><br />
<br />
==Сложность алгоритма==<br />
Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \max r_{i}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, очередь с приоритетами. Значит общее время работы алгоритма <tex>O((n + \max r_{i})\log n)</tex><br />
<br />
<br />
== Источники информации ==<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 19 - 20<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 84 - 85<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Теория расписаний]]</div>Sergej Arkhipovhttp://neerc.ifmo.ru/wiki/index.php?title=1ripi1sumwc&diff=470161ripi1sumwc2015-05-29T12:28:53Z<p>Sergej Arkhipov: </p>
<hr />
<div><tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum w_i C_i</tex><br />
<br />
{{Задача<br />
|definition=<br />
Дано <tex>n</tex> работ и один станок. Для каждой работы известно её время появления <tex>r_{i}</tex> и вес <tex>w_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>.Требуется выполнить все работы, чтобы значение <tex>\sum w_{i} C_{i}</tex> было минимальным, где <tex>C_{i}</tex> {{---}} время окончания работы.<br />
}}<br />
Это задание может быть сведено к более простому - Задаче о назначениях. По этой причине можно решить задачу за <tex>O(n^3)</tex>. Теперь рассмотрим как решить её эффективнее.<br />
<br />
==Описание алгоритма==<br />
Пусть <tex>time</tex> {{---}} текущий момент времени.<br/><br />
Для каждого очередного значения <tex>time</tex>, которое изменяется от <tex>0</tex> до времени окончания последней работы, будем:<br />
<ol><br />
<li> Выбирать работу <tex>j</tex> из множества невыполненных работ, у которой <tex>r_{i} \le time</tex>, а значение <tex>w_{i}</tex> максимально.</li><br />
<li> Если мы смогли найти работу <tex>j</tex>, то выполняем её в момент времени <tex>time</tex> и удаляем из множества невыполненных работ.</li><br />
<li> Увеличиваем <tex>time</tex> на один.</li><br />
</ol><br />
<br />
==Доказательство корректности алгоритма==<br />
{{Теорема<br />
|statement=<br />
Расписание, построенное данным алгоритмом, является корректным и оптимальным.<br />
|proof=<br />
Доказательство будем вести от противного.<br/><br />
Рассмотрим расписание <tex>S_{1}</tex>, полученное после выполнения нашего алгоритма, и оптимальное расписание <tex>S_{2}</tex>.<br/><br />
Возьмём первый момент времени <tex>t_{1}</tex>, когда расписания различаются. Пусть в этот момент времени в <tex>S_{1}</tex>, будет выполняться работа с весом <tex>w_{1}</tex>, а в <tex>S_{2}</tex> {{---}} работа с весом <tex>w_{2}</tex>.<br/><br />
Это первый момент, в котором расписания отличаются, значит в <tex>S_{2}</tex> работа с весом <tex>w_{1}</tex> выполнится в момент времени <tex>t_{2} > t_{1}</tex>.<br/><br />
Поменяем местами работы с весами <tex>w_{1}</tex> и <tex>w_{2}</tex> в <tex>S_{2}</tex> и полуим расписание <tex>S_{3}</tex>. Это возможно, потому что время появления этих работ не меньше <tex>t_{1}</tex>.<br/><br />
При такой перестановке ответы на задачу для <tex>S_{2}</tex> и <tex>S_{3}</tex> будут отличаться на <br />
<ul><tex>t_{1}w_{2} + t_{2}w_{1} - t_{1}w_{1} + t_{2}w_{2} = t_{1}(w_{2} - w_{1}) + t_{2}(w_{1} - w_{2}) = (t_{1} - t_{2})(w_{2} - w_{1})</tex></ul><br />
Первая скобка отрицательная: <tex>t_{1} < t_{2}</tex>. Вторая скобка тоже отрицательная из того, что в <tex>S_{1}</tex> работа с весом <tex>w_1</tex> выполняется раньше, значит её вес должен быть больше <tex>w_2</tex>.<br/><br />
Итого имеем, что ответ для <tex>S_{2}</tex> больше, чем ответ для <tex>S_{3}</tex>. Следовательно расписание <tex>S_2</tex> неоптимальное. Получили противоречие. Значит не существует такого момента времени, когда расписание <tex>S_{1}</tex> отличается от оптимального. Следовательно мы доказали, что оно оптимальное.<br />
}}<br />
<br />
==Псевдокод==<br />
<tex> S \leftarrow \{1 \dots n\}</tex><br />
<tex> time \leftarrow 0</tex><br />
<tex> answer \leftarrow 0</tex><br />
'''WHILE''' <tex> S \neq \varnothing </tex><br />
<tex> j \leftarrow null </tex><br />
'''IF''' <tex> i \in S</tex> '''AND''' <tex> r_{i} \leq time</tex> '''AND''' <tex>\max w_{i} </tex><br />
<tex> j \leftarrow i </tex><br />
'''IF''' <tex>j \neq null </tex><br />
<tex> S \leftarrow S \setminus j</tex><br />
<tex> Answer \leftarrow Answer + time \cdot w_{j}</tex><br />
<tex> time++</tex><br />
<br />
==Сложность алгоритма==<br />
Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \max r_{i}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, очередь с приоритетами. Значит общее время работы алгоритма <tex>O((n + \max r_{i})\log n)</tex><br />
<br />
<br />
== Источники информации ==<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 84 - 85<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Теория расписаний]]</div>Sergej Arkhipovhttp://neerc.ifmo.ru/wiki/index.php?title=1ripi1sumwc&diff=470121ripi1sumwc2015-05-29T12:14:13Z<p>Sergej Arkhipov: </p>
<hr />
<div><tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum w_i C_i</tex><br />
<br />
{{Задача<br />
|definition=<br />
Дано <tex>n</tex> работ и один станок. Для каждой работы известно её время появления <tex>r_{i}</tex> и вес <tex>w_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>.Требуется выполнить все работы, чтобы значение <tex>\sum w_{i} C_{i}</tex> было минимальным, где <tex>C_{i}</tex> {{---}} время окончания работы.<br />
}}<br />
<br />
==Описание алгоритма==<br />
Пусть <tex>time</tex> {{---}} текущий момент времени.<br/><br />
Для каждого очередного значения <tex>time</tex>, которое изменяется от <tex>0</tex> до времени окончания последней работы, будем:<br />
<ol><br />
<li> Выбирать работу <tex>j</tex> из множества невыполненных работ, у которой <tex>r_{i} \le time</tex>, а значение <tex>w_{i}</tex> максимально.</li><br />
<li> Если мы смогли найти работу <tex>j</tex>, то выполняем её в момент времени <tex>time</tex> и удаляем из множества невыполненных работ.</li><br />
<li> Увеличиваем <tex>time</tex> на один.</li><br />
</ol><br />
<br />
==Доказательство корректности алгоритма==<br />
{{Теорема<br />
|statement=<br />
Расписание, построенное данным алгоритмом, является корректным и оптимальным.<br />
|proof=<br />
Доказательство будем вести от противного.<br/><br />
Рассмотрим расписание <tex>S_{1}</tex>, полученное после выполнения нашего алгоритма, и оптимальное расписание <tex>S_{2}</tex>.<br/><br />
Возьмём первый момент времени <tex>t_{1}</tex>, когда расписания различаются. Пусть в этот момент времени в <tex>S_{1}</tex>, будет выполняться работа с весом <tex>w_{1}</tex>, а в <tex>S_{2}</tex> {{---}} работа с весом <tex>w_{2}</tex>.<br/><br />
Это первый момент, в котором расписания отличаются, значит в <tex>S_{2}</tex> работа с весом <tex>w_{1}</tex> выполнится в момент времени <tex>t_{2} > t_{1}</tex>.<br/><br />
Поменяем местами работы с весами <tex>w_{1}</tex> и <tex>w_{2}</tex> в <tex>S_{2}</tex> и полуим расписание <tex>S_{3}</tex>. Это возможно, потому что время появления этих работ не меньше <tex>t_{1}</tex>.<br/><br />
При такой перестановке ответы на задачу для <tex>S_{2}</tex> и <tex>S_{3}</tex> будут отличаться на <br />
<ul><tex>t_{1}w_{2} + t_{2}w_{1} - t_{1}w_{1} + t_{2}w_{2} = t_{1}(w_{2} - w_{1}) + t_{2}(w_{1} - w_{2}) = (t_{1} - t_{2})(w_{2} - w_{1})</tex></ul><br />
Первая скобка отрицательная: <tex>t_{1} < t_{2}</tex>. Вторая скобка тоже отрицательная из того, что в <tex>S_{1}</tex> работа с весом <tex>w_1</tex> выполняется раньше, значит её вес должен быть больше <tex>w_2</tex>.<br/><br />
Итого имеем, что ответ для <tex>S_{2}</tex> больше, чем ответ для <tex>S_{3}</tex>. Следовательно расписание <tex>S_2</tex> неоптимальное. Получили противоречие. Значит не существует такого момента времени, когда расписание <tex>S_{1}</tex> отличается от оптимального. Следовательно мы доказали, что оно оптимальное.<br />
}}<br />
<br />
==Псевдокод==<br />
<tex> S \leftarrow \{1 \dots n\}</tex><br />
<tex> time \leftarrow 0</tex><br />
<tex> answer \leftarrow 0</tex><br />
'''WHILE''' <tex> S \neq \varnothing </tex><br />
<tex> j \leftarrow null </tex><br />
'''IF''' <tex> i \in S</tex> '''AND''' <tex> r_{i} \leq time</tex> '''AND''' <tex>\max w_{i} </tex><br />
<tex> j \leftarrow i </tex><br />
'''IF''' <tex>j \neq null </tex><br />
<tex> S \leftarrow S \setminus j</tex><br />
<tex> Answer \leftarrow Answer + time \cdot w_{j}</tex><br />
<tex> time++</tex><br />
<br />
==Сложность алгоритма==<br />
Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \max r_{i}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, очередь с приоритетами. Значит общее время работы алгоритма <tex>O((n + \max r_{i})\log n)</tex><br />
<br />
<br />
== Источники информации ==<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 84 - 85<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Теория расписаний]]</div>Sergej Arkhipovhttp://neerc.ifmo.ru/wiki/index.php?title=1ripi1sumwc&diff=470111ripi1sumwc2015-05-29T12:13:12Z<p>Sergej Arkhipov: </p>
<hr />
<div><tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum w_i C_i</tex><br />
<br />
{{Задача<br />
|definition=<br />
Дано <tex>n</tex> работ и один станок. Для каждой работы известно её время появления <tex>r_{i}</tex> и вес <tex>w_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>.Требуется выполнить все работы, чтобы значение <tex>\sum w_{i} C_{i}</tex> было минимальным, где <tex>C_{i}</tex> {{---}} время окончания работы.<br />
}}<br />
<br />
==Описание алгоритма==<br />
Пусть <tex>time</tex> {{---}} текущий момент времени.<br/><br />
Для каждого очередного значения <tex>time</tex>, которое изменяется от <tex>0</tex> до времени окончания последней работы, будем:<br />
<ol><br />
<li> Выбирать работу <tex>j</tex> из множества невыполненных работ, у которой <tex>r_{i} \le time</tex>, а значение <tex>w_{i}</tex> максимально.</li><br />
<li> Если мы смогли найти работу <tex>j</tex>, то выполняем её в момент времени <tex>time</tex> и удаляем из множества невыполненных работ.</li><br />
<li> Увеличиваем <tex>time</tex> на один.</li><br />
</ol><br />
<br />
==Доказательство корректности алгоритма==<br />
{{Теорема<br />
|statement=<br />
Расписание, построенное данным алгоритмом, является корректным и оптимальным.<br />
|proof=<br />
Доказательство будем вести от противного.<br/><br />
Рассмотрим расписание <tex>S_{1}</tex>, полученное после выполнения нашего алгоритма, и оптимальное расписание <tex>S_{2}</tex>.<br/><br />
Возьмём первый момент времени <tex>t_{1}</tex>, когда расписания различаются. Пусть в этот момент времени в <tex>S_{1}</tex>, будет выполняться работа с весом <tex>w_{1}</tex>, а в <tex>S_{2}</tex> {{---}} работа с весом <tex>w_{2}</tex>.<br/><br />
Это первый момент, в котором расписания отличаются, значит в <tex>S_{2}</tex> работа с весом <tex>w_{1}</tex> выполнится в момент времени <tex>t_{2} > t_{1}</tex>.<br/><br />
Поменяем местами работы с весами <tex>w_{1}</tex> и <tex>w_{2}</tex> в <tex>S_{2}</tex> и полуим расписание <tex>S_{3}</tex>. Это возможно, потому что время появления этих работ не меньше <tex>t_{1}</tex>.<br/><br />
При такой перестановке ответы на задачу для <tex>S_{2}</tex> и <tex>S_{3}</tex> будут отличаться на <br />
<ul><tex>t_{1}w_{2} + t_{2}w_{1} - t_{1}w_{1} + t_{2}w_{2} = t_{1}(w_{2} - w_{1}) + t_{2}(w_{1} - w_{2}) = (t_{1} - t_{2})(w_{2} - w_{1})</tex></ul><br />
Первая скобка отрицательная: <tex>t_{1} < t_{2}</tex>. Вторая скобка тоже отрицательная из того, что в <tex>S_{1}</tex> работа с весом <tex>w_1</tex> выполняется раньше, значит её вес должен быть больше <tex>w_2</tex>.<br/><br />
Итого имеем, что ответ для <tex>S_{2}</tex> больше, чем ответ для <tex>S_{3}</tex>. Следовательно расписание <tex>S_2</tex> неоптимальное. Получили противоречие. Значит не существует такого момента времени, когда расписание <tex>S_{1}</tex> отличается от оптимального. Следовательно мы доказали, что оно оптимальное.<br />
}}<br />
<br />
==Псевдокод==<br />
<tex> S \leftarrow \{1 \dots n\}</tex><br />
<tex> time \leftarrow 0</tex><br />
<tex> answer \leftarrow 0</tex><br />
'''WHILE''' <tex> S \neq \varnothing </tex><br />
<tex> j \leftarrow null </tex><br />
'''if''' <tex> i \in S</tex> '''and''' <tex> r_{i} \leq time</tex> '''and''' <tex>\max w_{i} </tex><br />
<tex> j \leftarrow i </tex><br />
'''if''' <tex>j \neq null </tex><br />
<tex> S \leftarrow S \setminus j</tex><br />
<tex> Answer \leftarrow Answer + time \cdot w_{j}</tex><br />
<tex> time++</tex><br />
<br />
==Сложность алгоритма==<br />
Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \max r_{i}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, очередь с приоритетами. Значит общее время работы алгоритма <tex>O((n + \max r_{i})\log n)</tex><br />
<br />
<br />
== Источники информации ==<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 84 - 85<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Теория расписаний]]</div>Sergej Arkhipovhttp://neerc.ifmo.ru/wiki/index.php?title=1ripi1sumwc&diff=470101ripi1sumwc2015-05-29T11:47:38Z<p>Sergej Arkhipov: </p>
<hr />
<div><tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum w_i C_i</tex><br />
<br />
{{Задача<br />
|definition=<br />
Дано <tex>n</tex> работ и один станок. Для каждой работы известно её время появления <tex>r_{i}</tex> и вес <tex>w_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>.Требуется выполнить все работы, чтобы значение <tex>\sum w_{i} C_{i}</tex> было минимальным, где <tex>C_{i}</tex> {{---}} время окончания работы.<br />
}}<br />
<br />
==Описание алгоритма==<br />
Пусть <tex>time</tex> {{---}} текущий момент времени.<br/><br />
Для каждого очередного значения <tex>time</tex>, которое изменяется от <tex>0</tex> до времени окончания последней работы, будем:<br />
<ol><br />
<li> Выбирать работу <tex>j</tex> из множества невыполненных работ, у которой <tex>r_{i} \le time</tex>, а значение <tex>w_{i}</tex> максимально.</li><br />
<li> Если мы смогли найти работу <tex>j</tex>, то выполняем её в момент времени <tex>time</tex> и удаляем из множества невыполненных работ.</li><br />
<li> Увеличиваем <tex>time</tex> на один.</li><br />
</ol><br />
<br />
==Доказательство корректности алгоритма==<br />
{{Теорема<br />
|statement=<br />
Расписание, построенное данным алгоритмом, является корректным и оптимальным.<br />
|proof=<br />
Доказательство будем вести от противного.<br/><br />
Рассмотрим расписание <tex>S_{1}</tex>, полученное после выполнения нашего алгоритма, и оптимальное расписание <tex>S_{2}</tex>.<br/><br />
Возьмём первый момент времени <tex>t_{1}</tex>, когда расписания различаются. Пусть в этот момент времени в <tex>S_{1}</tex>, будет выполняться работа с весом <tex>w_{1}</tex>, а в <tex>S_{2}</tex> {{---}} работа с весом <tex>w_{2}</tex>.<br/><br />
Это первый момент, в котором расписания отличаются, значит в <tex>S_{2}</tex> работа с весом <tex>w_{1}</tex> выполнится в момент времени <tex>t_{2} > t_{1}</tex>.<br/><br />
Поменяем местами работы с весами <tex>w_{1}</tex> и <tex>w_{2}</tex> в <tex>S_{2}</tex> и полуим расписание <tex>S_{3}</tex>. Это возможно, потому что время появления этих работ не меньше <tex>t_{1}</tex>.<br/><br />
При такой перестановке ответы на задачу для <tex>S_{2}</tex> и <tex>S_{3}</tex> будут отличаться на <br />
<ul><tex>t_{1}w_{2} + t_{2}w_{1} - t_{1}w_{1} + t_{2}w_{2} = t_{1}(w_{2} - w_{1}) + t_{2}(w_{1} - w_{2}) = (t_{1} - t_{2})(w_{2} - w_{1})</tex></ul><br />
Первая скобка отрицательная: <tex>t_{1} < t_{2}</tex>. Вторая скобка тоже отрицательная из того, что в <tex>S_{1}</tex> работа с весом <tex>w_1</tex> выполняется раньше, значит её вес должен быть больше <tex>w_2</tex>.<br/><br />
Итого имеем, что ответ для <tex>S_{2}</tex> больше, чем ответ для <tex>S_{3}</tex>. Следовательно расписание <tex>S_2</tex> неоптимальное. Получили противоречие. Значит не существует такого момента времени, когда расписание <tex>S_{1}</tex> отличается от оптимального. Следовательно мы доказали, что оно оптимальное.<br />
}}<br />
<br />
==Псевдокод==<br />
<tex> S \leftarrow \{1 \dots n\}</tex><br />
<tex> time \leftarrow 0</tex><br />
<tex> answer \leftarrow 0</tex><br />
while <tex> S \neq \varnothing </tex><br />
<tex> j \leftarrow i : (\max \limits_{i \in S, r_{i} \leq time} w_{i})</tex><br />
if <tex>j \neq null </tex><br />
<tex> S \leftarrow S \setminus j</tex><br />
<tex> Answer \leftarrow Answer + time \cdot w_{j}</tex><br />
<tex> time++</tex><br />
<br />
==Сложность алгоритма==<br />
Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \max r_{i}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, очередь с приоритетами. Значит общее время работы алгоритма <tex>O((n + \max r_{i})\log n)</tex><br />
<br />
<br />
== Источники информации ==<br />
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 84 - 85<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Теория расписаний]]</div>Sergej Arkhipovhttp://neerc.ifmo.ru/wiki/index.php?title=1ripi1sumwc&diff=470091ripi1sumwc2015-05-29T11:34:26Z<p>Sergej Arkhipov: </p>
<hr />
<div><tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum w_i C_i</tex><br />
<br />
{{Задача<br />
|definition=<br />
Дано <tex>n</tex> работ и один станок. Для каждой работы известно её время появления <tex>r_{i}</tex> и вес <tex>w_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>.Требуется выполнить все работы, чтобы значение <tex>\sum w_{i} C_{i}</tex> было минимальным, где <tex>C_{i}</tex> {{---}} время окончания работы.<br />
}}<br />
<br />
==Описание алгоритма==<br />
Пусть <tex>time</tex> {{---}} текущий момент времени.<br/><br />
Для каждого очередного значения <tex>time</tex>, которое изменяется от <tex>0</tex> до времени окончания последней работы, будем:<br />
<ol><br />
<li> Выбирать работу <tex>j</tex> из множества невыполненных работ, у которой <tex>r_{i} \le time</tex>, а значение <tex>w_{i}</tex> максимально.</li><br />
<li> Если мы смогли найти работу <tex>j</tex>, то выполняем её в момент времени <tex>time</tex> и удаляем из множества невыполненных работ.</li><br />
<li> Увеличиваем <tex>time</tex> на один.</li><br />
</ol><br />
<br />
==Доказательство корректности алгоритма==<br />
{{Теорема<br />
|statement=<br />
Расписание, построенное данным алгоритмом, является корректным и оптимальным.<br />
|proof=<br />
Доказательство будем вести от противного.<br/><br />
Рассмотрим расписание <tex>S_{1}</tex>, полученное после выполнения нашего алгоритма, и оптимальное расписание <tex>S_{2}</tex>.<br/><br />
Возьмём первый момент времени <tex>t_{1}</tex>, когда расписания различаются. Пусть в этот момент времени в <tex>S_{1}</tex>, будет выполняться работа с весом <tex>w_{1}</tex>, а в <tex>S_{2}</tex> {{---}} работа с весом <tex>w_{2}</tex>.<br/><br />
Это первый момент, в котором расписания отличаются, значит в <tex>S_{2}</tex> работа с весом <tex>w_{1}</tex> выполнится в момент времени <tex>t_{2} > t_{1}</tex>.<br/><br />
Поменяем местами работы с весами <tex>w_{1}</tex> и <tex>w_{2}</tex> в <tex>S_{2}</tex> и полуим расписание <tex>S_{3}</tex>. Это возможно, потому что время появления этих работ не меньше <tex>t_{1}</tex>.<br/><br />
При такой перестановке ответы на задачу для <tex>S_{2}</tex> и <tex>S_{3}</tex> будут отличаться на <br />
<ul><tex>t_{1}w_{2} + t_{2}w_{1} - t_{1}w_{1} + t_{2}w_{2} = t_{1}(w_{2} - w_{1}) + t_{2}(w_{1} - w_{2}) = (t_{1} - t_{2})(w_{2} - w_{1})</tex></ul><br />
Первая скобка отрицательная: <tex>t_{1} < t_{2}</tex>. Вторая скобка тоже отрицательная из того, что в <tex>S_{1}</tex> работа с весом <tex>w_1</tex> выполняется раньше, значит её вес должен быть больше <tex>w_2</tex>.<br/><br />
Итого имеем, что ответ для <tex>S_{2}</tex> больше, чем ответ для <tex>S_{3}</tex>. Следовательно расписание <tex>S_2</tex> неоптимальное. Получили противоречие. Значит не существует такого момента времени, когда расписание <tex>S_{1}</tex> отличается от оптимального. Следовательно мы доказали, что оно оптимальное.<br />
}}<br />
<br />
==Псевдокод==<br />
<tex> S \leftarrow \{1 \dots n\}</tex><br />
<tex> time \leftarrow 0</tex><br />
<tex> answer \leftarrow 0</tex><br />
while <tex> S \neq \varnothing </tex><br />
<tex> j \leftarrow i : (\max \limits_{i \in S, r_{i} \leq time} w_{i})</tex><br />
if <tex>j \neq null </tex><br />
<tex> S \leftarrow S \setminus j</tex><br />
<tex> Answer \leftarrow Answer + time \cdot w_{j}</tex><br />
<tex> time++</tex><br />
<br />
==Сложность алгоритма==<br />
Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \max r_{i}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, очередь с приоритетами. Значит общее время работы алгоритма <tex>O((n + \max r_{i})\log n)</tex><br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Теория расписаний]]</div>Sergej Arkhipovhttp://neerc.ifmo.ru/wiki/index.php?title=1ripi1sumwc&diff=470081ripi1sumwc2015-05-29T11:33:50Z<p>Sergej Arkhipov: </p>
<hr />
<div><tex dpi = "200">\mid r_i,p_i = 1 \mid \sum w_i C_i</tex><br />
<br />
{{Задача<br />
|definition=<br />
Дано <tex>n</tex> работ и один станок. Для каждой работы известно её время появления <tex>r_{i}</tex> и вес <tex>w_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>.Требуется выполнить все работы, чтобы значение <tex>\sum w_{i} C_{i}</tex> было минимальным, где <tex>C_{i}</tex> {{---}} время окончания работы.<br />
}}<br />
<br />
==Описание алгоритма==<br />
Пусть <tex>time</tex> {{---}} текущий момент времени.<br/><br />
Для каждого очередного значения <tex>time</tex>, которое изменяется от <tex>0</tex> до времени окончания последней работы, будем:<br />
<ol><br />
<li> Выбирать работу <tex>j</tex> из множества невыполненных работ, у которой <tex>r_{i} \le time</tex>, а значение <tex>w_{i}</tex> максимально.</li><br />
<li> Если мы смогли найти работу <tex>j</tex>, то выполняем её в момент времени <tex>time</tex> и удаляем из множества невыполненных работ.</li><br />
<li> Увеличиваем <tex>time</tex> на один.</li><br />
</ol><br />
<br />
==Доказательство корректности алгоритма==<br />
{{Теорема<br />
|statement=<br />
Расписание, построенное данным алгоритмом, является корректным и оптимальным.<br />
|proof=<br />
Доказательство будем вести от противного.<br/><br />
Рассмотрим расписание <tex>S_{1}</tex>, полученное после выполнения нашего алгоритма, и оптимальное расписание <tex>S_{2}</tex>.<br/><br />
Возьмём первый момент времени <tex>t_{1}</tex>, когда расписания различаются. Пусть в этот момент времени в <tex>S_{1}</tex>, будет выполняться работа с весом <tex>w_{1}</tex>, а в <tex>S_{2}</tex> {{---}} работа с весом <tex>w_{2}</tex>.<br/><br />
Это первый момент, в котором расписания отличаются, значит в <tex>S_{2}</tex> работа с весом <tex>w_{1}</tex> выполнится в момент времени <tex>t_{2} > t_{1}</tex>.<br/><br />
Поменяем местами работы с весами <tex>w_{1}</tex> и <tex>w_{2}</tex> в <tex>S_{2}</tex> и полуим расписание <tex>S_{3}</tex>. Это возможно, потому что время появления этих работ не меньше <tex>t_{1}</tex>.<br/><br />
При такой перестановке ответы на задачу для <tex>S_{2}</tex> и <tex>S_{3}</tex> будут отличаться на <br />
<ul><tex>t_{1}w_{2} + t_{2}w_{1} - t_{1}w_{1} + t_{2}w_{2} = t_{1}(w_{2} - w_{1}) + t_{2}(w_{1} - w_{2}) = (t_{1} - t_{2})(w_{2} - w_{1})</tex></ul><br />
Первая скобка отрицательная: <tex>t_{1} < t_{2}</tex>. Вторая скобка тоже отрицательная из того, что в <tex>S_{1}</tex> работа с весом <tex>w_1</tex> выполняется раньше, значит её вес должен быть больше <tex>w_2</tex>.<br/><br />
Итого имеем, что ответ для <tex>S_{2}</tex> больше, чем ответ для <tex>S_{3}</tex>. Следовательно расписание <tex>S_2</tex> неоптимальное. Получили противоречие. Значит не существует такого момента времени, когда расписание <tex>S_{1}</tex> отличается от оптимального. Следовательно мы доказали, что оно оптимальное.<br />
}}<br />
<br />
==Псевдокод==<br />
<tex> S \leftarrow \{1 \dots n\}</tex><br />
<tex> time \leftarrow 0</tex><br />
<tex> answer \leftarrow 0</tex><br />
while <tex> S \neq \varnothing </tex><br />
<tex> j \leftarrow i : (\max \limits_{i \in S, r_{i} \leq time} w_{i})</tex><br />
if <tex>j \neq null </tex><br />
<tex> S \leftarrow S \setminus j</tex><br />
<tex> Answer \leftarrow Answer + time \cdot w_{j}</tex><br />
<tex> time++</tex><br />
<br />
==Сложность алгоритма==<br />
Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \max r_{i}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, очередь с приоритетами. Значит общее время работы алгоритма <tex>O((n + \max r_{i})\log n)</tex><br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Теория расписаний]]</div>Sergej Arkhipovhttp://neerc.ifmo.ru/wiki/index.php?title=1ripi1sumwc&diff=470071ripi1sumwc2015-05-29T11:33:28Z<p>Sergej Arkhipov: </p>
<hr />
<div><tex dpi = "200">\mid r_i,p_i = 1 \mid \sum w_i C_i</tex><br />
{{Задача<br />
|definition=<br />
Дано <tex>n</tex> работ и один станок. Для каждой работы известно её время появления <tex>r_{i}</tex> и вес <tex>w_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>.Требуется выполнить все работы, чтобы значение <tex>\sum w_{i} C_{i}</tex> было минимальным, где <tex>C_{i}</tex> {{---}} время окончания работы.<br />
}}<br />
<br />
==Описание алгоритма==<br />
Пусть <tex>time</tex> {{---}} текущий момент времени.<br/><br />
Для каждого очередного значения <tex>time</tex>, которое изменяется от <tex>0</tex> до времени окончания последней работы, будем:<br />
<ol><br />
<li> Выбирать работу <tex>j</tex> из множества невыполненных работ, у которой <tex>r_{i} \le time</tex>, а значение <tex>w_{i}</tex> максимально.</li><br />
<li> Если мы смогли найти работу <tex>j</tex>, то выполняем её в момент времени <tex>time</tex> и удаляем из множества невыполненных работ.</li><br />
<li> Увеличиваем <tex>time</tex> на один.</li><br />
</ol><br />
<br />
==Доказательство корректности алгоритма==<br />
{{Теорема<br />
|statement=<br />
Расписание, построенное данным алгоритмом, является корректным и оптимальным.<br />
|proof=<br />
Доказательство будем вести от противного.<br/><br />
Рассмотрим расписание <tex>S_{1}</tex>, полученное после выполнения нашего алгоритма, и оптимальное расписание <tex>S_{2}</tex>.<br/><br />
Возьмём первый момент времени <tex>t_{1}</tex>, когда расписания различаются. Пусть в этот момент времени в <tex>S_{1}</tex>, будет выполняться работа с весом <tex>w_{1}</tex>, а в <tex>S_{2}</tex> {{---}} работа с весом <tex>w_{2}</tex>.<br/><br />
Это первый момент, в котором расписания отличаются, значит в <tex>S_{2}</tex> работа с весом <tex>w_{1}</tex> выполнится в момент времени <tex>t_{2} > t_{1}</tex>.<br/><br />
Поменяем местами работы с весами <tex>w_{1}</tex> и <tex>w_{2}</tex> в <tex>S_{2}</tex> и полуим расписание <tex>S_{3}</tex>. Это возможно, потому что время появления этих работ не меньше <tex>t_{1}</tex>.<br/><br />
При такой перестановке ответы на задачу для <tex>S_{2}</tex> и <tex>S_{3}</tex> будут отличаться на <br />
<ul><tex>t_{1}w_{2} + t_{2}w_{1} - t_{1}w_{1} + t_{2}w_{2} = t_{1}(w_{2} - w_{1}) + t_{2}(w_{1} - w_{2}) = (t_{1} - t_{2})(w_{2} - w_{1})</tex></ul><br />
Первая скобка отрицательная: <tex>t_{1} < t_{2}</tex>. Вторая скобка тоже отрицательная из того, что в <tex>S_{1}</tex> работа с весом <tex>w_1</tex> выполняется раньше, значит её вес должен быть больше <tex>w_2</tex>.<br/><br />
Итого имеем, что ответ для <tex>S_{2}</tex> больше, чем ответ для <tex>S_{3}</tex>. Следовательно расписание <tex>S_2</tex> неоптимальное. Получили противоречие. Значит не существует такого момента времени, когда расписание <tex>S_{1}</tex> отличается от оптимального. Следовательно мы доказали, что оно оптимальное.<br />
}}<br />
<br />
==Псевдокод==<br />
<tex> S \leftarrow \{1 \dots n\}</tex><br />
<tex> time \leftarrow 0</tex><br />
<tex> answer \leftarrow 0</tex><br />
while <tex> S \neq \varnothing </tex><br />
<tex> j \leftarrow i : (\max \limits_{i \in S, r_{i} \leq time} w_{i})</tex><br />
if <tex>j \neq null </tex><br />
<tex> S \leftarrow S \setminus j</tex><br />
<tex> Answer \leftarrow Answer + time \cdot w_{j}</tex><br />
<tex> time++</tex><br />
<br />
==Сложность алгоритма==<br />
Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \max r_{i}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, очередь с приоритетами. Значит общее время работы алгоритма <tex>O((n + \max r_{i})\log n)</tex><br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Теория расписаний]]</div>Sergej Arkhipovhttp://neerc.ifmo.ru/wiki/index.php?title=1ripi1sumwc&diff=470041ripi1sumwc2015-05-29T11:21:47Z<p>Sergej Arkhipov: /* Постановка задачи */</p>
<hr />
<div>{{Задача<br />
|definition=<br />
Дано <tex>n</tex> работ и один станок. Для каждой работы известно её время появления <tex>r_{i}</tex> и вес <tex>w_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>.Требуется выполнить все работы, чтобы значение <tex>\sum w_{i} C_{i}</tex> было минимальным, где <tex>C_{i}</tex> {{---}} время окончания работы.<br />
}}<br />
<br />
==Описание алгоритма==<br />
Пусть <tex>time</tex> {{---}} текущий момент времени.<br/><br />
Для каждого очередного значения <tex>time</tex>, которое изменяется от <tex>0</tex> до времени окончания последней работы, будем:<br />
<ol><br />
<li> Выбирать работу <tex>j</tex> из множества невыполненных работ, у которой <tex>r_{i} \le time</tex>, а значение <tex>w_{i}</tex> максимально.</li><br />
<li> Если мы смогли найти работу <tex>j</tex>, то выполняем её в момент времени <tex>time</tex> и удаляем из множества невыполненных работ.</li><br />
<li> Увеличиваем <tex>time</tex> на один.</li><br />
</ol><br />
<br />
==Доказательство корректности алгоритма==<br />
{{Теорема<br />
|statement=<br />
Расписание, построенное данным алгоритмом, является корректным и оптимальным.<br />
|proof=<br />
Доказательство будем вести от противного.<br/><br />
Рассмотрим расписание <tex>S_{1}</tex>, полученное после выполнения нашего алгоритма, и оптимальное расписание <tex>S_{2}</tex>.<br/><br />
Возьмём первый момент времени <tex>t_{1}</tex>, когда расписания различаются. Пусть в этот момент времени в <tex>S_{1}</tex>, будет выполняться работа с весом <tex>w_{1}</tex>, а в <tex>S_{2}</tex> {{---}} работа с весом <tex>w_{2}</tex>.<br/><br />
Это первый момент, в котором расписания отличаются, значит в <tex>S_{2}</tex> работа с весом <tex>w_{1}</tex> выполнится в момент времени <tex>t_{2} > t_{1}</tex>.<br/><br />
Поменяем местами работы с весами <tex>w_{1}</tex> и <tex>w_{2}</tex> в <tex>S_{2}</tex> и полуим расписание <tex>S_{3}</tex>. Это возможно, потому что время появления этих работ не меньше <tex>t_{1}</tex>.<br/><br />
При такой перестановке ответы на задачу для <tex>S_{2}</tex> и <tex>S_{3}</tex> будут отличаться на <br />
<ul><tex>t_{1}w_{2} + t_{2}w_{1} - t_{1}w_{1} + t_{2}w_{2} = t_{1}(w_{2} - w_{1}) + t_{2}(w_{1} - w_{2}) = (t_{1} - t_{2})(w_{2} - w_{1})</tex></ul><br />
Первая скобка отрицательная: <tex>t_{1} < t_{2}</tex>. Вторая скобка тоже отрицательная из того, что в <tex>S_{1}</tex> работа с весом <tex>w_1</tex> выполняется раньше, значит её вес должен быть больше <tex>w_2</tex>.<br/><br />
Итого имеем, что ответ для <tex>S_{2}</tex> больше, чем ответ для <tex>S_{3}</tex>. Следовательно расписание <tex>S_2</tex> неоптимальное. Получили противоречие. Значит не существует такого момента времени, когда расписание <tex>S_{1}</tex> отличается от оптимального. Следовательно мы доказали, что оно оптимальное.<br />
}}<br />
<br />
==Псевдокод==<br />
<tex> S \leftarrow \{1 \dots n\}</tex><br />
<tex> time \leftarrow 0</tex><br />
<tex> answer \leftarrow 0</tex><br />
while <tex> S \neq \varnothing </tex><br />
<tex> j \leftarrow i : (\max \limits_{i \in S, r_{i} \leq time} w_{i})</tex><br />
if <tex>j \neq null </tex><br />
<tex> S \leftarrow S \setminus j</tex><br />
<tex> Answer \leftarrow Answer + time \cdot w_{j}</tex><br />
<tex> time++</tex><br />
<br />
==Сложность алгоритма==<br />
Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \max r_{i}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, очередь с приоритетами. Значит общее время работы алгоритма <tex>O((n + \max r_{i})\log n)</tex><br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Теория расписаний]]</div>Sergej Arkhipov