Том 2, номер 2, 1995 г., Стр. 69-100

УДК 519.854
С. В. Севастьянов
Нестрогое суммирование векторов на плоскости и его применение в задачах теории расписаний

Аннотация:
Рассматриваются четыре задачи многостадийной теории расписаний с критерием $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.

Севастьянов С. В. ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

Статья поступила 20 февраля 1995 г.