Том 13, серия 1, номер 3, 2006 г., Стр. 83-102
УДК 519.8
С. В. Севастьянов, Д. А. Чемисова, И. Д. Черных
О некоторых свойствах оптимальных расписаний в задаче Джонсона с прерываниями
Аннотация:
Исследуются свойства оптимальных расписаний в NP-трудной задаче Джонсона с разрешением прерываний операций. В частности, доказано, что длина оптимального расписания всегда совпадает с суммарной длиной некоторого подмножества операций. С использованием найденных свойств показано, что оптимальное расписание любого примера может быть построено жадным алгоритмом (при подходящем задании приоритетов операций). Впервые описан алгоритм точного решения указанной задачи. Показано, что число прерываний в любом жадном расписании (а следовательно, и в оптимальном) не превосходит числа операций, что существенно лучше известных оценок числа прерываний в оптимальном расписании.
Библ. 4.
Севастьянов С. В. 1
Чемисова Д. А. 1
Черных И. Д. 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
Статья поступила 24 марта 2006 г.
