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

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

При сведении текущей задачи теории расписаний [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]
• Некоторые задачи класса 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]
  • [math] F2 \mid pmtn \mid C_{max} [/math] (ссылка)
• Некоторые задачи проверки существования расписания сводятся к задаче поиска максимального потока:
  • [math] Q \mid pmtn, r_i\mid L_{max} [/math]
  • [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]
• [math] R \mid pmtn \mid C_{max}[/math]
• [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] 1 \mid prec \mid f_{max} [/math] (Lawler's algorithm)
• [math] 1 \mid outtree \mid \sum w_i C_i [/math] (ссылка)
• [math] 1 \mid p_i = 1 \mid \sum w_i U_i [/math] (Earliest Due Date rule)
• [math] 1 \mid \mid \sum U_i [/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] используется отношение «время последнего прерывания больше или количество прерываний меньше».

См. также.

• Правило Лаулера
• Flow shop
• [math] O \mid p_{ij} = 1 \mid \sum U_i[/math]

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

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