Методы решения задач теории расписаний — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Построение расписания по нижней оценке)
Строка 24: Строка 24:
  
 
== Построение расписания по нижней оценке ==
 
== Построение расписания по нижней оценке ==
 +
Этим методом обычно применим к задачам, в которых целевая функция — <tex> C_{max}</tex>. Построим какой-то набор нижних ограничений на произвольное расписание для задачи <tex> S </tex> и возьмем из них максимальное. Затем построим произвольное допустимое расписание, достигающее этой оценки.
 +
 +
С помощью этого метода решаются:
 +
* <tex> P \mid pmtn \mid C_{max}</tex>
 +
* <tex> R \mid pmtn \mid C_{max}</tex>
 +
* <tex> O \mid p_{ij}=1 \mid C_{max}</tex>
 +
 
=== Примеры ===
 
=== Примеры ===
 
==== P | pmtn | C_max ====
 
==== P | pmtn | C_max ====
 +
# В допустимом расписании выполнение всех работ не может завершиться раньше одной из них, поэтому <tex> T \ge p_i </tex>.
 +
# Если все станки работали время <tex> T </tex>, на них могло выполниться не больше <tex> Tm </tex> работы, то есть <tex> \sum\limits_i p_i \le Tm </tex> и <tex> T \ge \frac1m \sum\limits_i p_i </tex>.
 +
# Тогда <tex> T_{min} = \max {(\max\limits_i p_i, \frac1m \sum\limits_i p_i)} </tex>.
 +
Построим расписание, подходящее под эту границу: будем по очереди заполнять машины работами в произвольном порядке, и если очередная работа не помещается на текущей машине полностью, перенесем ее выходящую за <tex> T_{min} </tex> часть на следующую машину. Благодаря первому ограничению никакая работа не будет выполняться одновременно на двух станках, а благодаря второму — не останется работы, которую мы не сможем выполнить.
  
 
==== O | p_ij=1 | C_max ====
 
==== O | p_ij=1 | C_max ====
 +
# В допустимом расписании на каждом станке надо обработать каждую работу, поэтому <tex> T \ge n </tex>.
 +
# В допустимом расписании каждую работу нужно обработать на всех станках, причем ее нельзя обрабатывать на двух станках одновременно, поэтому <tex> T \ge m </tex>.
 +
# Тогда <tex> T_{min} = \max {(m, n)} </tex>
 +
Оптимальное расписание получается циклическими сдвигами последовательности <tex> 1 \dots n </tex> и выглядит следующим образом:
 +
* Для <tex> n < m </tex>:
 +
        '''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
 +
* Для <tex> n \ge m </tex>:
 +
        '''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
  
 
== Бинарный поиск по ответу ==
 
== Бинарный поиск по ответу ==

Версия 15:22, 26 апреля 2012

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

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

  1. Допустимость расписания, построенного с помощью задачи [math] P [/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)

O | p_ij=1 | Sum(C_i)

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

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

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

Примеры

O | p_ij = 1, d_i | -

Жадное построение расписания

Примеры

1 | prec | f_max

1 | outtree | Sum(w_i C_i)