Изменения
→P | pmtn | C_max
С помощью этого метода решаются следующие задачи:
* <tex> P \mid pmtn \mid C_{max}</tex> <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 108</ref>
* [[RpmtnCmax|<tex> R \mid pmtn \mid C_{max}</tex> <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 137-139</ref>]]
* [[Opij1Cmax|<tex> O \mid p_{ij}=1 \mid C_{max}</tex>]]
* [[QpmtnCmax|<tex> Q \mid pmtn \mid C_{max}</tex>]]
# В допустимом расписании выполнение всех работ не может завершиться раньше одной из них, поэтому <tex> C_{max} \geqslant p_i </tex>.
# Если все станки работали время <tex> C_{max} </tex>, на них могло выполниться не больше <tex> C_{max} \cdot m </tex> работы, то есть <tex> \sum\limits_{i=1}^n p_i \leqslant C_{max} \cdot m </tex> и <tex> C_{max} \geqslant \dfrac1m \sum\limits_{i=1}^n p_i </tex>.
Из этих ограничений следует, что <tex> C_{max} = \max {\left( \max\limits_{i=1 \hdots cdots n} p_i,~ \dfrac1m \sum\limits_{i=1}^n p_i \right)} </tex>.
Построим расписание, подходящее под эту границу: будем по очереди заполнять машины работами в произвольном порядке, и если очередная работа не помещается на текущей машине полностью, перенесем ее выходящую за <tex> C_{max} </tex> часть на следующую машину. Благодаря первому ограничению никакая работа не будет выполняться одновременно на двух станках, а благодаря второму — не останется работы, которую мы не сможем выполнить.
== Жадное построение расписания ==
Для решения задач теории расписаний часто применяется [[Определение матроида|теория матроидо]]в, а в частности — [[Теорема Радо-Эдмондса (жадный алгоритм)|жадный алгоритм]] : алгоритм решения задач путем выбора локально оптимальных решений на каждом этапе алгоритма.
Естественно, далеко не все оптимизационные задачи можно решать жадно — для этого сначала необходимо доказать оптимальность жадного выбора.
