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

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

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

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

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

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

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

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

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

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

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

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

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

Два способа сведения исходных задач к задачам упорядочения основаны на понятиях компактных и квазикомпактных решений. Эти понятия обобщены и на этой основе предложено новое понятие монотонных решений. Каждое монотонное решение является и компактным, и квазикомпактным одновременно, поэтому таких решений, как правило, меньше. Это упрощает решение задач упорядочения.

Литература

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