Викиконспекты - Вклад участника [ru]

Методы решения задач теории расписаний

2020-03-31T00:34:58Z

188.19.42.255: /* P | pmtn | C_max */

== Сведение к другой задаче ==
При сведении текущей задачи теории расписаний <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>]]
*:<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>]]
* Часто в задачах, в которых допускаются прерывания, оптимальный ответ совпадает с соответствующими задачами без прерываний:
*:<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>]]
* Ряд задач можно свести к задаче поиска максимального потока:
*:<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>]]
* Некоторые задачи сводятся к другим похожим задачам теории расписаний путем преобразования их расписаний:
*:[[1outtreesumwc|<tex> 1 \mid intree \mid \sum w_i C_i </tex>]]

== Построение расписания по нижней оценке ==
Этот метод обычно применим к задачам, в которых целевая функция — <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>
* [[RpmtnCmax|<tex> R \mid pmtn \mid C_{max}</tex>]]
* [[Opij1Cmax|<tex> O \mid p_{ij}=1 \mid C_{max}</tex>]]
* [[QpmtnCmax|<tex> Q \mid pmtn \mid C_{max}</tex>]]

Ниже будет рассмотрен частный пример решения задачи подобным образом:
=== P | pmtn | C_max ===
{{Задача
|definition = Имеется <tex>m</tex> однородных машин, работающих параллельно, и <tex>n</tex> работ, которые могут быть прерваны и продолжены позже. Необходимо минимизировать время выполнения всех работ
}}
Найдем набор ограничений на значение <tex> C_{max} </tex> для произвольного допустимого расписания <tex> S </tex> :
# В допустимом расписании выполнение всех работ не может завершиться раньше одной из них, поэтому <tex> C_{max} \geqslant p_i </tex>.
# Если все станки работали время <tex> C_{max} </tex>, на них могло выполниться не больше <tex> C_{max} \cdot m </tex> работы, то есть <tex> \sum\limits_{i=1}^n p_i \leqslant C_{max} \cdot m </tex> и <tex> C_{max} \geqslant \dfrac1m \sum\limits_{i=1}^n p_i </tex>.
Из этих ограничений следует, что <tex> C_{max} = \max {\left( \max\limits_{i=1 \cdots n} p_i,~ \dfrac1m \sum\limits_{i=1}^n p_i \right)} </tex>.

Построим расписание, подходящее под эту границу: будем по очереди заполнять машины работами в произвольном порядке, и если очередная работа не помещается на текущей машине полностью, перенесем ее выходящую за <tex> C_{max} </tex> часть на следующую машину. Благодаря первому ограничению никакая работа не будет выполняться одновременно на двух станках, а благодаря второму — не останется работы, которую мы не сможем выполнить.

== Бинарный поиск по ответу ==
Этот способ часто подходит для задач, в которых надо минимизировать <tex>C_{max} </tex> (если мы умеем решать соответствующую задачу существования расписания), реже для <tex> \sum w_i U_i </tex>. Важно помнить, что если требуется полиномиальное по <tex> n </tex> решение, оно не должно зависеть от логарифма ответа, но иногда ответ ограничен полиномом от <tex>n</tex>, и мы можем применить этот метод.

Примером решения задач подобным методом служит следующая задача:
[[QpmtnriLmax|<tex> Q \mid pmtn, r_i \mid L_{max} </tex>]]

== Жадное построение расписания ==
Для решения задач теории расписаний часто применяется [[Определение матроида|теория матроидо]]в, а в частности — [[Теорема Радо-Эдмондса (жадный алгоритм)|жадный алгоритм]]: алгоритм решения задач путем выбора локально оптимальных решений на каждом этапе алгоритма.
Естественно, далеко не все оптимизационные задачи можно решать жадно — для этого сначала необходимо доказать оптимальность жадного выбора.

С помощью этого метода решаются:
* [[Правило Лаулера|<tex> 1 \mid prec \mid f_{max} </tex>]]
* [[1outtreesumwc|<tex> 1 \mid outtree \mid \sum w_i C_i </tex>]]
* [[1pi1sumwu|<tex> 1 \mid p_i = 1 \mid \sum w_i U_i </tex>]]
* [[1sumu|<tex> 1 \mid \mid \sum U_i </tex>]]

Обычно оптимальность жадного выбора доказывают двумя способами:

=== Неправильно ===
Приведем пример часто распространенных '''неправильных''' действий при доказательстве оптимальности жадного алгоритма:

Пусть предложенным нами алгоритмом мы получили какое-то решение <tex> S </tex>. Атомарными изменениями в этом решении <tex> S </tex> будем получать другие допустимые решения <tex> S' </tex> и докажем, что <tex> f(S) \leqslant f(S') </tex>. Тогда решение <tex> S </tex> — оптимально.

Проблема в этих рассуждениях в том, что ими мы доказываем локальную оптимальность алгоритма в решении <tex> S </tex>. Получение же глобального минимума может потребовать нескольких атомарных изменений в расписании, поэтому доказать оптимальность таким образом в общем случае невозможно. Как ближайшую аналогию, можно привести '''неправильное''' утверждение для произвольной функции <tex> f(\bar x) </tex> — «если все частные производные <tex> \dfrac{\partial f}{\partial x_1} \dots \dfrac{\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') \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) \leqslant f(O_1') \leqslant \dots \leqslant f(O_t') \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> используется отношение «время последнего прерывания больше или количество прерываний меньше».

== См. также. ==
* [[Правило Лаулера]]
* [[Flow shop]]
* [[Opi1sumu|<tex> O \mid p_{ij} = 1 \mid \sum U_i</tex>]]

== Примечания ==
<references/>

== Источники информации ==
* Peter Brucker «Scheduling Algorithms», fifth edition, Springer ISBN 978-3-540-69515-8

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Теория расписаний]]

Методы решения задач теории расписаний

2020-03-31T00:34:38Z

188.19.42.255: /* P | pmtn | C_max */

== Сведение к другой задаче ==
При сведении текущей задачи теории расписаний <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>]]
*:<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>]]
* Часто в задачах, в которых допускаются прерывания, оптимальный ответ совпадает с соответствующими задачами без прерываний:
*:<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>]]
* Ряд задач можно свести к задаче поиска максимального потока:
*:<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>]]
* Некоторые задачи сводятся к другим похожим задачам теории расписаний путем преобразования их расписаний:
*:[[1outtreesumwc|<tex> 1 \mid intree \mid \sum w_i C_i </tex>]]

== Построение расписания по нижней оценке ==
Этот метод обычно применим к задачам, в которых целевая функция — <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>
* [[RpmtnCmax|<tex> R \mid pmtn \mid C_{max}</tex>]]
* [[Opij1Cmax|<tex> O \mid p_{ij}=1 \mid C_{max}</tex>]]
* [[QpmtnCmax|<tex> Q \mid pmtn \mid C_{max}</tex>]]

Ниже будет рассмотрен частный пример решения задачи подобным образом:
=== P | pmtn | C_max ===
{{Задача
|definition = Имеется <tex>m</tex> однородных машин, работающих параллельно, и <tex>n</tex> работ, которые могут быть прерваны и продолжены позже. Необходимо минимизировать время выполнения всех работ
}}
Найдем набор ограничений на значение <tex> C_{max} </tex> для произвольного допустимого расписания <tex> S </tex> :
# В допустимом расписании выполнение всех работ не может завершиться раньше одной из них, поэтому <tex> C_{max} \geqslant p_i </tex>.
# Если все станки работали время <tex> C_{max} </tex>, на них могло выполниться не больше <tex> C_{max} \cdot m </tex> работы, то есть <tex> \sum\limits_{i=1}^n p_i \leqslant C_{max} \cdot m </tex> и <tex> C_{max} \geqslant \dfrac1m \sum\limits_{i=1}^n p_i </tex>.
Из этих ограничений следует, что <tex> C_{max} = \max {\left( \max\limits_{i=1 \hdots n} p_i,~ \dfrac1m \sum\limits_{i=1}^n p_i \right)} </tex>.

Построим расписание, подходящее под эту границу: будем по очереди заполнять машины работами в произвольном порядке, и если очередная работа не помещается на текущей машине полностью, перенесем ее выходящую за <tex> C_{max} </tex> часть на следующую машину. Благодаря первому ограничению никакая работа не будет выполняться одновременно на двух станках, а благодаря второму — не останется работы, которую мы не сможем выполнить.

== Бинарный поиск по ответу ==
Этот способ часто подходит для задач, в которых надо минимизировать <tex>C_{max} </tex> (если мы умеем решать соответствующую задачу существования расписания), реже для <tex> \sum w_i U_i </tex>. Важно помнить, что если требуется полиномиальное по <tex> n </tex> решение, оно не должно зависеть от логарифма ответа, но иногда ответ ограничен полиномом от <tex>n</tex>, и мы можем применить этот метод.

Примером решения задач подобным методом служит следующая задача:
[[QpmtnriLmax|<tex> Q \mid pmtn, r_i \mid L_{max} </tex>]]

== Жадное построение расписания ==
Для решения задач теории расписаний часто применяется [[Определение матроида|теория матроидо]]в, а в частности — [[Теорема Радо-Эдмондса (жадный алгоритм)|жадный алгоритм]]: алгоритм решения задач путем выбора локально оптимальных решений на каждом этапе алгоритма.
Естественно, далеко не все оптимизационные задачи можно решать жадно — для этого сначала необходимо доказать оптимальность жадного выбора.

С помощью этого метода решаются:
* [[Правило Лаулера|<tex> 1 \mid prec \mid f_{max} </tex>]]
* [[1outtreesumwc|<tex> 1 \mid outtree \mid \sum w_i C_i </tex>]]
* [[1pi1sumwu|<tex> 1 \mid p_i = 1 \mid \sum w_i U_i </tex>]]
* [[1sumu|<tex> 1 \mid \mid \sum U_i </tex>]]

Обычно оптимальность жадного выбора доказывают двумя способами:

=== Неправильно ===
Приведем пример часто распространенных '''неправильных''' действий при доказательстве оптимальности жадного алгоритма:

Пусть предложенным нами алгоритмом мы получили какое-то решение <tex> S </tex>. Атомарными изменениями в этом решении <tex> S </tex> будем получать другие допустимые решения <tex> S' </tex> и докажем, что <tex> f(S) \leqslant f(S') </tex>. Тогда решение <tex> S </tex> — оптимально.

Проблема в этих рассуждениях в том, что ими мы доказываем локальную оптимальность алгоритма в решении <tex> S </tex>. Получение же глобального минимума может потребовать нескольких атомарных изменений в расписании, поэтому доказать оптимальность таким образом в общем случае невозможно. Как ближайшую аналогию, можно привести '''неправильное''' утверждение для произвольной функции <tex> f(\bar x) </tex> — «если все частные производные <tex> \dfrac{\partial f}{\partial x_1} \dots \dfrac{\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') \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) \leqslant f(O_1') \leqslant \dots \leqslant f(O_t') \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> используется отношение «время последнего прерывания больше или количество прерываний меньше».

== См. также. ==
* [[Правило Лаулера]]
* [[Flow shop]]
* [[Opi1sumu|<tex> O \mid p_{ij} = 1 \mid \sum U_i</tex>]]

== Примечания ==
<references/>

== Источники информации ==
* Peter Brucker «Scheduling Algorithms», fifth edition, Springer ISBN 978-3-540-69515-8

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Теория расписаний]]