Изменения
Нет описания правки
С помощью этого метода решаются следующие задачи:
* <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>]]
== Жадное построение расписания ==
Для решения задач теории расписаний часто применяется [[Определение матроида|теория матроидо]]в, а в частности — [[Теорема Радо-Эдмондса (жадный алгоритм)|жадный алгоритм]] — : алгоритм решения задач путем выбора локально оптимальных решений на каждом этапе алгоритма.
Естественно, далеко не все оптимизационные задачи можно решать жадно — для этого сначала необходимо доказать оптимальность жадного выбора.
