Методы решения задач теории расписаний — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показаны 42 промежуточные версии 9 участников)
Строка 1: Строка 1:
 
== Сведение к другой задаче ==
 
== Сведение к другой задаче ==
При сведении текущей задачи теории расписаний <tex> S </tex> к какой-то другой <tex> S' </tex> необходимо доказать два пункта:
+
При сведении текущей задачи теории расписаний <tex> S </tex> к какой-то другой <tex> S' </tex> (не обязательно задаче теории расписаний) необходимо доказать два пункта:
# Допустимость расписания, построенного с помощью задачи <tex> P </tex>, или существование способа его трансформации в допустимое.
+
# Допустимость расписания, построенного с помощью задачи <tex> S' </tex>, или существование способа его трансформации в допустимое без нарушения оптимальности.
# Следствие того, что если мы оптимизируем <tex> S' </tex>, мы также оптимизируем ответ для <tex> S </tex> (обратное в общем случае неверно).
+
# Следствие того, что если мы оптимизируем <tex> S' </tex>, мы также оптимизируем ответ для <tex> S </tex>.
Примечание — если требуется полиномиальное время для решения задачи, требуется, чтобы сведение к другой задаче и трансформация расписания в допустимое также происходили за полиномиальное время.
+
'''Примечание''': если требуется полиномиальное время для решения задачи, сведение к другой задаче и трансформация расписания в допустимое также должны происходить за полиномиальное время.
=== Примеры ===
 
==== 1 | intree | Sum(w_i C_i) ====
 
Предположим, что мы уже умеем решать задачу <tex> S' = 1 \mid outtree \mid \sum w_i C_i </tex>. Сведем нашу задачу <tex> S </tex> к ней следующим образом:
 
* Развернем все ребра, теперь если работа <tex> i </tex> зависела от работы <tex> j </tex>, работа <tex> j </tex> будет зависеть от <tex> i </tex>.
 
* Заменим все стоимости <tex> w_i </tex> на противоположные <tex> w'_i = - w_i</tex>.
 
Утверждается, что решив соответствующую задачу <tex> S' </tex> и развернув полученное расписание, мы получим ответ для текущей задачи.
 
# Полученное расписание будет допустимым, так как расписание для <tex> S' </tex> было допустимым, и в нем никакие две работы не пересекались и не прерывались. Развернув, мы не могли нарушить это свойство. Также из-за того, что мы развернули расписание, мы добились того, что все работы выполняются в правильном порядке (в расписании для <tex> S' </tex> из-за того, что расписание было развернуто, порядок был нарушен для всех работ). Таким образом, получили что расписание — допустимое.
 
# Пусть с помощью задачи <tex> S' </tex> мы получили последовательность работ <tex> 1 \dots n </tex> (не теряя общности, занумеруем их от 1 до n). Распишем по определению значение целевой функции для <tex> S </tex>:
 
#: <tex>\sum -w_i C_i = \sum \limits_{i=1}^n ( -w_i \sum \limits_{j=1}^i p_j ) = \\
 
\sum\limits_{i=1}^n ( w_i \sum\limits_{j=i+1}^n p_j ) - \sum\limits_{i=1}^n w_i \sum \limits_{i=1}^n p_i = \\
 
\sum\limits_{i=1}^n ( w_i \sum\limits_{j=i}^n p_j ) - \sum\limits_{i=1}^n w_i p_i - \sum\limits_{i=1}^n w_i \sum \limits_{i=1}^n p_i </tex>
 
#: Заметим, что первое слагаемое соответствует целевой функции <tex> \sum w_i C_i </tex> для последовательности <tex> n \dots 1 </tex>, а второе и третье слагаемые — константы, зависящие только от начальных данных и не зависящие от перестановки работ. Таким образом, оптимальное
 
значение для <tex> S' </tex> также минимизирует <tex> S </tex>, ч.т.д.
 
==== R || Sum(C_i) ====
 
  
==== O | p_ij=1 | Sum(C_i) ====
+
С помощью этого метода решаются:
 +
* Задачи класса [[Классификация задач|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 ===
==== 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>.
  
==== O | p_ij=1 | C_max ====
+
Построим расписание, подходящее под эту границу: будем по очереди заполнять машины работами в произвольном порядке, и если очередная работа не помещается на текущей машине полностью, перенесем ее выходящую за <tex> C_{max} </tex> часть на следующую машину. Благодаря первому ограничению никакая работа не будет выполняться одновременно на двух станках, а благодаря второму — не останется работы, которую мы не сможем выполнить.
  
 
== Бинарный поиск по ответу ==
 
== Бинарный поиск по ответу ==
=== Примеры ===
+
Этот способ часто подходит для задач, в которых надо минимизировать <tex>C_{max} </tex> (если мы умеем решать соответствующую задачу существования расписания), реже для <tex> \sum w_i U_i </tex>. Важно помнить, что если требуется полиномиальное по <tex> n </tex> решение, оно не должно зависеть от логарифма ответа, но иногда ответ ограничен полиномом от <tex>n</tex>, и мы можем применить этот метод.
==== O | p_ij = 1, d_i | - ====
+
 
 +
Примером решения задач подобным методом служит следующая задача:
 +
[[QpmtnriLmax|<tex> Q \mid pmtn, r_i \mid L_{max} </tex>]]
  
 
== Жадное построение расписания ==
 
== Жадное построение расписания ==
=== Примеры ===
+
Для решения задач теории расписаний часто применяется [[Определение матроида|теория матроидо]]в, а в частности — [[Теорема Радо-Эдмондса (жадный алгоритм)|жадный алгоритм]]: алгоритм решения задач путем выбора локально оптимальных решений на каждом этапе алгоритма.
==== 1 | prec | f_max ====
+
Естественно, далеко не все оптимизационные задачи можно решать жадно — для этого сначала необходимо доказать оптимальность жадного выбора.
 +
 
 +
С помощью этого метода решаются:
 +
* [[Правило Лаулера|<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/>
  
==== 1 | outtree | Sum(w_i C_i) ====
+
== Источники информации ==
 +
* Peter Brucker «Scheduling Algorithms», fifth edition, Springer ISBN 978-3-540-69515-8
  
[[Категория: Дискретная математика и алгоритмы]]
+
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Теория расписаний]]
 
[[Категория: Теория расписаний]]

Текущая версия на 19:31, 4 сентября 2022

Сведение к другой задаче

При сведении текущей задачи теории расписаний [math] S [/math] к какой-то другой [math] S' [/math] (не обязательно задаче теории расписаний) необходимо доказать два пункта:

  1. Допустимость расписания, построенного с помощью задачи [math] S' [/math], или существование способа его трансформации в допустимое без нарушения оптимальности.
  2. Следствие того, что если мы оптимизируем [math] S' [/math], мы также оптимизируем ответ для [math] S [/math].

Примечание: если требуется полиномиальное время для решения задачи, сведение к другой задаче и трансформация расписания в допустимое также должны происходить за полиномиальное время.

С помощью этого метода решаются:

  • Задачи класса Open Shop при условии [math]p_{ij}=1[/math] можно свести к задачам равной длительности на параллельных станках:
    [math] O \mid p_{ij} = 1 \mid \sum w_i C_i [/math]
    [math] O \mid p_{ij} = 1, r_i \mid C_{max} [/math] [1]
  • Задачи класса Flow Shop при условии [math]p_{ij}=1[/math] можно свести к задаче на одном станке:
    [math] F \mid p_{ij} = 1 \mid \sum w_i U_i [/math]
  • Часто в задачах, в которых допускаются прерывания, оптимальный ответ совпадает с соответствующими задачами без прерываний:
    [math] P \mid pmtn \mid \sum w_i C_i [/math] [2]
    [math] F2 \mid pmtn \mid C_{max} [/math]
  • Ряд задач можно свести к задаче поиска максимального потока:
    [math] Q \mid pmtn, r_i\mid L_{max} [/math] [3]
    [math] R \mid \mid \sum C_i [/math]
  • Некоторые задачи сводятся к другим похожим задачам теории расписаний путем преобразования их расписаний:
    [math] 1 \mid intree \mid \sum w_i C_i [/math]

Построение расписания по нижней оценке

Этот метод обычно применим к задачам, в которых целевая функция — [math] C_{max}[/math]. Обычно построение расписания по нижней оценке происходит в два этапа:

  1. Построение некоторого набора нижних ограничений на произвольное расписание для задачи [math] S [/math].
  2. Построение произвольного допустимого расписания, достигающего максимального ограничения из построенного набора.

С помощью этого метода решаются следующие задачи:

Ниже будет рассмотрен частный пример решения задачи подобным образом:

P | pmtn | C_max

Задача:
Имеется [math]m[/math] однородных машин, работающих параллельно, и [math]n[/math] работ, которые могут быть прерваны и продолжены позже. Необходимо минимизировать время выполнения всех работ

Найдем набор ограничений на значение [math] C_{max} [/math] для произвольного допустимого расписания [math] S [/math] :

  1. В допустимом расписании выполнение всех работ не может завершиться раньше одной из них, поэтому [math] C_{max} \geqslant p_i [/math].
  2. Если все станки работали время [math] C_{max} [/math], на них могло выполниться не больше [math] C_{max} \cdot m [/math] работы, то есть [math] \sum\limits_{i=1}^n p_i \leqslant C_{max} \cdot m [/math] и [math] C_{max} \geqslant \dfrac1m \sum\limits_{i=1}^n p_i [/math].

Из этих ограничений следует, что [math] C_{max} = \max {\left( \max\limits_{i=1 \cdots n} p_i,~ \dfrac1m \sum\limits_{i=1}^n p_i \right)} [/math].

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

Бинарный поиск по ответу

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

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

Жадное построение расписания

Для решения задач теории расписаний часто применяется теория матроидов, а в частности — жадный алгоритм: алгоритм решения задач путем выбора локально оптимальных решений на каждом этапе алгоритма. Естественно, далеко не все оптимизационные задачи можно решать жадно — для этого сначала необходимо доказать оптимальность жадного выбора.

С помощью этого метода решаются:

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

Неправильно

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

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

Проблема в этих рассуждениях в том, что ими мы доказываем локальную оптимальность алгоритма в решении [math] S [/math]. Получение же глобального минимума может потребовать нескольких атомарных изменений в расписании, поэтому доказать оптимальность таким образом в общем случае невозможно. Как ближайшую аналогию, можно привести неправильное утверждение для произвольной функции [math] f(\bar x) [/math] — «если все частные производные [math] \dfrac{\partial f}{\partial x_1} \dots \dfrac{\partial f}{\partial x_n} [/math] неотрицательны, то в точке [math] \bar x [/math] наблюдается глобальный минимум».

Правильно

При доказательстве оптимательности применима стратегия аргумент замены (англ. exchange argument). Стратегия заключается в рассмотрении текущего решения [math] S [/math] и оптимального решения [math] O [/math]. Далее предлагается способ модификации [math] O [/math] в [math] O'[/math] так, что:

  1. [math] f(O') \leqslant f(O) [/math], то есть [math] O' [/math] также оптимально.
  2. [math] O' [/math] «более похоже» на [math] S [/math], чем на [math] O [/math].

Если такой способ найден, получаем, что какой-то последовательностью модификаций [math] O \to O_t' \to \dots \to O_1' \to S [/math] получим [math] f(S) \leqslant f(O_1') \leqslant \dots \leqslant f(O_t') \leqslant f(O) [/math], из чего следует оптимальность [math] S [/math].

Отношение «более похоже» должно быть отношением частичного строгого порядка. Часто в качестве него можно выбрать отношение «длина наибольшего общего префикса решения [math] A [/math] и [math] S [/math] меньше наибольшего общего префикса решения [math] B [/math] и [math] S [/math]». Тогда если мы сможем увеличить длину наибольшего общего префикса для оптимального решения, не нарушив оптимальности, мы приблизимся к [math] S [/math]. Можно выбирать и более сложные отношения, например, в доказательстве оптимальности алгоритма [math] P \mid \mid \sum w_i C_i [/math] для решения задачи [math] P \mid pmtn \mid \sum w_i C_i [/math] используется отношение «время последнего прерывания больше или количество прерываний меньше».

См. также.

Примечания

  1. Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 161
  2. Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 121
  3. Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 129-133
  4. Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 108

Источники информации

  • Peter Brucker «Scheduling Algorithms», fifth edition, Springer ISBN 978-3-540-69515-8