Сотрудники лаборатории - Черных Илья Дмитриевич


Критические примеры для цеховых задач теории расписаний.

Для лучшего отображения формул на этой и других страницах сайта рекомендуется установить шрифты Computer Modern, которые используются в TeX-е. См, например, http://www.math.union.edu/~dpvc/jsmath/download/jsMath-fonts.html.

Для цеховых задач теории расписаний c m машинами и n работами справедлива следующая нижняя оценка длины расписания:
C^*_{\max}\geq\bar C\doteq\{\ell_{\max},d_{\max}\},
где \ell_{\max}\doteq\max\limits_i\sum\limits_{j=1}^np_{ji} — максимальная машинная нагрузка, а d_{\max}\doteq\max\limits_j\sum\limits_{i=1}^mp_{ji} — максимальная длина работы. Представляет интерес следующий вопрос: во сколько раз оптимум задачи может превышать нижнюю оценку \bar C в наихудшем (критическом) случае? На каких наихудших (критических) примерах это максимальное отношение достигается?

Предположим, что все входы задач отнормированы таким образом, что \bar C(I)=1. (Мы пренебрегаем тривиальными входами, в которых все операции имеют нулевую длительность.) Класс таких нормированных входов для задачи с m машинами будем обозначать через {\cal I}_m.

В этом разделе рассмотрим критические примеры для задач Open Shop, Flow Shop и Open Shop с маршрутизацией машин.

Open Shop

Для задачи Open Shop рассмотрим следующую функцию:
\rho(m)\doteq\sup\limits_{I\in{\cal I}_m}\frac{C^*_{\max}(I)}{\bar C(I)}=\sup\limits_{I\in{\cal I}_m}C^*_{\max}(I).
Для каждого фиксированного числа машин m нас интересует критический пример I_m^{\mathrm{OS}}, на котором достигается супремум \rho(m).

Flow Shop

Open Shop с маршрутизацией




Страница обновлена 31.03.2013.

Перейти к главной странице сотрудника