Том 16, номер 3, 2009 г., Стр. 74-98
УДК 519.854.2
Д. А. Чемисова
О свойствах оптимальных расписаний в задаче flow shop с прерываниями и произвольным регулярным критерием
Аннотация:
Исследуются свойства оптимальных расписаний в NP-трудной задаче flow shop с разрешением прерываний операций на минимум произвольной регулярной функции от моментов окончания операций. Показано, что оптимальное расписание любого примера такой задачи может быть построено жадным алгоритмом при подходящем задании приоритетов операций на машинах. Дана оценка на число прерываний в любом жадном (в частности, в оптимальном) расписании. Доказано также, что длина оптимального (по заданному регулярному критерию) расписания всегда совпадает с суммой длин операций из некоторого подмножества. Результаты данной работы обобщают известные ранее результаты для задачи с классическим критерием на минимум длины расписания.
Библиогр. 10.
Ключевые слова: теория расписаний, прерывание, оптимальное расписание, регулярный критерий.
Чемисова Дарья Александровна 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: jad99@mail.ru
Статья поступила 19 декабря 2008 г.
Исправленный вариант — 11 марта 2009 г.
