RpmtnCmax

$R \mid pmtn \mid C_{max}$

Задача:

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

Алгоритм

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

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

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

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

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

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

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

См. также

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

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

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