RpmtnCmax

Материал из Викиконспекты
Перейти к: навигация, поиск

[math]R \mid pmtn \mid C_{max}[/math]


Задача:
Имеется [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]\dfrac {t_{ij} } {p_{ij}} [/math] — часть времени, которое работа [math]i[/math] будет выполняться на [math]j[/math]-ом станке. Тогда [math] \sum\limits_{j=1}^m \dfrac {t_{ij} } {p_{ij}} = 1[/math] верно, если работа завершена.

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

  1. [math] \sum\limits_{j=1}^m \dfrac {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] [1] за полиномиальное время.

См. также

Примечания

  1. Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 15-17

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

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