03-05-2023
Теория расписаний — раздел дискретной математики, занимающийся проблемами упорядочения. В общем случае задача ставится так: задано некоторое множество работ (требований) с определенным набором характеристик: стоимость обработки требования, длительность обработки требования, момент поступления требования. Требуется решить задачу дискретной оптимизации: максимизировать/минимизировать стоимость работ/время задержки и т. п.
Задачи теории расписаний можно разделить на 2 группы:
Существуют различные варианты задач теории расписаний, часть из них является NP-полными, часть принадлежит к классу полиномиальных задач, для части задач так и не удалось доказать принадлежности к какому-либо классу сложности. Существует гипотеза, что задача, допускающая прерывания, не сложнее задачи без прерываний. Для большинства задач она соблюдается, кроме одной, где для варианта без прерывания доказана его принадлежность к классу полиномиальных задач, в то время как для аналогичной задачи с прерываниями не существует доказательств принадлежности к какому-либо классу сложности.
Теория расписаний.