Задачи и модели теории расписаний

Постановка проблемы решения задач календарного планирования

Временная увязка некоторого множества действий, сопряженных с достижением поставленной цели при определенных ограничениях, требует построения так называемого календарного плана. Это весьма сложная задача. Если же требуется построить в некотором смысле наилучший календарный план, то сложность такой задачи неизмеримо возрастает. Круг вопросов, связанных с построением наилучших календарных планов (расписаний), а также с разработкой математических методов их решения, изучает теория расписаний [20], представляющая собой одну из дисциплин прикладной математики.

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

Существует много способов представления расписаний. Среди них наиболее наглядным считается представление в виде графиков Ганта. В этих графиках каждой работе ставится в соответствие отрезок определенной длины, а каждой единице оборудования — ось времени, вдоль которой размещаются отрезки, обозначающие работу на данном оборудовании. При фиксированном начале отсчета времени взаимное расположение отрезков дает всю необходимую информацию (рис. 17.1).

Другим распространенным способом представления расписаний является построения сетевого графика (графа), который отображает логическую связь во времени отдельных работ. Сетевые графики могут быть двух типов: «работы-вершины» и «вершинысобытия». В первом типе графиков работы изображаются вершинами, а дуги информируют о взаимозависимости очередности выполнения работ (рис. 17.2). Сетевой график облегчает восприятие логической взаимозависимости очередности выполнения работ, а также распараллеливание комплексов работ. Часто каждой вершине бывает поставлено в соответствие число — оценка времени выполнения соответствующей работы.

Рис. 17.1. График Ганта.

Рис. 17.2. Сетевой график типа «работы-вершины».

Масштабное представление продолжительности и сроков выполнения работ используется в сетевых графиках типа «вершина-событие». В этом случае работы отображаются дугами, а вершины отделяют работы друг от друга. На практике вершины обычно отождествляют с некоторыми событиями, например окончанием работ. Неудобство такой формы сетевых графиков заключается в необходимости введения так называемых фиктивных вершин. Они вводятся для отражения очередности выполнения работ. На рис. 17.3 изображен сетевой график типа «вершины-события» идентичный графику, изображенному на рис. 17.2. Здесь введена фиктивная дуга 13, чтобы показать, что работа 6 может начать выполняться только после окончания и работы 4, и работы 5.

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

Рассмотрим две наиболее характерные постановки задач календарного планирования.

Рис. 17.3. Сетевой график типа «вершины-события».

Пусть требуется выполнить заданную совокупность работ (программу) S = (А_1; А₂, …, А_п). Для каждой работы А, е S указано подмножество предшествующих ей работ Р, = {A_fc}_;. К предшествующим относительно данной работы А, относятся все те работы, которые обязательно должны быть закончены до начала работы А" т. е.

где t, — время окончания г'-й работы; т, — ее длительность.

В то же время для каждой работы А, е S может быть указано подмножество всех последующих ей работ Р, = {A_h}_p т. е. тех работ, которые могут быть начаты только после завершения работы Ар

Решению задач, в которых ограничения описывают взаимную зависимость порядка выполнения работ (при этом считается, что расход ресурса практически не зависит от очередности выполнения работ), посвящены методы сетевого планирования и управления [5]. К наиболее характерным примерам такого рода задач можно отнести задачи построения технологий изготовления изделий.

Задачи второго типа, называемые задачами упорядочения, формулируются примерно так. Пусть требуется выполнить заданную совокупность работ (программу) S = (А_1; А₂,…, А"), последовательность выполнения которых может быть достаточно произвольной. При переходе от выполнения одной работы А, к другой работе Aj должен быть затрачен некоторый ресурс в объеме q_ip Требуется установить такой допустимый порядок выполнения всех работ, чтобы затратить на выполнение программы наименьший объем ресурсов [3]. Примерами таких задач являются задачи переналадки оборудования, составления маршрутов и т. п.

На практике чаще всего встречаются задачи с ограничениями обеих групп, что резко усложняет процесс их решения. В некоторых случаях поступают так: производственную программу представляют в виде некоторого разбиения на подпрограммы S = (ЩУ, {R_k}, …, {R_fc}). Каждая подпрограмма состоит из подмножества работ, очередность выполнения которых жестко связана с расходованием ресурсов. В то же время между подпрограммами существуют жесткие ограничения на порядок их выполнения. В качестве примера можно привести процесс изготовление обуви, где заготовка низа, верха и других элементов производится зачастую совершенно отдельно друг от друга. Сборка же обуви представляет собой в целом жестко упорядоченный набор операций.

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