Сложность задачи построения циклического расписания обработки партии идентичных деталей с технологическими ограничениями

Рассматривается задача построения циклического расписания обработки идентичных деталей с минимальным временем цикла при наличии запретов на простой между некоторыми парами последовательно выполняемых операций. Исследована сложность задачи и ряда её частных случаев. Доказано, что в общем случае задача является NP-трудной в сильном смысле. Выделены эффективно разрешимые случаи и описаны соответствующие алгоритмы. В случае обработки детали без простоев между операциями доказана полиномиальная разрешимость задачи и предложено два полиномиальных алгоритма. Разработан алгоритм решения задачи в общем случае, который является псевдополиномиальным, если число пар последовательных операций, между которыми разрешены простои, ограничено константой. С другой стороны, показано, что в случае одного запрета задача полиномиально разрешима, а при двух запретах уже NP-трудна. Ил. 4, библиогр. 14.