RpmtnCmax

Материал из Викиконспекты
Версия от 07:12, 8 июня 2016; Веда (обсуждение | вклад) (Новая страница: «{{Задача |definition = Имеется <tex>m</tex> машин, работающих параллельно. Есть <tex>n</tex> работ, причем ...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
Задача:
Имеется [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] [1] за полиномиальное время.

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

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

См. также

Примечания

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