Область оптимальности перестановки обслуживания на одном приборе требований с неопределенными длительностями

Исследуется задача оптимизации расписания обслуживания заданного множества требований на одном приборе. При составлении расписания для каждого требования известны нижняя граница и верхняя граница допустимой длительности его обслуживания. В качестве критерия оптимальности расписания рассматривается минимизация суммарного времени обслуживания заданного множества требований. Исследованы свойства области оптимальности перестановки обслуживания требований. Разработаны полиномиальные алгоритмы построения области оптимальности перестановки обслуживания требований и вычисления объема области оптимальности. Определены условия существования пустой области оптимальности для перестановки обслуживания требований. Установлен критерий существования перестановки обслуживания требований с максимально возможным объемом области оптимальности.