24
правки
Изменения
Фиксы
== Сведение к другой задаче ==
При сведении текущей задачи теории расписаний <tex> S </tex> к какой-то другой <tex> S' </tex>(не обязательно задаче теории расписаний) необходимо доказать два пункта:
# Допустимость расписания, построенного с помощью задачи <tex> S' </tex>, или существование способа его трансформации в допустимое без нарушения оптимальности.
# Следствие того, что если мы оптимизируем <tex> S' </tex>, мы также оптимизируем ответ для <tex> S </tex>.
'''Примечание — если ''': если требуется полиномиальное время для решения задачи, требуется, чтобы сведение к другой задаче и трансформация расписания в допустимое также происходили должны происходить за полиномиальное время.
С помощью этого метода решаются:
* Некоторые задачи класса Open Shop при условии <tex>p_{ij}=1</tex> сводятся к задачам равной длительности на параллельных станках.
** :[[Opij1Sumwc|<tex> O \mid p_{ij} = 1 \mid \sum w_i C_i </tex> ([[Opij1Sumwc|ссылка]])** :<tex> O \mid p_{ij} = 1, r_i \mid C_{max} </tex> <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 161</ref>
* Некоторые задачи класса Flow Shop при условии <tex>p_{ij}=1</tex> сводятся к задаче на одном станке.
** :[[Fpij1sumwu|<tex> F \mid p_{ij} = 1 \mid \sum w_i U_i </tex> ([[Fpij1sumwu|ссылка]])
* Часто в задачах, в которых допускаются прерывания, оптимальный ответ совпадает с соответствующими задачами без прерываний:
** :<tex> P \mid pmtn \mid \sum w_i C_i </tex> <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 121</ref>** :[[Flow shop|<tex> F2 \mid pmtn \mid C_{max} </tex> ([[Flow_shop|ссылка]])
* Некоторые задачи проверки существования расписания сводятся к задаче поиска максимального потока:
** :<tex> Q \mid pmtn, r_i\mid L_{max} </tex> <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 129-133</ref>** :[[RSumCi|<tex> R \mid \mid \sum C_i </tex> ([[RSumCi|ссылка]])* Некоторые задачи сводятся к другим похожим задачам теории расписаний путем преобразования их расписаний:*:[[1outtreesumwc|<tex> 1 \mid intree \mid \sum w_i C_i </tex> ([[1outtreesumwc|ссылка]])
== Построение расписания по нижней оценке ==
Этот метод обычно применим к задачам, в которых целевая функция — <tex> C_{max}</tex>. Построим какой-то набор Обычно построение расписания по нижней оценке происходит в два этапа:# Построение некоторого набора нижних ограничений на произвольное расписание для задачи <tex> S </tex> и возьмем из них максимальное. Затем построим произвольное допустимое расписание# Построение произвольного допустимого расписания, достигающее этой оценкидостигающего максимального ограничения из построенного набора.
С помощью этого метода решаютсяследующие задачи:
* <tex> P \mid pmtn \mid C_{max}</tex> <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 108</ref>
* <tex> R \mid pmtn \mid C_{max}</tex> <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 137-139</ref>
* [[Opij1Cmax|<tex> O \mid p_{ij}=1 \mid C_{max}</tex> ([[Opij1Cmax|ссылка]])* [[QpmtnCmax|<tex> Q \mid pmtn \mid C_{max}</tex> ([[QpmtnCmax|ссылка]])
=== P | pmtn | C_max ===
Найдем набор ограничений на значение <tex> C_{max} </tex> для произвольного допустимого расписания <tex> S </tex> : # В допустимом расписании выполнение всех работ не может завершиться раньше одной из них, поэтому <tex> T C_{max} \ge geqslant p_i </tex>.# Если все станки работали время <tex> T C_{max} </tex>, на них могло выполниться не больше <tex> Tm C_{max} \cdot m </tex> работы, то есть <tex> \sum\limits_i p_i \le Tm leqslant C_{max} \cdot m </tex> и <tex> T C_{max} \ge geqslant \frac1m dfrac1m \sum\limits_i p_i </tex>.# Тогда Из этих ограничений следует, что <tex> T_C_{minmax} = \max {\left(\max\limits_i p_i, ; \frac1m dfrac1m \sum\limits_i p_i\right)} </tex>. Построим расписание, подходящее под эту границу: будем по очереди заполнять машины работами в произвольном порядке, и если очередная работа не помещается на текущей машине полностью, перенесем ее выходящую за <tex> T_C_{minmax} </tex> часть на следующую машину. Благодаря первому ограничению никакая работа не будет выполняться одновременно на двух станках, а благодаря второму — не останется работы, которую мы не сможем выполнить.
== Бинарный поиск по ответу ==
Этот способ часто подходит для задач, в которых надо минимизировать <tex>C_{max} </tex> (если мы умеем решать соответствующую задачу существования расписания), реже для <tex> \sum w_i U_i </tex>. Важно помнить, что если требуется полиномиальное по <tex> n </tex> решение, оно не должно зависеть от логарифма ответа, но иногда ответ ограничен полиномом от <tex>n</tex>, и мы можем применить этот метод.
== Жадное построение расписания ==
{{Определение
|definition=[[Теорема Радо-Эдмондса (жадный алгоритм)|'''Жадный алгоритм''' ]] — алгоритм, в котором локальные оптимизации решения достигают глобального оптимумазадач путем выбора локально оптимальных решений на каждом этапе алгоритма.
}}
Естественно, далеко не все оптимизационные задачи можно решать жадно — для этого сначала необходимо доказать оптимальность жадного выбора.
С помощью этого метода решаются:
* [[Правило Лаулера|<tex> 1 \mid prec \mid f_{max} </tex> ([[Правило Лаулера|''Lawler's algorithm]])* [[1outtreesumwc|<tex> 1 \mid outtree \mid \sum w_i C_i </tex> ([[1outtreesumwc|ссылка]])* [[1pi1sumwu|<tex> 1 \mid p_i = 1 \mid \sum w_i U_i </tex> ([[1pi1sumwu|''Earliest Due Date rule'']])* [[1sumu|<tex> 1 \mid \mid \sum U_i </tex> ([[1sumu|ссылка]])
Обычно оптимальность жадного выбора доказывают двумя способами:
Приведем пример часто распространенных '''неправильных''' действий при доказательстве оптимальности жадного алгоритма:
Пусть предложенным нами алгоритмом мы получили какое-то решение <tex> S </tex>. Атомарными изменениями в этом решении <tex> S </tex> будем получать другие допустимые решения <tex> S' </tex> и докажем, что <tex> f(S) \le leqslant f(S') </tex>. Тогда решение <tex> S </tex> — оптимально.
Проблема в этих рассуждениях в том, что ими мы доказываем локальную оптимальность алгоритма в решении <tex> S </tex>. Получение же глобального минимума может потребовать нескольких атомарных изменений в расписании, поэтому доказать оптимальность таким образом в общем случае невозможно. Как ближайшую аналогию, можно привести '''неправильное''' утверждение для произвольной функции <tex> f(\bar x) </tex> — «если все частные производные <tex> \fracdfrac{\partial f}{\partial x_1} \dots \fracdfrac{\partial f}{\partial x_n} </tex> неотрицательны, то в точке <tex> \bar x </tex> наблюдается глобальный минимум».
=== Правильно ===
При доказательстве оптимательности применима стратегия '''аргумент замены''' (англ. ''exchange argument''). Стратегия заключается в рассмотрении текущего решения <tex> S </tex> и оптимального решения <tex> O </tex>. Далее предлагается способ модификации <tex> O </tex> в <tex> O'</tex> так, что:
# <tex> f(O') \le leqslant f(O) </tex>, то есть <tex> O' </tex> также оптимально.
# <tex> O' </tex> «более похоже» на <tex> S </tex>, чем на <tex> O </tex>.
Если такой способ найден, получаем, что какой-то последовательностью модификаций <tex> O \to O_t' \to \dots \to O_1' \to S </tex> получим <tex> f(S) \le leqslant f(O_1') \le leqslant \dots \le leqslant f(O_t') \le leqslant f(O) </tex>, из чего следует оптимальность <tex> S </tex>.
Отношение «более похоже» должно быть [[Отношение порядка | отношением частичного строгого порядка]]. Часто в качестве него можно выбрать отношение «длина наибольшего общего префикса решения <tex> A </tex> и <tex> S </tex> меньше наибольшего общего префикса решения <tex> B </tex> и <tex> S </tex>». Тогда если мы сможем увеличить длину наибольшего общего префикса для оптимального решения, не нарушив оптимальности, мы приблизимся к <tex> S </tex>. Можно выбирать и более сложные отношения, например, в доказательстве оптимальности алгоритма <tex> P \mid \mid \sum w_i C_i </tex> для решения задачи <tex> P \mid pmtn \mid \sum w_i C_i </tex> используется отношение «время последнего прерывания больше или количество прерываний меньше».
* Peter Brucker «Scheduling Algorithms», fifth edition, Springer ISBN 978-3-540-69515-8
[[Категория: Дискретная математика Алгоритмы и алгоритмыструктуры данных]]
[[Категория: Теория расписаний]]
