1679
правок
Изменения
→Построение расписания по нижней оценке
== Построение расписания по нижней оценке ==
Этим методом обычно применим к задачам, в которых целевая функция — <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 ====
# В допустимом расписании выполнение всех работ не может завершиться раньше одной из них, поэтому <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 ====
# В допустимом расписании на каждом станке надо обработать каждую работу, поэтому <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
== Бинарный поиск по ответу ==
