ВВЕДЕНИЕ 4
1. АНАЛИЗ ПРЕДМЕТНОЙ ОБЛАСТИ 6
1.1. ПРОБЛЕМА ПЛАНИРОВАНИЯ РАСПИСАНИЯ КУРСОВ 6
1.1.1 ПОСТАНОВКА ЗАДАЧИ UCTP 6
1.1.2 ОБЗОР СУЩЕСТВУЮЩИХ АЛГОРИТМОВ 8
1.2. ПРОБЛЕМА ДИНАМИЧЕСКОГО УПРАВЛЕНИЯ РАСПИСАНИЕМ КУРСОВ 11
1.2.1 ОБЗОР СУЩЕСТВУЮЩИХ РЕШЕНИЙ 12
1.2.2 ВЫБОР И ОПИСАНИЕ МЕТОДА ДЛЯ ДИНАМИЧЕСКОЙ
ОПТИМИЗАЦИИ РАСПИСАНИЯ 14
2. РЕАЛИЗАЦИЯ ОБРАБОТКИ И УПРАВЛЕНИЯ ОГРАНИЧЕНИЯМИ
РАСПИСАНИЯ И АЛГОРИТМА ЕГО ОПТИМИЗАЦИИ 16
2.1. АРХИТЕКТУРА ДАННЫХ РАСПИСАНИЯ И РЕСУРСОВ 16
2.2. АРХИТЕКТУРА И РЕАЛИЗАЦИЯ ОБРАБОТКИ ОГРАНИЧЕНИЙ
РАСПИСАНИЯ 18
2.2.3 РЕАЛИЗАЦИЯ ВЫВОДА РЕЗУЛЬТАТОВ АНАЛИЗА
ОГРАНИЧЕНИЙ 22
2.3. АЛГОРИТМ ОПТИМИЗАЦИИ РАСПИСАНИЯ 23
2.3.1 РЕАЛИЗАЦИЯ АЛГОРИТМА ОПТИМИЗАЦИИ 23
2.3.2 РЕЗУЛЬТАТЫ ТЕСТИРОВАНИЯ АЛГОРИТМА 28
3. РЕАЛИЗАЦИЯ WEB-ПРИЛОЖЕНИЯ ДЛЯ ЗАДАЧ УПРАВЛЕНИЯ
ОПТИМИЗАЦИИ РАСПИСАНИЕМ 30
3.1. ИСПОЛЬЗУЕМЫЕ ТЕХНОЛОГИИ И АРХИТЕКТУРА ПРИЛОЖЕНИЯ 30
3.2. ФУНКЦИОНАЛЬНОСТЬ И ИНТЕРФЕЙС 30
3.2.1 ИМПОРТ ДАННЫХ РАСПИСАНИЯ И РЕСУРСОВ 31
3.2.2 РУЧНОЕ УПРАВЛЕНИЕ РАСПИСАНИЕМ И АНАЛИЗ НАРУШЕНИЙ 32
3.2.3 УПРАВЛЕНИЕ ОГРАНИЧЕНИЯМИ И ФАКТОРАМИ 34
3.2.4 УПРАВЛЕНИЕ ДАННЫМИ И РЕСУРСАМИ 35
3.2.5 ОПТИМИЗАТОР РАСПИСАНИЯ 36
ЗАКЛЮЧЕНИЕ 38
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 39
ПРИЛОЖЕНИЕ А: SQL выражения факторов 41
ПРИЛОЖЕНИЕ Б: Код обработки ресурсных ограничений 45
ПРИЛОЖЕНИЕ В: Код обработки факторных ограничений 47
ПРИЛОЖЕНИЕ Г: Код оптимизатора расписания 49
В настоящее время в высших учебных заведениях рассматриваются некоторые структурные изменения, приводящие к тому, что образование в вузах становится более динамичной средой [22]. Процессы эффективного планирования и распределения ресурсов учебных заведений находятся в постоянно меняющейся области и сталкиваются с большим количеством ограничений, потребность в гибкости и доступности таких процессов растет [22, 2].
Одной из наиболее важных и распространенных задач планирования в учебных заведениях является планирование расписания занятий [11]. Данная задача хорошо исследованна и неоднократно решалась, однако большинство разработок посвящены статическим задачам планирования расписания до начала учебного процесса [12], последующее же управление им обычно осуществляется вручную. Динамичность ресурсов и учебных планов усиливает необходимость в управлении и оптимизации учебного расписания непосредственно в течение образовательного процесса [2]. При этом из-за объемов данных, которые необходимо учитывать при принятии решений об изменениях в расписании, ручное управление становится сложным и трудоемким процессом [5].
Целью настоящей работы является разработка инструмента, позволяющего управлять и оптимизировать учебное расписание в течение всего учебного семестра. Предполагается, что инструмент позволит настраивать расписание под конкретные текущие ограничения и ресурсы.
Для выполнения работы необходимо решить следующие задачи:
• Оптимизация должна оказывать минимальное воздействие на текущий вариант расписания, так как сильное перераспределение ресурсов нежелательно;
• Система должна предоставлять возможность внесения новых ограничений и конфигурации существующих;
• Пользователям системы должны быть доступны результаты анализа текущего расписания.
Так как почти все методы и алгоритмы, используемые для задачи составления расписания, являются оптимизационными, в данной работе было принято решение проанализировать существующие подходы составления расписания относительно применимости для решения задачи оптимизации расписания со внесением минимальных изменений, и модифицировать выбранный алгоритм.
В первой главе работы произведен анализ предметной области, выявлены существующие алгоритмы оптимизации расписания, среди них выбран подходящий для использования. Также рассмотрены существующие решения проблемы.
Вторая глава включает в себя описание реализации обработки и задания ограничений и алгоритма оптимизации расписания, модифицированного под задачу управления им.
В третьей главе будут описаны структура и функциональность разработанного веб-приложения, используемые технологии и интерфейс пользователя.
В ходе работы была разработана система, позволяющая управлять и оптимизировать расписание учебных курсов в течение образовательного процесса.
В рамках разработки системы была спроектирована архитектура ограничений расписания и реализована их обработка, позволяющая конфигурировать и изменять ограничения в системе. Также был реализован алгоритм оптимизации расписания, выбранный на основе анализа методов, применяемых для задачи составления расписания, и модифицированный под задачу, поставленную в работе. Было разработано веб-приложение, позволяющее использовать данный функционал и предоставляющее вебинтерфейс для управления расписанием.
Дальнейшее развитие работы предполагает реализацию в оптимизаторе исправлений конкретных нарушений ресурсных ограничений для лучшего удовлетворения жестких ограничений и реализацию API системы. Также необходимо рассмотреть вопрос улучшения производительности реализованного оптимизатора расписания. На основе системы возможна реализация анализа влияния факторов расписания на показатели учебного процесса, такие как успеваемость студентов.
