Задача диспетчеризации: анализ вычислительной сложности и полиномиально разрешимые подклассы

Рассматривается задача составления оптимального расписания обслуживания конечного детерминированного потока заявок одним прибором по критерию минимума суммы линейных функций индивидуальных штрафов по заявкам. Для вводимых иерархий частных классов рассматриваемой массовой задачи устанавливаются границы возникновения NP-трудности. Показано, что наложение некоторых естественных с точки зрения приложений ограничений на класс моделей или на класс управлений позволяет построить основанные на рекуррентных соотношениях динамического программирования полиномиальные алгоритмы синтеза оптимальных расписаний.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, грант 93–013–16253.