Материал из Викиконспекты
|
|
| Строка 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
