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

Материал из Викиконспекты
Версия от 12:31, 6 июня 2016; Qradimir (обсуждение | вклад) (Выделены задачи в конспекты, добавлены ссылки, разделы в конце конспекта)
Перейти к: навигация, поиск

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

При сведении текущей задачи теории расписаний [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]. Построим какой-то набор нижних ограничений на произвольное расписание для задачи [math] S [/math] и возьмем из них максимальное. Затем построим произвольное допустимое расписание, достигающее этой оценки.

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

  • [math] P \mid pmtn \mid C_{max}[/math] [4]
  • [math] R \mid pmtn \mid C_{max}[/math] [5]
  • [math] O \mid p_{ij}=1 \mid C_{max}[/math] (ссылка)
  • [math] Q \mid pmtn \mid C_{max}[/math] (ссылка)

P | pmtn | C_max

  1. В допустимом расписании выполнение всех работ не может завершиться раньше одной из них, поэтому [math] T \ge p_i [/math].
  2. Если все станки работали время [math] T [/math], на них могло выполниться не больше [math] Tm [/math] работы, то есть [math] \sum\limits_i p_i \le Tm [/math] и [math] T \ge \frac1m \sum\limits_i p_i [/math].
  3. Тогда [math] T_{min} = \max {(\max\limits_i p_i, \frac1m \sum\limits_i p_i)} [/math].

Построим расписание, подходящее под эту границу: будем по очереди заполнять машины работами в произвольном порядке, и если очередная работа не помещается на текущей машине полностью, перенесем ее выходящую за [math] T_{min} [/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) \le f(S') [/math]. Тогда решение [math] S [/math] — оптимально.

Проблема в этих рассуждениях в том, что ими мы доказываем локальную оптимальность алгоритма в решении [math] S [/math]. Получение же глобального минимума может потребовать нескольких атомарных изменений в расписании, поэтому доказать оптимальность таким образом в общем случае невозможно. Как ближайшую аналогию, можно привести неправильное утверждение для произвольной функции [math] f(\bar x) [/math] — «если все частные производные [math] \frac{\partial f}{\partial x_1} \dots \frac{\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') \le 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) \le f(O_1') \le \dots \le f(O_t') \le 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
  5. ↑ Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 137-139

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

  • Peter Brucker «Scheduling Algorithms», fifth edition, Springer ISBN 978-3-540-69515-8
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Методы_решения_задач_теории_расписаний&oldid=54700»