24
правки
Изменения
Фиксы
С помощью этого метода решаются:
* Некоторые задачи Задачи класса [[Классификация задач|Open Shop ]] при условии <tex>p_{ij}=1</tex> сводятся можно свести к задачам равной длительности на параллельных станках.:
*:[[Opij1Sumwc|<tex> O \mid p_{ij} = 1 \mid \sum w_i C_i </tex>]]
*:<tex> O \mid p_{ij} = 1, r_i \mid C_{max} </tex> <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 161</ref>
* Некоторые задачи Задачи класса [[Классификация задач|Flow Shop ]] при условии <tex>p_{ij}=1</tex> сводятся можно свести к задаче на одном станке. :
*:[[Fpij1sumwu|<tex> F \mid p_{ij} = 1 \mid \sum w_i U_i </tex>]]
* Часто в задачах, в которых допускаются прерывания, оптимальный ответ совпадает с соответствующими задачами без прерываний:
*:<tex> P \mid pmtn \mid \sum w_i C_i </tex> <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 121</ref>
*:[[Flow shop|<tex> F2 \mid pmtn \mid C_{max} </tex>]]
* Некоторые задачи проверки существования расписания сводятся Ряд задач можно свести к задаче поиска максимального потока:
*:<tex> Q \mid pmtn, r_i\mid L_{max} </tex> <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 129-133</ref>
*:[[RSumCi|<tex> R \mid \mid \sum C_i </tex>]]
* [[QpmtnCmax|<tex> Q \mid pmtn \mid C_{max}</tex>]]
Ниже будет рассмотрен частный пример решения задачи подобным образом:
=== P | pmtn | C_max ===
{{Задача
|definition = Имеется <tex>m</tex> однородных машин, работающих параллельно, и <tex>n</tex> работ, которые могут быть прерваны и продолжены позже. Необходимо минимизировать время выполнения всех работ
}}
Найдем набор ограничений на значение <tex> C_{max} </tex> для произвольного допустимого расписания <tex> S </tex> :
# В допустимом расписании выполнение всех работ не может завершиться раньше одной из них, поэтому <tex> C_{max} \geqslant p_i </tex>.
# Если все станки работали время <tex> C_{max} </tex>, на них могло выполниться не больше <tex> C_{max} \cdot m </tex> работы, то есть <tex> \sum\limits_i limits_{i=1}^n p_i \leqslant C_{max} \cdot m </tex> и <tex> C_{max} \geqslant \dfrac1m \sum\limits_i limits_{i=1}^n p_i </tex>.Из этих ограничений следует, что <tex> C_{max} = \max {\left( \max\limits_i limits_{i=1 \hdots n} p_i; ,~ \dfrac1m \sum\limits_i limits_{i=1}^n p_i \right)} </tex>.
Построим расписание, подходящее под эту границу: будем по очереди заполнять машины работами в произвольном порядке, и если очередная работа не помещается на текущей машине полностью, перенесем ее выходящую за <tex> C_{max} </tex> часть на следующую машину. Благодаря первому ограничению никакая работа не будет выполняться одновременно на двух станках, а благодаря второму — не останется работы, которую мы не сможем выполнить.
== Жадное построение расписания ==
Естественно, далеко не все оптимизационные задачи можно решать жадно — для этого сначала необходимо доказать оптимальность жадного выбора.
