Том 1, номер 1, 1994 г., Стр. 20-42
УДК 519.854.2
С. В. Севастьянов
Эффективное построение расписаний в системах открытого типа
Аннотация:
Показано, что для задачи open shop с $m$ машинами и $n$ работами оптимальное
расписание строится полиномиальным от $m$ и $n$ алгоритмом, если нагрузка одной из
машин превосходит нагрузку на остальных машинах на заданную величину “доминирования”. Описывается приближенный алгоритм трудоемкости $O(nm^2)$, который
для любой функции $\eta(m)$ и любого входа задачи open shop, удовлетворяющего условию $M\ge\eta(m)K$ (где $M$ – максимальная нагрузка машины, $K$ – максимальная длительность операции), позволяет находить расписание с абсолютной оценкой точности, зависящей от функции $\eta(m)$ и не зависящей от числа работ. В частности, при $M\ge(7m-6)K$ длина расписания не превосходит величины $m+(m-1)K/3$, что улучшает известную оценку длины любого жадного расписания.
Библиогр. 7.
Севастьянов С. В. 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
Статья поступила 4 октября 1993 г.
|