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

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

При сведении текущей задачи теории расписаний [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(\log n \cdot T_{exists}(n)) [/math], где [math] T_{exists} [/math] — время решения задачи [math] O \mid p_{ij}=1, d_i \mid - [/math].