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

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

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

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

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

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

• Задачи класса Open Shop при условии $p_{ij}=1$ можно свести к задачам равной длительности на параллельных станках:

  $O \mid p_{ij} = 1 \mid \sum w_i C_i$

  $O \mid p_{ij} = 1, r_i \mid C_{max}$

• Задачи класса Flow Shop при условии $p_{ij}=1$ можно свести к задаче на одном станке:

  $F \mid p_{ij} = 1 \mid \sum w_i U_i$

• Часто в задачах, в которых допускаются прерывания, оптимальный ответ совпадает с соответствующими задачами без прерываний:

  $P \mid pmtn \mid \sum w_i C_i$

  $F2 \mid pmtn \mid C_{max}$

• Ряд задач можно свести к задаче поиска максимального потока:

  $Q \mid pmtn, r_i\mid L_{max}$

  $R \mid \mid \sum C_i$

• Некоторые задачи сводятся к другим похожим задачам теории расписаний путем преобразования их расписаний:

  $1 \mid intree \mid \sum w_i C_i$

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

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

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

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

• $P \mid pmtn \mid C_{max}$
• $R \mid pmtn \mid C_{max}$
• $O \mid p_{ij}=1 \mid C_{max}$
• $Q \mid pmtn \mid C_{max}$

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

P | pmtn | C_max

Задача:

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

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

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

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

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

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

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

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

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

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

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

• $1 \mid prec \mid f_{max}$
• $1 \mid outtree \mid \sum w_i C_i$
• $1 \mid p_i = 1 \mid \sum w_i U_i$
• $1 \mid \mid \sum U_i$

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

Неправильно

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

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

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

Правильно

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

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

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

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

См. также.

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

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

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