Важное практическое значение имеет группа задач, связанных с выполнением комплекса работ, называемых “операциями”, “заявками”, “требованиями”, при наличии ограничений на порядок их выполнения, длительность каждой работы, выделяемые ресурсы и т.п. С такими задачами приходится сталкиваться при решении вопросов календарного планирования и оперативного управления в производстве и при обслуживании населения.
Задачи подобного рода весьма разнообразны и их исследование в зависимости от характерных признаков проводится в рамках различных научных дисциплин.
В теории сетевого планирования основное внимание уделяется определению порядка выполнения сложных разработок, включающих большое число взаимосвязанных работ, требующих многочисленных исполнителей и значительных материальных затрат.
В теории упорядочения рассматриваются вопросы установления порядка выполнения большого комплекса однородных работ с помощью одного или нескольких специальных устройств (машин, приборов).
В теории массового обслуживания рассматриваются задачи назначения приоритетов в обслуживании поступающих заявок некоторыми устройствами (машинами и т.п.).
Все эти виды задач имеют определенное сходство формальных моделей.
6.2Постановка задачи теории расписаний
Целенаправленную деятельность можно рассматривать как некоторый протекающий во времени процесс, заключающийся в реализации (выполнении) определенной совокупности работ S=(P1,...,Ps) называемой также программой.
Выполнение программы связано целым рядом ограничений и условий, которые обычно удается разбить на две группы.
Ограничения a. Эти ограничения описывают взаимную зависимость выполнения работ. Каждой работе Рi Î S можно поставить в соответствие некоторое множество Пi Ì S непосредственно предшествующих работ, без выполнения которых нельзя начинать выполнение работы Рi, а также ряд работ, не входящих в множество S, которые могут рассматриваться как внешние факторы, необходимые для выполнения работы Рi.
Удобно ход выполнения работ рассматривать в дискретном времени, приняв некоторую величину Dt за единичный интервал времени. Этот интервал называют шагом (можно “условный день”, “условный год”).
Некоторые работы могут быть выполнены целиком за один шаг. Другие могут потребовать нескольких шагов. В этом случае в ограничение a должно входить условие допустимости или недопустимости прерывания работ.
Пусть - номер рассматриваемого шага. Обозначим через yi() - долю работы Pi, (= 1,2...) выполняемую на шаге с номером , которую назовем единичной (дневной, сменной и т.п.) порцией работы Pi. Через S() обозначим перечень работ, выполняемых на шаге с номером .
Пусть работа Pi состоит из m единичных порций yi и прерывание этой работы недопустимо.
Условие недопустимости прерывания работы заключается в том, что если эта работа начинается на шаге с номером , то единичные порции yi должны входить в перечень работ S().S(+ 1),..., S(+ m - 1).
Ограничения b. Эти ограничения связаны с ограниченным объемом ресурсов, который может быть выделен на выполнение программы S.
Обозначим через Q() вектор ресурса, который может быть выделен на выполнение работ на шаге с номером . Компонентами вектора Q() могут быть величины Q1 - cырье, материалы, Q2 - оборудование, Q3 - рабочая сила и т.п. Обозначим через q[yi()] - количество ресурса, которое необходимо затратить на выполнение работы yi(t). В этих обозначениях ограничение b записывается в виде
где М - общее число шагов.
Задача на составление расписания сводится к тому, чтобы для каждого шага назвать перечень работ S()={P,...,Р}, которые должны выполняться в течении этого шага, а также долю yi() каждой из этих работ с учетом всех ограничений, накладываемых на порядок выполнения работ и на выделяемые ресурсы.
Если количество работ велико, то количество вариантов расписаний может быть огромным.
Выбор конкретного варианта расписания связан с понятием директивного срока.
Если перечень работ и ресурс на их выполнение уже заданы, то наилучшим (оптимальным) вариантом расписания следует считать такой вариант, при котором срок выполнения всего перечня будет минимальным. Этот срок и принято называть директивным сроком.
Задачу на составление расписания можно разбить на две самостоятельные задачи.
Для решения задач 1-го типа широкое применение получили методы сетевого планирования и управления. Определение порядка выполнения работ внутри каждой подпрограммы с учетом ограничений на очередность выполнения работ и распределение ресурса по этапам выполнения подпрограммы. Жесткие ограничения a в таких задачах в значительной степени предопределяют порядок выполнения отдельных работ. Среди множества вариантов возможны такие, где минимальное время выполнения подпрограммы, наиболее рациональное распределение ресурсов и т.п.
В задачах 2-го типа ограничения на очередность выполнения отдельных работ незначительны; необходимо рассматривать очень большое число различных комбинаций порядка работ, от которого зависит распределение ресурса по шагам (замена оборудования, переналадка). Такие задачи получили название комбинаторных задач на составление расписания или задач упорядочения.
S=(P1,...,Ps) называемой также программой.
- номер рассматриваемого шага. Обозначим через yi(
, то единичные порции yi должны входить в перечень работ S(
,...,Р
}, которые должны выполняться в течении этого шага, а также долю yi(