Главная
Новости
Строительство
Ремонт
Дизайн и интерьер




07.05.2021


07.05.2021


01.05.2021


26.04.2021


21.04.2021





Яндекс.Метрика





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

09.03.2021

Теория расписаний — раздел дискретной математики, занимающийся проблемами упорядочения. В общем случае проблемы формулируются так: Задано некоторое множество работ (требований) 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-полными, часть принадлежит к классу полиномиальных задач, для части задач так и не удалось доказать принадлежности к какому-либо классу сложности. Существует гипотеза, что задача, допускающая прерывания, не сложнее задачи без прерываний. Для большинства задач она соблюдается, кроме одной, где для варианта без прерывания доказана его принадлежность к классу полиномиальных задач, в то время как для аналогичной задачи с прерываниями не существует доказательств принадлежности к какому-либо классу сложности.

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

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

    В частности, для задачи 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 г. впервые использовал в неявном виде и в непрерывном времени операцию свёртки. В дальнейшем он использовал эту операцию в явном виде и для дискретного времени и сформулировал общую постановку задачи теории расписаний (календарного планирования) в виде задачи линейного динамического программирования со свёртками. Эта постановка позволяет просто и компактно описывать большое количество динамических задач, в том числе и с целочисленными переменными. Шмелёв В. В. распространил свои результаты по методу точных штрафных функций на данную постановку.