Современные информационные технологи / 3. Программное
обеспечение
к.т.н. Супруненко О.А., магистрант Корольчук А.О.
Черкасский национальный университет имени Богдана
Хмельницкого, Украина
ТЕХНОЛОГИЯ ИМИТАЦИОННОГО
МОДЕЛИРОВАНИЯ ДЛЯ ПО СОСТАВЛЕНИЯ РАСПИСАНИЯ ВУЗа
Одним из полезных аспектов автоматизации
формирования учебного расписания ВУЗа является возможность рассмотрения
вариантов составления расписания для выбора наиболее приемлемого при рабочем
использовании. Важна и возможность ведения расписания для внесения текущих
изменений.
В соответствии с теорией расписаний,
эффективность планирования и составления расписания зависит от ряда принципов.
В частности это: участие (к планированию привлекаются те лица, которых оно
касается), единичность (каждое звено взаимодействует со всей системой), непрерывность
(процесс формирования проводится регулярно), гибкость (возможность вносить изменения)
и тонкость (план сложен с точностью, которую можно реализовать) [1].
Формирование расписания занятий является
сложной математической задачей, которую можно рассматривать как задачу оптимизации
с большим количеством критериев. К ним можно отнести факторы полноты и равномерности
выполнения учебного плана, нагрузку на студентов и преподавателей, загруженность
и вместительность аудиторий, личные пожелания и др.
Верховным Советом приняты изменения и
дополнения к Закону Украины "Об образовании" [2], которые необходимо учитывать
при составлении учебных планов и расписания. Это уменьшение количества часов на
один учебный кредит ECTS; уделение внимания планированию как аудиторных занятий,
так и самостоятельной работы студентов; адаптация учебной нагрузки студентов к
условиям обучения по каждому направлению подготовки каждым ВУЗом самостоятельно,
что позволяет учесть особенности изложения учебного материала, его практической
проработки, а также авторские подходы к планированию
учебного процесса специалистами конкретных ВУЗов.
Процесс формирования
расписания можно разделить на такие этапы
(рис. 1):
1.
Составление и
утверждение учебных планов по направлениям подготовки и специальностям.
2.
Формирование на основе учебных
планов рабочих учебных планов для студенческих групп на каждый семестр. Формирование
нагрузки кадрового преподавательского состава. Формирование контингента
студентов, потоков, групп и подгрупп. Формирование аудиторного фонда. Составление
ограничений по четырём предыдущим документам.
3.
Получение на основе рабочих
учебных планов групп/подгрупп перечня занятий, которые нужно разместить в расписании,
а также разпределение нагрузки между преподавателями (т.е. закрепление за каждым
видом занятий в определённой группе преподавателя, который читает данную
дисциплину и проводит данный вид занятий), уточнение ограничений.
4.
Размещение занятий в
соответствии с требованиями и ограничениями.
Рис. 1. Упрощённая схема процесса формирования расписания.
Процесс составления расписания относится к
задачам целочисленного программирования, сложность решения которых растёт экспоненциально
с ростом числа и возможных значений варьируемых параметров (такие задачи относятся
к классу NP-полных задач [3]). Кроме того, для данных задач характерно наличие
большого объёма разнородной начальной информации, большого числа требований и ограничений,
которые сложно формализуются. Эти факторы усложняют автоматизацию процесса составления
расписания, несмотря на широкий спектр методов целочисленного программирования.
Для решения задачи составления расписания применяются
методы полного перебора (ограниченно), метод ветвей и границ, а также эвристические
методы, в том числе методы, построенные на основе генетических алгоритмов [4]. С
помощью данных методов можно сформировать математическую модель, которая
отвечает необходимым ограничениям, но в силу NP-полного характера задачи составления
расписания, эта модель будет громоздкой, что значительно усложняет её построение.
Точного обобщённого решения поставленная задача не имеет, потому она решается приближено,
а затем проводится оценка вариантов полученных решений, что усложняет программную
реализацию.
Чтобы упростить процесс построения расписания
в работе предлагается применение итерационного метода формирования расписания
на основе парадигмы имитационного моделирования. При этом алгоритм предусматривает
итеративную процедуру, которая оперирует непосредственно расписанием и таблицами
данных, которые необходимо включить в расписание [3, 5].
Процесс составления расписания начинается с
пустой формы расписания, все занятия находятся в списке неучтённых занятий, преподаватели
не загружены, группы для постановки занятий открыты, аудитории не заняты. Затем
алгоритм позволяет перейти от начального состояния расписания к последующим, реализуя
стремление по выбранным критериям разместить все занятия, включённые в список.
Процесс продолжается до тех пор, пока не будет сформировано полное расписание
или выполнится определённое количество итераций, которое будет остановлено определёнными
ограничениями. По подобному принципу работает и алгоритм на основе оценки
свободы расположения занятий в расписании [6].
При реализации итерационного метода формируются
правила выбора очередного занятия из списка; определение преподавателя,
ведущего данное занятие, группы студентов, для которой проводиться занятие,
аудитории и лучшей для занятия позиции в расписании; оценка элементов
расписания. Задача составления расписания разделяется на ряд задач размещения в
расписании отдельного занятия, каждая подзадача решается путём
целенаправленного перебора возможных вариантов расположения отдельного занятия,
и после нахождения допустимых решений всех подзадач, задача формирования расписания
считается решенной.
Программный продукт на основе предложенного
решения ускорит процесс формирования расписания ВУЗа, повышая уровень
автоматизации путём анализа составляющих рабочего учебного плана и выдвинутых ограничений,
в частности особенностей распределения преподавателей и аудиторного фонда. Разработка
позволит уменьшить нагрузку на персонал, который составляет и ведёт расписание,
благодаря тому, что процесс преимущественно автоматизирован, а пользователь лишь
вносит текущие правки в расписание.
Литература:
1.
Эффективность планирования принципов [Электронный документ]. Режим доступа:
http://upravlencam.ru/page307/page318/index.html.