Изменения
Нет описания правки
<tex dpi = "200" >R \mid pmtn \mid C_{max}</tex>
{{Задача
|definition =
Вычислим для каждой работы время <tex>t_{ij}</tex>, которое работа <tex>i</tex> будет выполняться на <tex>j</tex>-ом станке в оптимальном расписании.
Пусть <tex>\dfrac {t_{ij}/} {p_{ij}}</tex> {{--- }} часть времени, которое работа <tex>i</tex> будет выполняться на <tex>j</tex>-ом станке. Тогда <tex> \sum\limits_{j=1}^m \dfrac {t_{ij}/} {p_{ij}} = 1</tex> верно, если работа завершена.
Теперь оптимальное расписание должно удовлетворять следующим условиям:
# <tex> \sum\limits_{j=1}^m \dfrac {t_{ij}/} {p_{ij}} = 1, \quad i = 1,\ldots, n</tex>
# <tex> \sum\limits_{j=1}^m t_{ij} \leqslant C_{max}, \quad i = 1,\ldots, n</tex>
# <tex> \sum\limits_{i=1}^n t_{ij} \leqslant C_{max}, \quad j = 1,\ldots, m</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 [[Категория: Дискретная математика Алгоритмы и алгоритмыструктуры данных]]
[[Категория: Теория расписаний]]
