Эффективное построение расписаний в системах открытого типа

Показано, что для задачи 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