Теория расписаний

Теория расписаний — раздел дискретной математики, занимающийся проблемами упорядочения. В общем случае задача ставится так: задано некоторое множество работ (требований) с определённым набором характеристик: стоимость обработки требования, длительность обработки требования, момент поступления требования. Требуется решить задачу дискретной оптимизации: максимизировать/минимизировать стоимость работ/время задержки и т. п.

Задачи теории расписаний можно разделить на 2 группы:

• задачи с прерываниями (когда в момент поступления нового требования старое требование (задача) может быть прервана, т.е. отложена, с возможностью завершения позже)
• задачи без прерываний (то есть каждое требование выполняется до конца без прерываний).

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

Литература

• Конвей Р. В., Максвелл В. Л., Миллер Л. В. Теория расписаний. Москва: Главная редакция физико-математической литературы изд-ва "Наука", 1975.
• Левин В.И. Структурно-логические методы в теории расписаний. Пенза: Изд-во Пенз. гос. технол. акад., 2006.