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

Рассматривается вычислительная сложность оптимальной рекомбинации для различных вариантов задачи составления поточного расписания (flowshop) с критериями минимизации общего времени завершения работ и максимального временного смещения. Доказана NP-трудность этих задач, и предложен точный алгоритм их решения. Показано, что в случае перестановочной задачи flowshop трудоёмкость предложенного алгоритма полиномиальна для “очти всех” пар родительских решений при числе работ, стремящемся к бесконечности. Ил. 4, библиогр. 26.