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

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

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

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

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

Примеры

1 | intree | Sum(w_i C_i)

Предположим, что мы уже умеем решать задачу [math] S' = 1 \mid outtree \mid \sum w_i C_i [/math]. Сведем нашу задачу [math] S [/math] к ней следующим образом:

• Развернем все ребра, теперь если работа [math] i [/math] зависела от работы [math] j [/math], работа [math] j [/math] будет зависеть от [math] i [/math].
• Заменим все стоимости [math] w_i [/math] на противоположные [math] w'_i = - w_i[/math].

Утверждается, что решив соответствующую задачу [math] S' [/math] и развернув полученное расписание, мы получим ответ для текущей задачи.

1. Полученное расписание будет допустимым, так как расписание для [math] S' [/math] было допустимым, и в нем никакие две работы не пересекались и не прерывались. Развернув, мы не могли нарушить это свойство. Также из-за того, что мы развернули расписание, мы добились того, что все работы выполняются в правильном порядке (в расписании для [math] S' [/math] из-за того, что расписание было развернуто, порядок был нарушен для всех работ). Таким образом, получили что расписание — допустимое.
2. Пусть с помощью задачи [math] S' [/math] мы получили последовательность работ [math] 1 \dots n [/math] (не теряя общности, занумеруем их от 1 до n). Распишем по определению значение целевой функции для [math] S' [/math]:

   [math]\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 [/math]

   Заметим, что первое слагаемое соответствует целевой функции [math] \sum w_i C_i [/math] для последовательности [math] n \dots 1 [/math], а второе и третье слагаемые — константы, зависящие только от начальных данных и не зависящие от перестановки работ. Таким образом, оптимальное значение для [math] S' [/math] также минимизирует [math] S [/math], ч.т.д.

R || Sum(C_i)

В этой задаче дано [math] n [/math] работ и [math] m [/math] машин, причем для каждой машины длительность выполнения на ней [math]i[/math]-й работы своя и равна [math] p_{ij} [/math].

Рассмотрим произвольное допустимое расписание для этой задачи. Рассмотрим какую-то машину [math] j [/math], пусть на ней выполняется [math]n_j[/math] работ. Тогда вклад этой машины в целевую функцию (не теряя общности, пронумеруем работы на этой машине от [math]1 [/math] до [math]n_j[/math]) рассчитывается как:

[math] \sum\limits_{i=1}^{n_j} (p_ij + \sum\limits_{q=1}^{i-1} p_qj) = n_j p_{1j} + (n_j - 1) p_{2j} + \dots + 2 p_{(n_j-1)j} + p_{n_jj} [/math]

Заметим, что в каждом допустимом расписании перед каждой работой окажется коэффициент [math] k [/math], означающий, что соответствующая работа выпллняется [math] k [/math]-й с конца. Понятно, что в различных расписаниях [math] k [/math] может принимать значения от [math]1[/math] до [math]n[/math].

Сведем задачу к назначению каждой работы [math] i [/math] позиции с конца [math] k [/math] на машине [math] j [/math] с помощью задачи mincost-maxflow. Поместим в левую долю графа работы, в правую долю — пары из машины и коэффициента и проведем соответствующие ребра пропускной способности [math]1[/math] и стоимости [math]k p_{ij}[/math], соответствующие вкладу работы в целевую функцию, если она окажется в позиции [math] k [/math] с конца на машине [math] j [/math]. Проведем из стока в левую долю ребра стоимости [math]0[/math] и пропускной способности [math]1[/math], из правой доли в сток — также ребра стоимости [math] 0 [/math] и пропускной способности [math]1[/math]. Найдем в этой сети максимальный поток минимальной стоимости. Утверждается, что если ребро [math] i \to (j, k) [/math] насыщено потоком, то работа [math] i [/math] в оптимальном расписании должна стоять на машине [math] j [/math] в позиции [math] k [/math] с конца.

1. Целевые функции задачи mincost-maxflow и текущей задачи совпадают, так как у ребер между долями пропускная способность 1, а у дополнительных ребер из истока и в сток нулевая стоимость, и они не могут внести вклад в целевую функцию.
2. Расписание, построенное по вышепредставленному способу действительно будет допустимым.
   1. Благодаря ограничениям на поток, входящий в левую долю, каждая работа будет назначена только один раз.
   2. Благодаря ограничениям на поток, выходящий из правой доли, на каждую позицию будет назначено не более одной работы.
   3. Докажем, что не возникает ситуации такой, что существует такая позиция [math] l [/math], что в этой позиции с конца стоит какая-то работа, а в позиции [math] l - 1 [/math] с конца — нет (это противоречит определению [math]l[/math]-й с конца работы). Такая ситуация означает, что ребро [math] i \to (j, l) [/math] оказалось насышено потоком, а ребро [math]i \to (j, l - 1) [/math] — не насыщено. Но стоимость ребра [math] i \to (j, l - 1) [/math] меньше стоимости ребра [math] i \to (j, l) [/math], поэтому можем переместить поток с ребра [math] i \to (j, l) [/math] на ребро [math] i \to (j, l - 1) [/math], не нарушив свойства потока и улучшив целевую функцию, что противоречит оптимальности ответа для mincost-maxflow. Следовательно, такой позиции не возникнет и расписание будет допустимым.

O | p_ij=1 | Sum(w_i C_i)

Докажем, что оптимальный ответ для [math] S [/math] равен оптимальному ответу к задаче [math]S' = P \mid p_i=m, pmtn \mid \sum w_i C_i [/math], где прерывания позволено делать только в целые моменты времени.

1. Целевые функции задач совпадают, поэтому из оптимальности [math] S' [/math] следует оптимальность [math] S [/math].
2. Покажем, как получить из расписания [math] S' [/math] допустимое расписание для [math]S[/math] (в расписании для [math]S'[/math] допустимость нарушает то, что на одной машине выполняется несколько блоков одной работы):
   1. Построим двудольный граф, в левую долю которого поместим работы, а в правую — возможные моменты времени. Из вершины, соответствующей работе [math] i [/math] будет идти ребро в вершину, соответствующую временному моменту [math] t[/math], если работа [math] i [/math] в расписании для [math] S' [/math] претендует на выполнение в момент времени [math]t[/math].
   2. Раскрасим ребра этого графа в [math]m[/math] цветов, из теории графов известно, что это можно сделать.
   3. Назначим выполнение единичного элемента работы [math]i[/math] в момент времени [math]t[/math] на машине [math]k[/math], если соответствующее ребро раскрашено в цвет [math]k[/math].
   4. После данного преобразования мы не изменим значение целевой функции (так как мы переставляем только элементы работ, выполняющихся в один и тот же момент времени). Также расписание станет допустимым для [math] S [/math], так как по определению реберной раскраски, не будет ни одной работы, два единичных блока которых выполняется на одной машине и во все моменты времени не окажется того, что на одну машину назначено две работы.

Чтобы непосредственно решить эту задачу, воспользуемся теоремой о том, что для задачи [math] P \mid p_i=m, pmtn \mid \sum w_i C_i [/math] существует оптимальное расписание без прерываний. Известно, что для того, чтобы получить оптимальное расписание для такой задачи без прерываний, надо помещать работы по очереди на машины [math]1 \dots m [/math] в порядке убывания весов. Длительности у всех работ совпадают, поэтому расписание будет состоять из [math] \lfloor \frac{n}{m} \rfloor [/math] блоков по [math] m [/math] работ и, возможно, одного неполного блока из [math] n \mod m [/math] работ. Таким образом, аналогично задаче [math] O \mid p_{ij}=1 \mid C_{max}[/math], чтобы получить допустимое расписание, можно не строить раскраску графа, а просто циклически сдвигать последовательности работ внутри каждого блока, что позволяет достичь асимптотики [math] O(m n) [/math].

Метод сведения задачи к задаче на параллельных машинах также работает для некоторых других open-shop задач.

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

Этот метод обычно применим к задачам, в которых целевая функция — [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]

Примеры

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] часть на следующую машину. Благодаря первому ограничению никакая работа не будет выполняться одновременно на двух станках, а благодаря второму — не останется работы, которую мы не сможем выполнить.

O | p_ij=1 | C_max

1. В допустимом расписании на каждом станке надо обработать каждую работу, поэтому [math] T \ge n [/math].
2. В допустимом расписании каждую работу нужно обработать на всех станках, причем ее нельзя обрабатывать на двух станках одновременно, поэтому [math] T \ge m [/math].
3. Тогда [math] T_{min} = \max {(m, n)} [/math]

Оптимальное расписание получается циклическими сдвигами последовательности [math] 1 \dots n [/math] и выглядит следующим образом:

• Для [math] n \lt m [/math]:

        0   1   2   ... n-1 n   n+1 ... m-1 m
 M_1    1   2   3   ... n-1 n   -   ... -   -
 M_2    -   1   2   ... n-2 n-1 n   ... -   -
 .      ... ... ... ... ... ... ... ... ... ...
 M_m-1  -   -   -   ... ... ... ... ... n   -
 M_m    -   -   -   ... ... ... ... ... n-1 n

• Для [math] n \ge m [/math]:

        0     1     2   ... k   k+1 ... n-1 n
 M_1    1     2     3   ... k   k+1 ... n-1 n
 M_2    n     1     2   ... k-1 k   ... n-2 n-1
 .      ...   ...   ... ... ... ... ... ... ...
 .      ...   ...   ... ... ... ... ... ... ...
 M_m    n-m+2 n-m+3 ... ... ... ... ... n-m n-m+1

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

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

Примеры

O | p_ij = 1| Sum(U_i)

Перенумеруем работы по возрастанию их дедлайнов, то есть [math] d_1 \le d_2 \le \dots d_n [/math].

Утверждение:

Если мы можем выполнить [math] k [/math] каких-то работ, мы можем выполнить [math] k [/math] последних работ.

[math]\triangleright[/math]

Действительно, если в допустимом расписании все периоды выполнения [math] t_{iq} [/math] работы [math] i [/math] заменить на периоды выполнения работы [math] j \gt i [/math], оно останется допустимым, так как [math] t_{iq} \le d_i \le d_j [/math].

[math]\triangleleft[/math]

Таким образом, будем брать последние [math] k [/math] работ и пытаться составить из них допустимое расписание (для этого известен полиномиальный алгоритм за [math] O(mn) [/math]). Получили решение за [math] O(mn\log n ) [/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 | prec | f_max

Дано множество работ [math] J [/math] размера [math] n [/math], для которых заданы отношения предшествования, нужно минимизировать [math] f_{max} = \max\limits_i f_i(C_i) [/math], где [math] f_i[/math] — монотонно неубывают по времени завершения работы [math] i [/math].

Приведем алгоритм решения и докажем его оптимальность:

1. Пусть [math] U \subseteq J [/math] — множество еще не назначенных работ. Пусть [math] p(U) = \sum\limits_{i \in U} p_i [/math].
2. Назначим работу [math] j \in U [/math], у которой нет потомков в [math] U [/math] и с минимальным значением [math] f_j(p(U)) [/math] последней работой в [math] U [/math].

Теорема:

Предложенный алгоритм оптимален.

Доказательство:

[math]\triangleright[/math]

Не теряя общности, пронумеруем работы в расписании, построенном нашим алгоритмом, от [math] 1 [/math] до [math] n [/math]. Пусть [math] \pi(1) \dots \pi(n) [/math] — оптимальная последовательность работ такая, что наибольший общий суффикс их расписаний — максимален (пусть они впервые различаются в позиции [math] r [/math]). Получили, следующую ситуацию: pi: ... ... r-1 k .... j r r+1 ... n Докажем, что можно привести это расписание к оптимальному расписанию с большим общим суффиксом. Заметим, что если выполнить работу r-1 прямо перед r, расписание все еще будет допустимым (несмотря на еще не доказанную оптимальность, наш алгоритм строит только допустимые расписания, а в построенном нами расписании r-1 стояло прямо перед r). По оптимальному расписанию j выполняется непосредственно перед r. Таким образом, у работ j и r нет ни одного потомка в можестве работ 1, 2.. r-2, r-1. По построенной нашим алгоритмом последовательности 1..n мы получаем, что [math] f_{r-1}(\sum\limits_{i}^{r-1} p_i) \le f_j(\sum\limits_{i}^{r-1}) [/math] (иначе мы бы поставили последней на тот момент работу j, а не r). Сдвинем в последовательности [math] \pi [/math] работы k .. j влево на одну позицию, а работу r-1 поместим перед r. Так как после сдвига влево, [math]f_k \dots f_j [/math] не могли увеличиться, максимум так же не мог увеличиться. Следовательно, оптимальная последовательность [math] \pi [/math] имела не самый длинный общий суффикс, что противоречит её выбору.

[math]\triangleleft[/math]