PpmtnCmax

Задача:

Имеется [math]M[/math] однородных машин, работающих параллельно. Есть [math]n[/math] работ, каждая из которых имеет своё время окончания [math]d_i[/math]. Работа может быть прервана и продолжена позже. Необходимо составить такое расписание, чтобы значение [math]C_{max} = \max\limits_{i=1\ldots n} C_i[/math] было минимальным.

Алгоритм

Рис. 1. Пример построения расписания

Будет строить расписание по нижней оценке.

Мы не сможем выполнить работы быстрее, чем [math]\max\limits_{i} p_i[/math], так как работы на разных станках не могут выполняться в один момент времени. И нам потребуется минимум [math](\sum\limits_{i=1}^n p_i)/m[/math] времени, чтобы выполнить все работы, используя ресурсы только [math]m[/math] станков.

Обозначим нижнюю оценку как [math]LB = \max\{\max\limits_{i} p_i, (\sum\limits_{i=1}^n p_i)/m\} [/math].

Расписание, удовлетворяющее этой оценке может быть построено за [math]O(n)[/math].

Будем выполнять работы на станке в произвольном порядке до тех пор, пока не будет достигнуто время [math]LB[/math]. Тогда оставшаяся часть работы, которая не была закончена, переносится в начало следующего станка. Таким образом, времена выполнения одной работы на разных станках не будут совпадать.

Источники информации

• Peter Brucker. «Scheduling Algorithms» — «Springer», 2006 г. — 108 стр. — ISBN 978-3-540-69515-8

См. также

• Классификация задач
• [math]P \mid pmtn, r_i \mid L_{max}[/math]