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

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

При сведении текущей задачи теории расписаний [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]. Обычно построение расписания по нижней оценке происходит в два этапа:

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

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

• [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

Задача:

Имеется [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 \hdots 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] 1 \mid prec \mid f_{max} [/math]
• [math] 1 \mid outtree \mid \sum w_i C_i [/math]
• [math] 1 \mid p_i = 1 \mid \sum w_i U_i [/math]
• [math] 1 \mid \mid \sum U_i [/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] используется отношение «время последнего прерывания больше или количество прерываний меньше».

См. также.

• Правило Лаулера
• 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