14
правок
Изменения
Новая страница: «{{Задача |definition = Имеется <tex>m</tex> машин, работающих параллельно. Есть <tex>n</tex> работ, причем ...»
{{Задача
|definition =
Имеется <tex>m</tex> машин, работающих параллельно. Есть <tex>n</tex> работ, причем для каждого станка длительность выполнения на нем <tex>i</tex>-й работы составляет <tex> p_{ij} </tex>. Работа может быть прервана и продолжена позже.
Необходимо составить такое расписание, чтобы значение <tex>C_{max} = \max\limits_{i=1\ldots n} C_i</tex> было минимальным.}}
==Алгоритм==
Будет строить расписание по нижней оценке.
Вычислим для каждой работы время <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> \sum\limits_{j=1}^m 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> t_{ij} \geqslant 0, \quad i = 1,\ldots, n; j = 1,\ldots, m</tex>
Обозначим нижнюю оценку как <tex>LB = \max\{\max\limits_{i=1}^n \sum\limits_{j=1}^m t_{ij}, \sum\limits_{i=1}^n t_{ij}\} </tex>.
Можем получить ответ на задачу за <tex>O(n)</tex>. Расписание, удовлетворяющее этой оценке строится аналогично <tex>O \mid pmtn \mid C_{max}</tex> <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 15-17</ref> за полиномиальное время.
==Источники информации==
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 108 стр. {{---}} ISBN 978-3-540-69515-8
== См. также ==
* [[Классификация задач]]
* [[PpmtnriLmax|<tex>P \mid pmtn, r_i \mid L_{max}</tex>]]
== Примечания ==
<references/>
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]
|definition =
Имеется <tex>m</tex> машин, работающих параллельно. Есть <tex>n</tex> работ, причем для каждого станка длительность выполнения на нем <tex>i</tex>-й работы составляет <tex> p_{ij} </tex>. Работа может быть прервана и продолжена позже.
Необходимо составить такое расписание, чтобы значение <tex>C_{max} = \max\limits_{i=1\ldots n} C_i</tex> было минимальным.}}
==Алгоритм==
Будет строить расписание по нижней оценке.
Вычислим для каждой работы время <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> \sum\limits_{j=1}^m 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> t_{ij} \geqslant 0, \quad i = 1,\ldots, n; j = 1,\ldots, m</tex>
Обозначим нижнюю оценку как <tex>LB = \max\{\max\limits_{i=1}^n \sum\limits_{j=1}^m t_{ij}, \sum\limits_{i=1}^n t_{ij}\} </tex>.
Можем получить ответ на задачу за <tex>O(n)</tex>. Расписание, удовлетворяющее этой оценке строится аналогично <tex>O \mid pmtn \mid C_{max}</tex> <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 15-17</ref> за полиномиальное время.
==Источники информации==
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 108 стр. {{---}} ISBN 978-3-540-69515-8
== См. также ==
* [[Классификация задач]]
* [[PpmtnriLmax|<tex>P \mid pmtn, r_i \mid L_{max}</tex>]]
== Примечания ==
<references/>
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]
