Том 16, номер 1, 2009 г., Стр. 3-36
УДК 519.854.2
Ф. Баптист, Ж. Карлье, А. В. Кононов, М. Керан, С. В. Севастьянов, М. Свириденко
Структурные свойства оптимальных расписаний с прерываниями операций
Аннотация:
Рассматриваются задачи на построение расписаний с разрешением прерываний операций, в которых каждая операция может быть прервана и возобновлена позднее без какого-либо штрафа. Исследуются фундаментальные свойства оптимальных решений этих задач такие, как существование оптимального решения (при условии, что множество допустимых решений непусто), конечность/полиномиальность числа прерываний в оптимальном решении, существование оптимального решения с прерываниями лишь в целочисленных точках и т. п. Такие теоретические вопросы представляют и практический интерес, поскольку структурные свойства оптимальных решений могут быть использованы для уменьшения пространства поиска в практических задачах на построение расписаний. В статье даются ответы на некоторые из этих фундаментальных вопросов для достаточно общей модели теории расписаний (включающей в качестве её частных случаев классические модели на параллельных машинах, цеховые модели и модели календарного планирования с ресурсными ограничениями) и для широкого множества целевых функций, включающего почти все известные. Для двух специальных классов целевых функций (включающих, тем не менее, все классические целевые функции) доказывается существование оптимального решения, обладающего специальной «рациональной» структурой. Важным следствием этого свойства является то, что распознавательные версии многих известных задач теории расписаний с допущением прерываний операций принадлежат классу NP.
Библиогр. 13.
Ключевые слова: теория расписаний, прерывания, оптимальное расписание.
Баптист Филипп 3
Карлье Жан 3
Кононов Александр Вениаминович 1
Керан Морис 4
Севастьянов Сергей Васильевич 1,2
Свириденко Максим Иванович 5
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2.
Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
3. CNRS, Heudiasyc, Univ. de Tech. de Compiègne & École Polytechnique
4. Faculty of Commerce and Business Administration, University of British Columbia,
Vancouver, B.C., Canada V6T 1Z2
5. IBM T. J. Watson Research Center,
Yorktown Heights, USA
е-mail: baptiste@utc.fr, carlier@utc.fr, alvenko@math.nsc.ru, Maurice.Queyranne@commerce.ubc.ca, seva@math.nsc.ru, sviri@us.ibm.com
Статья поступила 13 октября 2008 г.
Исправленный вариант — 12 декабря 2008 г.
