ВВЕДЕНИЕ 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 системы. Также необходимо рассмотреть вопрос улучшения производительности реализованного оптимизатора расписания. На основе системы возможна реализация анализа влияния факторов расписания на показатели учебного процесса, такие как успеваемость студентов.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
