Теория расписаний — раздел дискретной математики, занимающийся проблемами упорядочения. В общем случае проблемы формулируются так: Задано некоторое множество работ (требований) с определённым набором характеристик: длительность обработки требования (простейший случай), стоимость обработки требования, момент поступления требования, директивный срок окончания обслуживания требования. Задано некоторое множество машин (приборов) , на которых требования должны обслуживаться в соответствии с некоторым порядком.
Ставится задача дискретной оптимизации: построить расписание, минимизирующее время выполнения работ, стоимость работ и т. п. Расписание — указание, на каких машинах и в какое время должны обслуживаться требования (выполняться работы).
Задачи теории расписаний можно разделить на две группы:
Существуют различные варианты задач теории расписаний, часть из них является NP-полными, часть принадлежит к классу полиномиальных задач, для части задач так и не удалось доказать принадлежности к какому-либо классу сложности. Существует гипотеза, что задача, допускающая прерывания, не сложнее задачи без прерываний. Для большинства задач она соблюдается, кроме одной, где для варианта без прерывания доказана его принадлежность к классу полиномиальных задач, в то время как для аналогичной задачи с прерываниями не существует доказательств принадлежности к какому-либо классу сложности.
По дисциплине выполнения работ на машинах можно выделить четыре основные класса задач:
Последняя задача называется одностадийной, три первые — многостадийными, поскольку для каждого требования задано несколько стадий или операций обслуживания на разных приборах. Возможны разнообразные комбинации ограничений и дисциплин обслуживания, но полиномиальные по времени выполнения алгоритмы известны только для простейших задач из этих классов.
В частности, для задачи Flow shop на двух машинах существует алгоритм Джонсона[1] временной сложности , который строит расписание с минимальным общим временем обслуживания.
Для задачи с директивными сроками с произвольным числом приборов и прерываниями обслуживания существует алгоритм временной сложности , который строит расписание соблюдающее директивные сроки[2].
Решением задач Open shop и Job shop с одним прибором без прерываний является некоторая перестановка требований и для произвольной целевой функции эти задачи NP-полны. Но для некоторых конкретных целевых функций найдены полиномиальные алгоритмы.[3][4][5]
Задачи теории расписаний (календарного планирования), записанные в непрерывном времени, имеют, как правило, бесконечное множество допустимых решений. Метод упорядочения позволяет свести задачи теории расписаний к задачам оптимизации на конечных множествах перестановок работ. Сформулирована общая постановка задачи теории расписаний (календарного планирования) в непрерывном времени, в которой компоненты решений описываются с помощью целочисленных функций времени и которая может быть решена методом упорядочения.[6]
Два способа сведения исходных задач к задачам упорядочения основаны на понятиях компактных (active) и квазикомпактных (semiactive) решений.[7] В указанном выше препринте В. В. Шмелёва [6] понятия компактных и квазикомпактных решений обобщены и на этой основе предложено новое понятие монотонных решений. Каждое монотонное решение является и компактным, и квазикомпактным одновременно, поэтому таких решений, как правило, меньше. Это упрощает решение задач упорядочения.
Для описания динамических задач распределения ресурсов со сложными запаздываниями, в том числе с векторными и распределёнными, к которым относятся и задачи теории расписаний (календарного планирования), Шмелёв В. В. в 1983 г.[6] впервые использовал в неявном виде и в непрерывном времени операцию свёртки. В дальнейшем он использовал эту операцию в явном виде и для дискретного времени и сформулировал общую постановку задачи теории расписаний (календарного планирования) в виде задачи линейного динамического программирования со свёртками.[8][9] Эта постановка позволяет просто и компактно описывать большое количество динамических задач, в том числе и с целочисленными переменными. Шмелёв В. В. распространил свои результаты по методу точных штрафных функций на данную постановку.
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .