RpmtnCmax

Задача:

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

Алгоритм

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

Вычислим для каждой работы время [math]t_{ij}[/math], которое работа [math]i[/math] будет выполняться на [math]j[/math]-ом станке в оптимальном расписании.

Пусть [math]t_{ij}/p_{ij}[/math] - часть времени, которое работа [math]i[/math] будет выполняться на [math]j[/math]-ом станке. Тогда [math] \sum\limits_{j=1}^m t_{ij}/p_{ij} = 1[/math] верно, если работа завершена.

Теперь оптимальное расписание должно удовлетворять следующим условиям:

1. [math] \sum\limits_{j=1}^m t_{ij}/p_{ij} = 1, \quad i = 1,\ldots, n[/math]
2. [math] \sum\limits_{j=1}^m t_{ij} \leqslant C_{max}, \quad i = 1,\ldots, n[/math]
3. [math] \sum\limits_{i=1}^n t_{ij} \leqslant C_{max}, \quad j = 1,\ldots, m[/math]
4. [math] t_{ij} \geqslant 0, \quad i = 1,\ldots, n; j = 1,\ldots, m[/math]

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

Можем получить ответ на задачу за [math]O(n)[/math]. Расписание, удовлетворяющее этой оценке строится аналогично [math]O \mid pmtn \mid C_{max}[/math] за полиномиальное время.

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

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

См. также

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