Теория расписаний — раздел дискретной математики, занимающийся проблемами упорядочения. В общем случае проблемы формулируются так: Задано некоторое множество работ (требований) J = { J 1 , J 2 , … , J n } {displaystyle J={J_{1},J_{2},dots ,J_{n}}} с определённым набором характеристик: длительность обработки требования (простейший случай), стоимость обработки требования, момент поступления требования, директивный срок окончания обслуживания требования. Задано некоторое множество машин (приборов) M = { M 1 , M 2 , … , M m } {displaystyle M={M_{1},M_{2},dots ,M_{m}}} , на которых требования должны обслуживаться в соответствии с некоторым порядком.
Ставится задача дискретной оптимизации: построить расписание, минимизирующее время выполнения работ, стоимость работ и т. п. Расписание — указание, на каких машинах и в какое время должны обслуживаться требования (выполняться работы).
Задачи теории расписаний можно разделить на две группы:
- Задачи с прерываниями. В любой момент обслуживание требования на машине может быть прервано (с возможностью завершения позже на той же или другой машине) ради обслуживания другого требования.
- задачи без прерываний — каждое требование на машине обслуживается от начала до конца без прерываний.
Существуют различные варианты задач теории расписаний, часть из них является NP-полными, часть принадлежит к классу полиномиальных задач, для части задач так и не удалось доказать принадлежности к какому-либо классу сложности. Существует гипотеза, что задача, допускающая прерывания, не сложнее задачи без прерываний. Для большинства задач она соблюдается, кроме одной, где для варианта без прерывания доказана его принадлежность к классу полиномиальных задач, в то время как для аналогичной задачи с прерываниями не существует доказательств принадлежности к какому-либо классу сложности.
По дисциплине выполнения работ на машинах можно выделить четыре основные класса задач:
Последняя задача называется одностадийной, три первые — многостадийными, поскольку для каждого требования задано несколько стадий или операций обслуживания на разных приборах. Возможны разнообразные комбинации ограничений и дисциплин обслуживания, но полиномиальные по времени выполнения алгоритмы известны только для простейших задач из этих классов.
В частности, для задачи Flow shop на двух машинах существует алгоритм Джонсона временной сложности O ( n log ( n ) ) {displaystyle O(nlog(n))} , который строит расписание с минимальным общим временем обслуживания.
Для задачи с директивными сроками с произвольным числом приборов и прерываниями обслуживания существует алгоритм временной сложности O ( n 3 ) {displaystyle O(n^{3})} , который строит расписание соблюдающее директивные сроки.
Решением задач Open shop и Job shop с одним прибором без прерываний является некоторая перестановка требований и для произвольной целевой функции эти задачи NP-полны. Но для некоторых конкретных целевых функций найдены полиномиальные алгоритмы.
Задачи теории расписаний (календарного планирования), записанные в непрерывном времени, имеют, как правило, бесконечное множество допустимых решений. Метод упорядочения позволяет свести задачи теории расписаний к задачам оптимизации на конечных множествах перестановок работ. Сформулирована общая постановка задачи теории расписаний (календарного планирования) в непрерывном времени, в которой компоненты решений описываются с помощью целочисленных функций времени и которая может быть решена методом упорядочения.
Два способа сведения исходных задач к задачам упорядочения основаны на понятиях компактных (active) и квазикомпактных (semiactive) решений. В указанном выше препринте В. В. Шмелёва понятия компактных и квазикомпактных решений обобщены и на этой основе предложено новое понятие монотонных решений. Каждое монотонное решение является и компактным, и квазикомпактным одновременно, поэтому таких решений, как правило, меньше. Это упрощает решение задач упорядочения.
Для описания динамических задач распределения ресурсов со сложными запаздываниями, в том числе с векторными и распределёнными, к которым относятся и задачи теории расписаний (календарного планирования), Шмелёв В. В. в 1983 г. впервые использовал в неявном виде и в непрерывном времени операцию свёртки. В дальнейшем он использовал эту операцию в явном виде и для дискретного времени и сформулировал общую постановку задачи теории расписаний (календарного планирования) в виде задачи линейного динамического программирования со свёртками. Эта постановка позволяет просто и компактно описывать большое количество динамических задач, в том числе и с целочисленными переменными. Шмелёв В. В. распространил свои результаты по методу точных штрафных функций на данную постановку.