Изменения
Нет описания правки
<tex dpi = "200" >R \mid pmtn \mid C_{max}</tex>
{{Задача
|definition =
Вычислим для каждой работы время <tex>t_{ij}</tex>, которое работа <tex>i</tex> будет выполняться на <tex>j</tex>-ом станке в оптимальном расписании.
Пусть <tex>t_{ij}/p_{ij}</tex> {{- --}} часть времени, которое работа <tex>i</tex> будет выполняться на <tex>j</tex>-ом станке. Тогда <tex> \sum\limits_{j=1}^m t_{ij}/p_{ij} = 1</tex> верно, если работа завершена.
Теперь оптимальное расписание должно удовлетворять следующим условиям:
Можем получить ответ на задачу за <tex>O(n)</tex>. Расписание, удовлетворяющее этой оценке строится аналогично <tex>O \mid pmtn \mid C_{max}</tex> <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 15-17</ref> за полиномиальное время.
== См. также ==
<references/>
==Источники информации==* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 137-139 стр. {{---}} ISBN 978-3-540-69515-8 [[Категория: Дискретная математика Алгоритмы и алгоритмыструктуры данных]]
[[Категория: Теория расписаний]]
