О сложности некоторых обобщений двухстаночной задачи Джонсона

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