RpmtnCmax — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показаны 2 промежуточные версии 2 участников)
Строка 13: Строка 13:
 
Вычислим для каждой работы время <tex>t_{ij}</tex>, которое работа <tex>i</tex> будет выполняться на <tex>j</tex>-ом станке в оптимальном расписании.
 
Вычислим для каждой работы время <tex>t_{ij}</tex>, которое работа <tex>i</tex> будет выполняться на <tex>j</tex>-ом станке в оптимальном расписании.
  
Пусть <tex>t_{ij}/p_{ij}</tex> {{---}} часть времени, которое  работа <tex>i</tex> будет выполняться на <tex>j</tex>-ом станке. Тогда <tex> \sum\limits_{j=1}^m t_{ij}/p_{ij} = 1</tex> верно, если работа завершена.
+
Пусть <tex>\dfrac {t_{ij} } {p_{ij}} </tex> {{---}} часть времени, которое  работа <tex>i</tex> будет выполняться на <tex>j</tex>-ом станке. Тогда <tex> \sum\limits_{j=1}^m \dfrac {t_{ij} } {p_{ij}} = 1</tex> верно, если работа завершена.
  
 
Теперь оптимальное расписание должно удовлетворять следующим условиям:
 
Теперь оптимальное расписание должно удовлетворять следующим условиям:
# <tex> \sum\limits_{j=1}^m t_{ij}/p_{ij} = 1, \quad i = 1,\ldots, n</tex>
+
# <tex> \sum\limits_{j=1}^m \dfrac {t_{ij} } {p_{ij}} = 1, \quad i = 1,\ldots, n</tex>
 
# <tex> \sum\limits_{j=1}^m t_{ij} \leqslant C_{max},  \quad i = 1,\ldots, n</tex>
 
# <tex> \sum\limits_{j=1}^m t_{ij} \leqslant C_{max},  \quad i = 1,\ldots, n</tex>
 
# <tex> \sum\limits_{i=1}^n t_{ij} \leqslant C_{max},  \quad j = 1,\ldots, m</tex>
 
# <tex> \sum\limits_{i=1}^n t_{ij} \leqslant C_{max},  \quad j = 1,\ldots, m</tex>

Текущая версия на 19:40, 4 сентября 2022

[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