Нестрогое суммирование векторов на плоскости и его применение в задачах теории расписаний

Рассматриваются четыре задачи многостадийной теории расписаний с критерием $C_{max}$ с $m$ машинами и $n$ работами: open-shop $(m=3)$, flow-shop $(m=4)$, Акерса–Фридмана $(m=3)$ и двухмаршрутная, с маршрутами (1,2,3) и (2,3,1) при $m=3$. Доказано, что задача open-shop $(m=3)$ эффективно разрешима при выполнении условия $M\ge 7K$, где $M$ – максимальная загрузка машины, $K$ – максимальная длительность операции. Для трех остальных задач построены приближенные алгоритмы полиномиальной трудоемкости с оценками вида $C_{max}(S)\le M+\mu K$, где $r=6, 5.5$ и 5 соответственно. Для задачи flow-shop $(m=3)$ оценка $C_{max}(S)\le M+3K$ достигается за время $O(n)$. При построении эффективных алгоритмов решения указанных задач используется конструктивно доказываемая теорема, устанавливающая достаточные условия “нестрогой суммируемости” конечного семейства векторов с нулевой суммой в заданной области на плоскости.
Ил. 2, библиогр. 10