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

Теория расписаний — раздел дискретной математики, занимающийся проблемами упорядочения. В общем случае проблемы формулируются так: Задано некоторое множество работ (требований) ${\displaystyle J=\{J_{1},J_{2},\dots ,J_{n}\}}$ с определённым набором характеристик: длительность обработки требования (простейший случай), стоимость обработки требования, момент поступления требования, директивный срок окончания обслуживания требования. Задано некоторое множество машин (приборов) ${\displaystyle M=\{M_{1},M_{2},\dots ,M_{m}\}}$, на которых требования должны обслуживаться в соответствии с некоторым порядком.

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

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

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

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

По дисциплине выполнения работ на машинах можно выделить четыре основные класса задач:

1. Open shop, открытая линия — для каждого требования задано своё подмножество машин, на каждой из которых оно должно обслуживаться некоторое время. Порядок обслуживания на этих машинах произвольный. Задаются разнообразные целевые функции.
2. Job shop, рабочий цех — для каждого требования задано своё упорядоченное подмножество машин (маршрут), на которых оно должно обслуживаться в заданном порядке. Задаются разнообразные целевые функции.
3. Flow shop, потоковая линия — все машины упорядочены — ${\displaystyle M_{1},M_{2},\dots ,M_{m}}$ и каждое требование проходит все машины в этом порядке. Расписание задано перестановкой требований. Как правило, минимизируется общее время обслуживания требований.
4. Задача с директивными сроками — для каждого требования задан момент поступления, время обслуживания и директивный срок окончания обслуживания. Порядок обслуживания на приборах произвольный. Необходимо найти расписание, соблюдающее директивные сроки. При существовании такого расписания можно ставить задачу минимизации числа прерываний.

Последняя задача называется одностадийной, три первые — многостадийными, поскольку для каждого требования задано несколько стадий или операций обслуживания на разных приборах. Возможны разнообразные комбинации ограничений и дисциплин обслуживания, но полиномиальные по времени выполнения алгоритмы известны только для простейших задач из этих классов.

В частности, для задачи Flow shop на двух машинах существует алгоритм Джонсона^[1] временной сложности ${\displaystyle O(n\log(n))}$, который строит расписание с минимальным общим временем обслуживания.

Для задачи с директивными сроками с произвольным числом приборов и прерываниями обслуживания существует алгоритм временной сложности ${\displaystyle O(n^{3})}$, который строит расписание соблюдающее директивные сроки^[2].

Решением задач Open shop и Job shop с одним прибором без прерываний является некоторая перестановка требований и для произвольной целевой функции эти задачи NP-полны. Но для некоторых конкретных целевых функций найдены полиномиальные алгоритмы.^[3][4][5]

Задачи теории расписаний (календарного планирования), записанные в непрерывном времени, имеют, как правило, бесконечное множество допустимых решений. Метод упорядочения позволяет свести задачи теории расписаний к задачам оптимизации на конечных множествах перестановок работ. Сформулирована общая постановка задачи теории расписаний (календарного планирования) в непрерывном времени, в которой компоненты решений описываются с помощью целочисленных функций времени и которая может быть решена методом упорядочения.^[6]

Два способа сведения исходных задач к задачам упорядочения основаны на понятиях компактных (active) и квазикомпактных (semiactive) решений.^[7] В указанном выше препринте В. В. Шмелёва^[6] понятия компактных и квазикомпактных решений обобщены и на этой основе предложено новое понятие монотонных решений. Каждое монотонное решение является и компактным, и квазикомпактным одновременно, поэтому таких решений, как правило, меньше. Это упрощает решение задач упорядочения.

Для описания динамических задач распределения ресурсов со сложными запаздываниями, в том числе с векторными и распределёнными, к которым относятся и задачи теории расписаний (календарного планирования), Шмелёв В. В. в 1983 г.^[6] впервые использовал в неявном виде и в непрерывном времени операцию свёртки. В дальнейшем он использовал эту операцию в явном виде и для дискретного времени и сформулировал общую постановку задачи теории расписаний (календарного планирования) в виде задачи линейного динамического программирования со свёртками.^[8][9] Эта постановка позволяет просто и компактно описывать большое количество динамических задач, в том числе и с целочисленными переменными. Шмелёв В. В. распространил свои результаты по методу точных штрафных функций на данную постановку.

• Richard W. Conway, William L. Maxwell, Louis W. Miller. Theory of scheduling
  • Конвей Р. В., Максвелл В. Л., Миллер Л. В. Теория расписаний. Москва: Главная редакция физико-математической литературы изд-ва «Наука», 1975.
• Танаев В. С., Шкурба В. В. Введение в теорию расписаний. (серия «Экономико-математическая библиотека»), Москва: Главная редакция физико-математической литературы изд-ва «Наука», 1975.
• Левин В. И. Структурно-логические методы в теории расписаний. Пенза: Изд-во Пенз. гос. технол. акад., 2006.
• Лазарев А. А. Теория расписаний. Оценки абсолютной погрешности и схема приближённого решения задач теории расписаний. Учебное пособие. (ИПУ РАН, МФТИ) — М.: МФТИ, 2008. — 222 c. ISBN 978-5-7417-0257-4
• Лазарев А. А., Мусатова Е. Г., Гафаров Е. Р., Кварацхелия А. Г. Теория расписаний. Задачи железнодорожного планирования. М.: ИПУ РАН, 2012. 92 с. ISBN 978-5-91450-102-7.
• Brucker P. Scheduling Algorithms. Heidelberg, Springer. Fifth ed. ISBN 978-3-540-24804-0 (офиц. выпуск на портале издателя).
• Peter Brucker Scheduling Algorithms. Heidelberg, Springer. Fifth ed. ISBN 978-3-540-24804-0 Архивная копия от 21 февраля 2016 на Wayback Machine

Научно-популярные издания

• Шкурба В. В. «Задача трёх станков». — М.: Наука, 1976. — 96 с., илл.