Расписание является необходимым инструментом в организации деятельности человека. Более того, составление расписания является профессиональной обязанностью для многих категорий служащих. Они организуют учебный процесс, составляют расписание движения транспортных потоков, разрабатывают календарные графики работы предприятий, учреждений и т. д. Зачастую, задача довольно сложная — увязать со временем множество дискретных действий, сопряженных с достижением заданной цели.
Математическое описание управляемого производственного или организационного технологического процесса, в котором определено множество допустимых управлений (расписаний) этого процесса, можно понимать как математическую модель теории расписаний.
Под математической моделью теории расписаний понимается математическое описание некоторого управляемого производственного, организационно-технологического процесса, в котором определено множество допустимых управлений (расписаний) этого процесса. Длительность во времени некоторого дискретного процесса является критерием оптимальности для задач теории расписаний. Задачей оптимизации теории расписаний в основном является минимизация времени выполнения данного процесса. Примером задач теории расписаний являются задачи календарного и сетевого планирования [1, 2].
Задача составления расписания вуза состоит из двух подзадач: составление расписания занятий и составление расписания экзаменов. Эта задача играет особую роль в управлении организационно-технологическим процессом учреждения с линейно-штабной (с временно-целевыми компонентами) моделью организационной структуры управления. Высшие учебные заведения, несомненно, относятся к данному типу учреждений [3–5].
В наиболее общей формулировке задача составления расписания состоит в следующем: с помощью некоторого множества ресурсов или обслуживающих устройств должны быть распределены временные ресурсы таким образом чтобы была выполнена некоторая фиксированная система заданий. Цель заключается в том, чтобы при заданных свойствах заданий и ресурсов и наложенных на них ограничениях найти эффективный алгоритм упорядочения заданий во времени, оптимизирующий или стремящийся оптимизировать требуемую меру эффективности решения поставленной задачи. В качестве основных мер эффективности являются длина расписания и среднее время пребывания заданий в системе. Модель этой задачи является детерминированной в том смысле, что вся информация, на основе которой принимаются решения об упорядочении, известна заранее.
Общая теория расписаний предполагает, что все обслуживающие устройства (или процессоры) не могут выполнять в данный момент времени более одного задания. Так, например, если в качестве процессора при распределении заданий принять учебную аудиторию, то во время, когда аудитория занята одной из групп (неважно, проходит ли там учебное занятие или сдается экзамен), она не может использоваться другой группой.
Поэтому при переносе общей теории расписаний на расписание экзаменационной сессии необходимо сделать следующие ограничения:
- в качестве множества заданий для распределения выступают множества учебных групп и их экзаменов;
- все экзамены должны быть проведены в период времени, определенного для экзаменационной сессии;
- для проведения экзамена должны выделяться аудитории с необходимым для сдачи данного предмета оборудованием;
- для подготовки к каждому из экзаменов должно выделяться не менее 3 свободных дней;
- у преподавателя не должно быть занятий с другими группами на время проведения экзамена;
- аудитории должны быть свободны от занятий других групп во время проведения экзамена;
- задания имеют принадлежность к объектам, в качестве которых выступают учебные аудитории и преподаватели.
В итоге формулировка задачи составления расписания экзаменационной сессии звучит следующим образом. Для заданного набора учебных групп, их экзаменов и заданного временного интервала (период экзаменационной сессии) необходимо построить такое распределение всех объектов (преподаватели и аудитории) во времени, при котором будут учтены все требования и ограничения, предъявляемые к расписанию экзаменационной сессии.
Составление расписания относится к задачам целочисленного программирования, сложность решения которых растет экспоненциально с ростом числа и возможных значений варьируемых переменных (такие задачи относятся к классу NP-трудных задач). Кроме того, для нее характерно наличие большого объема различной по своему составу исходной информации и большого числа трудно формализуемых требований. Указанные сложности препятствуют автоматизации процедуры составления расписания, несмотря на наличие широкого спектра методов целочисленного программирования.
Однако существование удачно составленных расписаний говорит о том, что задача составления оптимального расписания разрешима, или хотя бы о том, что для нее существуют допустимые решения.
Для составления расписания используются следующие методы [6]:
- точные (классические) методы и алгоритмы целочисленного программирования;
- метод имитации отжига;
- метод раскраски графов;
- имитационное моделирование;
- логическое программирование в ограничениях;
- эвристические методы, в том числе основанные на генетических алгоритмах;
- и др.
С помощью данных методов возможно получение точной математической модели, отвечающей всем ограничениям, но в силу NP-сложного характера задачи составления расписания эта модель будет громоздкой и сложной. Чтобы избежать этого, применяется имитационное моделирование. В этом случае алгоритм оперирует непосредственно расписанием и списком занятий, которые необходимо включить в расписание (учебным планом). Тогда алгоритм формирования расписания экзаменов является итерационным. Процесс поиска в нем представляет движение от одного непротиворечивого (не содержащего конфликтов) расписания к другому в направлении улучшения его качества. Исходная точка поиска — начальное (опорное) расписание, результат — расписание, качество которого улучшить нельзя или когда выполнится фиксированное количество итераций.
При реализации алгоритма, основанного на принципах имитационного моделирования, особое внимание уделяется разработке эвристических правил выбора очередного занятия из списка, определения наилучшей для него позиции в расписании и оценке получаемого расписания.
К положительным чертам такого подхода можно отнести возможность детального учета специфики решаемой задачи в случае составления расписания для конкретного вуза. Однако при этом сильно ограничивается возможность применения разработанной системы в других учебных заведениях. Кроме того, по-видимому, понадобится вносить существенные изменения в алгоритм при незначительных внутренних изменениях в вузе.
Однако, так как алгоритм основан на действиях, совершаемых диспетчером при составлении расписания, то существует возможность организации деятельного диалога между пользователем и системой при поиске оптимального расписания.
Если под фазой понимать операцию, которая однократно обрабатывает все множество данных, то автоматизированное составление расписания на любом этапе его формирования является многофазным процессом, включающим:
- разработку структуры представления данных, учитывающую большинство ограничений, накладываемых на расписание;
- разработку алгоритма построения опорного решения, результатом работы которого является хотя бы одно непротиворечивое расписание, если оно существует в рамках заданных начальных условий;
- оценку полученного множества решений и выбор наиболее подходящего.
Уже на этапе формирования опорного решения для оценки качества формируемого расписания к строгим ограничениям добавляется ряд непротиворечивых нестрогих ограничений. Расписание может не отвечать вовсе, отвечать частично или полностью нестрогим ограничениям. С формальной точки зрения разделение ограничений на строгие и нестрогие носит условный характер и зависит от применяемого подхода к построению расписания. Например, авторы работы [7] при разработке системы составления учебного расписания все наложенные на расписание ограничения рассматривают как нестрогие с различными приоритетами. Тогда при сравнении непротиворечивых расписаний оптимальным из них следует считать расписание, которое наиболее полно соответствует наложенным на него ограничениям, причем предпочтение отдается требованиям более высокого приоритета.
Нельзя не заметить принципиальные отличия строгих ограничений при формировании расписания экзаменов от строгих ограничений, используемых при формировании расписания занятий. Например, в расписании экзаменов необходимо обязательное включение временных интервалов (пауз) между экзаменами группы таким образом, чтобы студенты имели время на подготовку, тогда как при формировании расписаний занятий наоборот — отсутствие временных «окон» между занятиями являются одним из видов строгих ограничений.
Литература:
1. Tanaev, V., Gordon, W., Shafransky, Yakov M. Scheduling Theory. Single-Stage Systems — Dordrecht, Boston, London. Kluwer Academic Publishers, 1994. — 374 p.
2. Сотсков Ю. Н., Струсевич В. А., Танаев В. С. Математические модели и методы календарного планирования: Учебное пособие. — Мн.: Университетское, 1994. — 232 с.
3. Греченко Д. А. Структурная компонента модели организационного управления высшим учебным заведением / Д. А. Греченко, В. А. Чулюков // Современные наукоемкие технологии. — 2010. — № 4 — С. 13–16.
4. Греченко Д. А., Чулюков В. А. Ситуационное моделирование в задачах организационного управления вузом // Сборник научных трудов Sworld. — 2009. — Т.3, № 1 — С. 13–15.
5. Чулюков В. А., Греченко Д. А. Концептуальная модель информационных систем организационного управления образованием в условиях неопределенности. / Депонированная рукопись № 472-В2010 21.07.2010. — ВИНИТИ РАН.
6. Безгинов А. Н., Трегубов С. Ю. Обзоор существующих методов составления расписания. / Информационные технологии и программирование: Межвузовский сборник статей. Вып. 2(14). — М.: МГИУ, 2005. — С. 5–18.
7. Rudovà H., Vlk M. Multi-criteria soft constraints in timetabling //Proc. MISTA. — 2005. — P. 11–15.
