О свойствах оптимальных расписаний в задаче flow shop с прерываниями и произвольным регулярным критерием

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