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

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

При сведении текущей задачи теории расписаний [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] i [/math] на какую-то позицию [math] k [/math] на машине [math] j [/math] Сведем задачу к задаче mincost-maxflow. Поместим в левую долю графа работы, в правую долю — пары из машины и позиции работы и проведем соответствующие ребра пропускной способности [math]1[/math] и стоимости [math]\frac{p_{i}}{v_{ij}}[/math], соответствующие времени выполнения работы [math]i[/math] на машине [math]j[/math]. Проведем из стока в левую долю ребра стоимости [math]0[/math] и пропускной способности [math]1[/math], из правой доли в сток — ребра пропускной способности [math]n[/math] и стоимости [math] 0 [/math]. Найдем в этой сети максимальный поток минимальной стоимости,

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].