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

Рассматриваются конечные семейства векторов на плоскости, сумма которых равна нулю, а норма каждого вектора не превосходит единицы. Конструктивно доказывается возможность нестрогого суммирования всякого такого семейства в выпуклом неограниченном множестве, содержащем точку нуль, все диаметры которого имеют длину (в заданной норме) не меньше единицы. В случае, когда норма одного из диаметров множества меньше единицы на сколь угодно малую величину, проверка существования нестрогой суммируемости заданного семейства векторов в данном множестве становится NP-трудной проблемой в сильном смысле. Применение алгоритма нестрогого суммирования к трем задачам теории расписаний для трех машин позволяет за полиномиальное время вычислять их приближенные расписания с оценками точности, не зависящими от числа работ.
Ил. 3, библиогр. 22