Том 3, номер 1, 1996 г., Стр. 80-90
УДК 519.854
А. Г. Щукин, Н. И. Глебов
О сложности некоторых обобщений двухстаночной задачи Джонсона
Аннотация:
Рассматриваются некоторые обобщения двухстаночной задачи Джонсона, изучавшиеся ранее другими авторами в предположении, что последовательности обработки деталей на первом и втором станках совпадают. При таком допущении задачи оказывались полиномиально разрешимыми, так как они сводились (с линейной сложностью)
к обычной задаче Джонсона с двумя станками.
В статье доказана теорема, одним из следствий которой является утверждение о том, что эти задачи NP-трудны, если не предполагать совпадения упомянутых последовательностей. Другое следствие этой теоремы характеризует один известный полиномиальный алгоритм в определенном смысле как достаточно точный приближенный алгоритм для решения рассматриваемых задач. Наряду с этим получено также некоторое достаточное условие полиномиальной разрешимости.
Ил. 1, библиогр. 20.
Щукин А. Г. 2
Глебов Н. И. 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
Статья поступила 5 декабря 1995 г.
