Разработка автоматизированной системы составления и оптимизации расписания занятий



Ключевые слова: генетический алгоритм, составление школьного расписания, автоматическая генерация, описание ограничений.

Одними из важных задач современного мира являются задачи планирования и оптимального распределения ресурсов.

Большинство из них являются NP-трудными, и алгоритмы, применимые для их решения, реализованные на ЭВМ, зачастую требуют неприемлемо большое время работы для задач «большой размерности».

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

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

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

Рис. 1. Схема составления расписания

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

Постановка задачи

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

1. Описывать ограничения и критерии оптимальности
2. Автоматически генерировать расписание, удовлетворяющее ограничениям и критериям из пункта [1]
3. Составлять расписание вручную
4. Визуализировать и редактировать составленное расписание

Математическая модель

При описании математической модели составления расписания будут использоваться следующие множества объектов.

1. Множество учебных групп
2. Множество учителей
3. Множество дисциплин
4. Множество кабинетов
5. Множество уроков

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

Тогда в качестве теоретико-множественной модели будет рассматриваться функция

отображения декартового произведения множеств на множество , где означает, что учитель проводит занятие у группы по дисциплине в кабинете во время урока

Объединим множества учителей, учебных групп и множество дисциплин в одно композиционное множество , где

.

Тогда функцию отображения можно представить как каждый конечный вариант расписания можно определить двумя векторами: и , где и соответствуют элементу .

Ограничения и критерии оптимальности расписания предлагается описывать функциями штрафа .

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

Генетический алгоритм

Для решения данной задачи могут быть использованы как эвристические алгоритмы, так и точные методы решения, например, метод раскраски графа. Но использование точных методов решения повлечет за собой сильный рост временных затрат, при увеличении объема входной информации. В связи с этим, было принято решение использовать эвристический метод, а именно — генетический алгоритм.

Алгоритм позволяет сформировать оптимальную особь(расписание) путем скрещивания различных особей, их мутации и селекции.

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

Сам алгоритм состоит из нескольких этапов:

1. Формирование начальной популяции
2. Скрещивание особей
3. Селекция особей и формирование новой популяции
4. Мутация особей
5. Проверка условия остановки алгоритма

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

генов. В первой хромосоме — это элементы множества кабинетов , во второй — элементы множества уроков . При этом генотип каждый хромосомы упорядочен и имеется взаимно однозначное соответствие между -ой позицией в хромосоме и -ым элементом в множестве .

Рис. 2. Особь

Оптимальность особи оценивается значением целевой функции . Чем меньше значение функции, тем оптимальнее особь.

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

Рис. 3. Скрещивание

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

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

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

Программная реализация

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

Рис. 4. Схема взаимодействия модулей

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

Модуль описания ограничений

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

У каждой сущности есть свое наименование, с помощью которого пользователь может идентифицировать её при описании ограничений и добавлении атрибутов. У некоторых сущностей есть константные атрибуты, которые содержат какое-либо значение или являются ссылками на другие сущности. Например, сущность, представляющая учебную неделю группы, содержит в себе атрибут, показывающий количество дней в учебной неделе.

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

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

Описание атрибута должно содержать его тип (целочисленное число, текстовое значение, ссылка на элемент и т. д.), может содержать значение по умолчанию и функцию вычисления.

Описание ограничений можно разделить на три условные части: подготовка данных, проверка и вычисление штрафа.

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

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

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

Рис. 5. Вкладки для описания атрибутов и ограничений

Модуль автоматической генерации

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

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

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

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

Модуль управления

Данный модуль является настольным приложением и основным для взаимодействия с пользователем. Может быть использован отдельно для ручного и полуавтоматического составления расписания.

Рис. 6. Модуль управления

Приложение предоставляет следующий функционал

1. Сохранение, загрузка и создание расписания
2. Ведение справочников
3. Ручное составление расписания
4. Проверка ограничений
5. Визуализация в различных форматах
6. Прочие вспомогательные функции

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

Сохраняется расписание в виде текстового файла в формате stt и загружается открытием этих же файлов.

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

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

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

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

Рис. 7. Подсказка при перетаскивании

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

Также присутствует возможность экспортировать созданное расписание в формат xlsx. Причем экспортирование можно производить в двух самых распространенных форматах: относительно учебных дней и классов, а также относительно учебных дней и учителей. Размеры и вид всех объектов также можно настроить перед экспортированием.

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

Заключение

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

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

Литература:

1. Лазарева А. А., Гафаров Е. Р., Теория расписаний. Задачи и алгоритмы. — М.: МГУ, 2011 г., 224с.
2. Григорьева Н. С., Алгоритм ветвей и границ для задачи составления расписания на параллельных процессорах. [Электронный ресурс] — URL: https://cyberleninka.ru/article/n/algoritm-vetvey-i-granits-dlya-zadachi-sostavleniya-raspisaniya-na-parallelnyh-protsessorah/viewer
3. Кабальнов Ю. С., Шехтман Л. И., Низамова Г. Ф., Земченкова Н. А., Композиционный генетический алгоритм составления реасписания учебных занятий [Электронный ресурс] — URL: https://cyberleninka.ru/article/n/kompozitsionnyy-geneticheskiy-algoritm-sostavleniya-raspisaniya-uchebnyh-zanyatiy
4. Бабкина Т. С., Задача составления расписания: решение на основе многоагентного подхода. [Электронный ресурс] — URL: https://cyberleninka.ru/article/n/zadacha-sostavleniya-raspisaniy-reshenie-na-osnove-mnogoagentnogo-podhoda/viewer
5. Шлее М., Qt 5.10. Профессиональное программирование на C++. — СПб.: БХВ-Петербург, 2018 г., 1072с.
6. Астахова И. Ф., Фирас А. М., Составление расписаний учебных занятий на основе генетического алгоритма [Электронный ресурс] — URL: http://www.vestnik.vsu.ru/pdf/analiz/2013/02/2013–02–17.pdf