Том 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. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

Статья поступила 4 октября 1993 г.