14
правок
Изменения
Новая страница: «{{Задача |definition = Имеется <tex>M</tex> однородных машин, работающих параллельно. Есть <tex>n</tex> ра...»
{{Задача
|definition =
Имеется <tex>M</tex> однородных машин, работающих параллельно. Есть <tex>n</tex> работ, каждая из которых имеет своё время окончания <tex>d_i</tex>. Работа может быть прервана и продолжена позже.
Необходимо составить такое расписание, чтобы значение <tex>C_{max} = \max\limits_{i=1\ldots n} C_i</tex> было минимальным.}}
==Алгоритм==
[[Файл:exmpl1.png|400px|thumb|right|Рис. 1. Пример построения расписания]]
Будет строить расписание по нижней оценке.
Мы не сможем выполнить работы быстрее, чем <tex>\max\limits_{i} p_i</tex>, так как работы на разных станках не могут выполняться в один момент времени. И нам потребуется минимум <tex>(\sum\limits_{i=1}^n p_i)/m</tex> времени, чтобы выполнить все работы, используя ресурсы только <tex>m</tex> станков.
Обозначим нижнюю оценку как <tex>LB = \max\{\max\limits_{i} p_i, (\sum\limits_{i=1}^n p_i)/m\} </tex>.
Расписание, удовлетворяющее этой оценке может быть построено за <tex>O(n)</tex>.
Будем выполнять работы на станке в произвольном порядке до тех пор, пока не будет достигнуто время <tex>LB</tex>. Тогда оставшаяся часть работы, которая не была закончена, переносится в начало следующего станка. Таким образом, времена выполнения одной работы на разных станках не будут совпадать.
==Источники информации==
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 108 стр. {{---}} ISBN 978-3-540-69515-8
== См. также ==
* [[Классификация задач]]
* [[PpmtnriLmax|<tex>P \mid pmtn, r_i \mid L_{max}</tex>]]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]
|definition =
Имеется <tex>M</tex> однородных машин, работающих параллельно. Есть <tex>n</tex> работ, каждая из которых имеет своё время окончания <tex>d_i</tex>. Работа может быть прервана и продолжена позже.
Необходимо составить такое расписание, чтобы значение <tex>C_{max} = \max\limits_{i=1\ldots n} C_i</tex> было минимальным.}}
==Алгоритм==
[[Файл:exmpl1.png|400px|thumb|right|Рис. 1. Пример построения расписания]]
Будет строить расписание по нижней оценке.
Мы не сможем выполнить работы быстрее, чем <tex>\max\limits_{i} p_i</tex>, так как работы на разных станках не могут выполняться в один момент времени. И нам потребуется минимум <tex>(\sum\limits_{i=1}^n p_i)/m</tex> времени, чтобы выполнить все работы, используя ресурсы только <tex>m</tex> станков.
Обозначим нижнюю оценку как <tex>LB = \max\{\max\limits_{i} p_i, (\sum\limits_{i=1}^n p_i)/m\} </tex>.
Расписание, удовлетворяющее этой оценке может быть построено за <tex>O(n)</tex>.
Будем выполнять работы на станке в произвольном порядке до тех пор, пока не будет достигнуто время <tex>LB</tex>. Тогда оставшаяся часть работы, которая не была закончена, переносится в начало следующего станка. Таким образом, времена выполнения одной работы на разных станках не будут совпадать.
==Источники информации==
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 108 стр. {{---}} ISBN 978-3-540-69515-8
== См. также ==
* [[Классификация задач]]
* [[PpmtnriLmax|<tex>P \mid pmtn, r_i \mid L_{max}</tex>]]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]
