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

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

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

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

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

Примеры

1 | intree | Sum(w_i C_i)

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

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

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

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

   $\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$

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

значение для $S'$ также минимизирует $S$, ч.т.д.

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

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

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

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

Примеры

P | pmtn | C_max

1. В допустимом расписании выполнение всех работ не может завершиться раньше одной из них, поэтому $T \ge p_i$.
2. Если все станки работали время $T$, на них могло выполниться не больше $Tm$ работы, то есть $\sum\limits_i p_i \le Tm$ и $T \ge \frac1m \sum\limits_i p_i$.
3. Тогда $T_{min} = \max {(\max\limits_i p_i, \frac1m \sum\limits_i p_i)}$.

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

O | p_ij=1 | C_max

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

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

• Для $n \lt m$:

        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

• Для $n \ge m$:

        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

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

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

Примеры

O | p_ij = 1| Sum(U_i)

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

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

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

$\triangleright$

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

$\triangleleft$

Таким образом, будем брать последние $k$ работ и пытаться составить из них допустимое расписание (для этого известен полиномиальный алгоритм). Получили решение за $O(\log n \cdot T_{exists}(n))$, где $T_{exists}$ — время решения задачи $O \mid p_{ij}=1, d_i \mid -$.