Интегрированная система составления школьных расписаний

Авторы: Луиза Карпенте, Анна Цейдейра-Пена, Гильерме де Бернардо, Диего Секо.

Автор перевода: Горбань А.С.

Источник (англ.): Университет Ла-Корунья, Лаборатория баз данных

Вступление

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

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

Разработка приложений

Полный процесс строительства происходит в несколько этапов:

1) Ввод данных: данные о преподавателях, группах и предметах.

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

3) Уточнение расписания: сгенерированное решение показывается пользователю. Хотя сгенерированные решения всегда достаточно эффективны, они могут быть улучшены вручную.

Наконец, приложение экспортирует автоматически сгенерированное расписание.

Рис.1 Архитектура приложения.

На рисунке 1 показана наша модульная архитектура, управляющая всем процессом. Хотя используется общая модель данных, импорт и экспорт задач нужны для взаимодействия с внешними системами. Поколение программы было разработано чтобы дать возможность эволюционировать потомкам программы. Таким образом, приложение построено на двух модулях, которые держат «внешнее» управление информацией, и которые интегрированы в результате преобразования информации в общую модель данных. Модуль интеграции или обмена данными обеспечивает обмен данными между приложением и AAOS. Модуль расписания отвечает за генерацию полного решения согласно определенных пользователем ограничений. Это поколение также может работать как автономная система.

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

Модуль интеграции

Этот модуль позволяет приложению обмен с AAOS, которые хранят информацию обо всех учебных центрах в регионе. AAOS обычно хранит всю информациюцию о центрах и предоставляет веб-интерфейс для представления окончательного расписания. Следует отметить, что, например, Ксаде не предоставляет веб-сервис для получения/хранения данных, так что эта задача должна выполняться вручную. Более того, расписания, которые генерировались несколько раз, содержат элементы, которые не приняты официальной моделью данных и должны быть адаптированы. С этой целью модуль обеспечивает обращение с этим к AAOS.

Для того, чтобы поддерживать те AAOS, которые не ориентированы на веб для доступа к хранимой информации, используются системы веб-автоматизации для импорта/экспорта данных из/в AAOS. Этот двигатель использует данные на основе анализа HTML. Инструмент содержит множество импортеров/экспортеров, которые имеют дело с различными моделями предметной области. Целостность индивидуальных лиц контролируется импортерами. Также импортеры могут общаться друг с другом чтобы вывести отношения между внешними объектами и привязать их к общей модели.

Для экспорта данных в AAOS выполняется более сложный процесс так как созданные расписания могут содержать элементы, которые не допускаются в AAOS. Большинство элементов, которые не могут содержаться в AAOS распознаются автоматически. В случае, если некоторая информация изменилась, модуль использует эвристику, чтобы соответствовать сгенерированной модели с информацией, найденной в данный момент во внешнем приложении, используя статистические данные, полученные от предыдущих отображения и некоторую предметно-ориентированную информацию (например, официальное сокращение таблиц). В большинстве случаев выводы не требуют дополнительной регулировки попользователем. В любом случае, пользователь может вручную вносить какие-либо изменения перед экспортом.

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

Главная проблема школьных расписаний - это нахождение момента времени, когда определённый преподаватель проводит определённый предмет в определённой группе Кроме того, существует два различных типа ограничений: жесткие и мягкие ограничения. Жесткие ограничения должны быть выполнены для получения допустимого решение. Рассмотрим следующие типы: в одном классе не могут преподавать два предмета в один и тот же момент, разбиение группы на подгруппы, отсутствие возможности быть на определённой паре у группы или преподавател, определённая последовательность уроков и так далее. Мягкие ограничения задаются для удобства. Например, отсутствие окон или переездов между корпусами.

Описание алгоритмов

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

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

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

Кроме того, мы объединили предыдущие алгоритмы для получения двух гибридных (GT4C и РНК). Кроме того, мы создали несколько вариантов наших генетических алгоритмов, основанных на следующих стратегиях:

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

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

3) Не устранять проигравших кандидатов. Таким образом все лица могут быть родителями по крайней мере один раз.

Оценочные алгоритмы

Для правильной оценки производительности алгоритмов были проведены различные эксперименты на двух наборах синтетических тестов с различными размерами и конфигурацией. Данные берутся из 10 файлов и состоят из 6 групп, 70 классов и 15 учителей. Рисунок показывает среднее значение неудовлетворенных ограничениями и стандартное отклонение для ограничения во времени до 30 минут. Результаты показывают, что большинство алгоритмов получили хорошие результаты и выполняются совершенно аналогично, за исключением небольшой группы, которые выполняют работу очень плохо: варианты V1 и V1 + V2 изгенетических алгоритмов и вариант v3. Кажется, что лучшим выбором является РНК и GT4C.

Рис.2 Результаты для набора А.

После удаления плохо проявивших себя алгоритмов была изучена производительность оставшихся на большой тест: 27 групп, 333 класса, 71 преподаватель. Тестирование проводилось 5 раз с ограничением времени до 5 часов каждый. Рисунок 3 показывает, что вариант v2 получает очень хорошие результаты, в особенности в версии GT + РНК, что снижает изменчивость решения. РНК и вариант V1 + V2 + V3 ведут себя также хорошо, но мягкие ограничения практически не соблюдаются.

Рис.3 Результаты для реальной ситуации.

Для завершения исследования мы проверили лучшие алгоритмы с реальными данными, полученными от средней школы. В левой части рисунка 3 показаны все выбранные алгоритмы, которые достигли хороших результатов. Тем не менее, мы можем выделить те же РНК и GT4C. Обратите внимание, что на 100% удовлетворить жесткие ограничения.

Взаимодействие с пользователем

Как мы уже объясняли ранее, наше приложение управляет всем процессом строительства школьного расписаниия. В большинстве своём трудоёмкая задача решается автоматически. Фазы, которые невозможно автоматизировать на 100% – это фаза введения данных и уточнение решения. Для упрощения этих шагов, мы работали в сотрудничестве с экспертами предметной области, чтобы извлечь реальные потребности пользователей и функциональные возможности, которыми можно решить эту проблему.

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

Когда расписание генерируется, конечный результат должен быть проверен и подтверждён пользователем. Большинство существующих инструментов имеют базовый интерфейс для этого. В большинстве случаев любое изменение в существующем расписании требует множество изменений (например, сдвинуть один урок у одного учителя – это может обернуться проблемой для других учителей). Таким образом наше приложение имеет различные способы изменений, позволяет пользователю принимать решения. Экран делится, чтобы показать одновременно группы и преподавателей. Если обнаружены ошибки, пользователь видит это на экране и может их исправить.

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

Список литературы

  1. de Haan, P., Landman, R., Post, G., and Ruizenaar, H. (2006). A four-phase approach to a timetabling prob- lem in secondary schools. PATAT’06, pp. 423–425.
  2. de Werra, D. (1985). An introduction to timetabling. Eur. Journal of Operational Research, 19(2):151–162.
  3. Even, S., Itai, A., and Shamir, A. (1976). On the complex- ity of timetable and multicommodity row problems. SIAM Journal on Computing, 5:691–703.
  4. Keppler, J. and Erben,W. (1996). A genetic algorithm solv- ing a weekly course-timetabling problem. PATAT’96, pp. 198–211.
  5. Schaerf, A. (1999). Local search techniques for large high- school timetabling problems. IEEE Transactions on Systems, Man, and Cybernetics, 29:368–377.