Многогранники устойчивости оптимальной перестановки обслуживания требований

Рассматривается задача минимизации суммы взвешенных моментов завершения обслуживания $n$ требований одним прибором при условии, что длительность обслуживания требования может принимать любое вещественное значение из заданного числового отрезка. Разработан алгоритм сложности $O(n)$ для построения многогранника (параллелепипеда) оптимальности перестановки обслуживания $n$ требований, который содержится в области устойчивости той же перестановки и содержит в себе многогранник ее устойчивости. Для случайно сгенерированных задач проведено экспериментальное сравнение размерностей и относительных объемов многогранников оптимальности и устойчивости оптимальной перестановки обслуживания $n$ требований при случайно сгенерированных сценариях.

Статья представлена к публикации членом редколлегии: А. А. Лазарев