Структурные свойства оптимальных расписаний с прерываниями операций

Рассматриваются задачи на построение расписаний с разрешением прерываний операций, в которых каждая операция может быть прервана и возобновлена позднее без какого-либо штрафа. Исследуются фундаментальные свойства оптимальных решений этих задач такие, как существование оптимального решения (при условии, что множество допустимых решений непусто), конечность/полиномиальность числа прерываний в оптимальном решении, существование оптимального решения с прерываниями лишь в целочисленных точках и т.п. Такие теоретические вопросы представляют и практический интерес, поскольку структурные свойства оптимальных решений могут быть использованы для уменьшения пространства поиска в практических задачах на построение расписаний. В статье даются ответы на некоторые из этих фундаментальных вопросов для достаточно общей модели теории расписаний (включающей в качестве её частных случаев классические модели на параллельных машинах, цеховые модели и модели календарного планирования с ресурсными ограничениями) и для широкого множества целевых функций, включающего почти все известные. Для двух специальных классов целевых функций (включающих, тем не менее, все классические целевые функции) доказывается существование оптимального решения, обладающего специальной “рациональной” структурой. Важным следствием этого свойства является то, что распознавательные версии многих известных задач теории расписаний с допущением прерываний операций принадлежат классу NP. Библиогр. 13.