PpmtnCmax — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{Задача |definition = Имеется <tex>M</tex> однородных машин, работающих параллельно. Есть <tex>n</tex> ра...»)
 
(Удалено содержимое страницы)
 
Строка 1: Строка 1:
{{Задача
 
|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>]]
 
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Теория расписаний]]
 

Текущая версия на 06:10, 8 июня 2016