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

Введение

Теория расписаний — раздел дискретной математики, занимающийся проблемами упорядочения.

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

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

• В каждый момент времени на машине выполняется не более одной работы.

• Прерывания в выполнении работ не допустимы.

• Вся исходная информация об индивидуальной задаче определена и известна заранее.

Результаты, к которым приводит то или иное упорядочение, существенно отличаются. В ряде практических случаев эти различия принимают стоимостной характер или определяются какой-либо другой величиной.

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

1 Теоретическая часть

1.1   Основные определения, относящиеся к теории расписаний

Расписание  —  указание,  на  каких  машинах  и  в  какое  время  должны  выполняться работы.

В каждый момент времени каждая машина выполняет не более одной работы, и каждая работа выполняется на одной машине или не выполняется вовсе.

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

1) Подлежащие выполнению работы определены и известны полностью. Предполагается, что все заданные работы должны быть выполнены (разбиение совокупности работ на классы выполняемых и невыполняемых не входит в задачу упорядочения).

2) Однозначно определены устройства, выделяемые для выполнения заданных работ.

3) Задана совокупность всех элементарных действий, связанных с выполнением каждой из работ, и ограничений, налагаемых на порядок их выполнения. Известно также, каким образом осуществляются эти действия и что существует, по крайней мере, по одному устройству, способному выполнить каждое из них.

Существует определенное различие между терминами “упорядочение” и “составление расписания”. Упорядочение подразумевает формирование очередности операций, выполняемых одной машиной, в то время как составление расписания означает задание последовательности действий нескольким машинам.

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

Обычно в задачах теории расписаний предполагается, что время выполнения каждой работы или ее операции на каждой машине фиксировано. Однако на практике оно часто зависит от времени начала выполнения. Если время выполнения каждой работы определяется собственной функцией, то вряд ли можно надеяться на существование точного полиномиального алгоритма для решения задачи. Действительно, если длительность каждой работы J, - определяется непрерывной кусочно-линейной функцией

то, нахождение минимального по длине расписания является NP-трудной в сильном смысле задачей.

1.2   Математическая постановка задачи

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

1) индексом принадлежности к определенной работе,

2) индексом принадлежности к определенной машине,

3) числом, представляющим собой длительность операции.

По первому индексу все множество операций разбивается на систему непересекающихся подмножеств, называемых работами. Разбиение исходного множества по второму индексу приводит к взаимно непересекающимся подмножествам операций, относящихся к определенным машинам.

Для каждой работы задается последовательность составляющих ее операций (определяемая технологическим процессом). Такое частичное упорядочение операций осуществляется заданием отношения порядка. Если операция X должна быть осуществима раньше, чем Y, то говорят, что X предшествует Y. Это записывается в виде:     X<Y или Y>X. Отношение порядка транзитивно: если X<Y, Y<Z, то X<Z. Будем говорить, что операция X непосредственно предшествует операции Y и записывать X<<Y или Y>>X, если X<Y и нет операции Z, такой, что X <Z<Y.

Часто бывает удобно представлять упомянутые соотношения в виде ориентированного графа. Вершины (узлы) графа изображают операции, а дуги - отношение непосредственного предшествования. Две вершины связаны отношением порядка, если существует путь между ними.

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

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

   - равно длительности операции ;

        число - значение , относящееся к X, не меньше, чем для двух операций X и Y относящихся к одной работе и таких, что ;

        каждый из интервалов   расположен целиком внутри одного из отрезков времени доступности соответствующей машины.

Т.о. составление расписания может рассматриваться как задача упорядочения операций, выполняемых каждой машиной.

Почти вся теория, разработанная в настоящее время, относится к ограниченному числу моделей простого процесса обслуживания. Под последним понимается процесс, для которого существенны следующие ограничения:

1) Каждая машина может быть назначена в любой момент времени, т.е. запрещены перерывы в работе машины. Каждая машина формально представляет собой интервал (0, Т), где Т есть произвольно большое число.

2) Работы представляют собой строго упорядоченные последовательности операций. Для заданной операции X существует не более одной операции Y такой, что , и одной операции Z такой, что (рисунок 1).

…

Рисунок 1. Упорядоченная последовательность

3) Каждая операция выполняется только одной машиной.

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

5) Отсутствуют прерывания операций. Для каждой операции задан единственный интервал , причем длительность операции равна .

6) Интервалы выполнения последовательных операций одной и той же работы не пересекаются. Величина , соответствующая назначению операции X, не может быть меньше для любой операции Y такой, что .

7) В каждый момент времени машина может выполнять не более одной операции.

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

Решение задачи расписания можно представить с помощью диаграмм Гантта (рисунок 2).

Рисунок 2. Одно решение, представленное на двух диаграммах Гантта.

1.3 Классификация задач теории расписаний и примеры

Задача теории расписаний считается заданной, если определены

1) подлежащие выполнению работы и операции;

2) количество и типы машин, выполняющих операцию;

3) порядок прохождения машин;

4) критерии оценки расписаний.

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

Порядок выполнения машинами операций одной работы определяет, является ли система машин:

а) конвейерной;

б) со случайным порядком выполнения работ;

в) системой произвольного типа.

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

В системе со случайным порядком выполнения работ машинами любая операция может выполняться любой машиной, т.е. все машины являются идентичными.

В системах произвольного типа каждая операция может выполняться какой-либо определенной машиной.

Для классификации задач теории расписаний в дальнейшем используется запись А/В/С/D, где

        А характеризует процесс поступления работ. Для динамических задач А представляет собой функцию распределения времени между поступлениями. Для статических задач А соответствует числу одновременно поступивших работ, если по этому поводу ничего специально не оговорено. Если на месте А стоит n то это означает произвольное, но конечное число работ в статическом случае.

        В характеризует число машин в системе. Если на месте В стоит m то это означает произвольное число машин.

        С характеризует порядок (дисциплину) выполнения работ машинами. Если на месте С находится F, то это соответствует конвейерной системе; если R - то случайной, и если G - произвольной. Для системы, состоящей из одной машины, указанные дисциплины теряют смысл и поэтому для такой системы третий параметр опускается.

        D характеризует оценку (критерий) расписания.

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

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

Пример 1. P | prec, pi = 1 | Cmax

Задача поиска расписания с минимальным временем окончания всех работ на m параллельных машинах с длительностями работ pi = 1 и условиями предшествования, то есть предполагается известным ориентированный граф без циклов, вершинами которого являются работы, а дуги задают частичный порядок выполнения работ.

Если n = 7, m = 2 и условия предшествования заданы графом:

Рисунок 3 Известный ориентированный граф

то одно из допустимых решений имеет вид

                                          Рисунок 4 Диаграмма Гантта для примера 1

Пример 2. 1 | ri, pmtn | Lmax

Задача на одной машине с возможностью прерывания работ, директивными сроками окончания работ и произвольными временами появления работы.

Требуется найти расписание , минимизирующее максимальное запаздывание, то есть