О некоторых свойствах оптимальных расписаний в задаче Джонсона с прерываниями

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