ВВЕДЕНИЕ 4
ГЛАВА 1. АНАЛИЗ ПРЕДМЕТНОЙ ОБЛАСТИ 6
1.1. РАСПИСАНИЕ В ОБРАЗОВАНИИ 6
1.1.1. Компоненты и участники расписания 7
1.1.2. Роль индивидуализации при составлении расписания 8
1.2. ТЕОРИЯ РАСПИСАНИЙ 9
1.2.1. Классификация задач теории расписания и определение класса задачи
составления учебного расписания в ВУЗе 10
1.2.2. Методы решения задачи построения расписания 12
1.2.3. Существующие решения задачи построения учебного расписания .... 15
1.2.4. Выбор, обоснование и описание алгоритма для составления учебного
расписания в контексте индивидуализации 18
ГЛАВА 2. ГЕНЕТИЧЕСКИЙ АЛГОРИТМ В КОНТЕКСТЕ ГЕНЕРАЦИИ
РАСПИСАНИЯ С УЧЕТОМ ИНДИВИДУАЛИЗАЦИИ 20
2.1. ВХОДНЫЕ ДАННЫЕ 20
2.2. РЕАЛИЗАЦИЯ АЛГОРИТМА 20
ГЛАВА 3. РЕАЛИЗАЦИЯ WEB-ПРИЛОЖЕНИЯ 34
3.1. СТРУКТУРА ПРИЛОЖЕНИЯ 34
3.2. СТРУКТУРА REST API 34
3.3. ФУНКЦИОНАЛ И USER INTERFACE 38
ГЛАВА 4. ТЕСТИРОВАНИЕ АЛГОРИТМА ГЕНЕРАЦИИ 45
4.1. ТЕСТОВЫЕ ДАННЫЕ 45
4.2. РЕЗУЛЬТАТЫ ТЕСТИРОВАНИЯ 45
4.3. ОБЩИЙ ВЫВОД ПО РЕЗУЛЬТАТАМ ТЕСТИРОВАНИЯ 55
ВЫВОД 56
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 57
Приложение 1 59
Приложение 2 60
Приложение 3 61
Приложение 4 66
Приложение 5 67
Приложение 6 69
Приложение 7 70
Приложение 8
Образование является одной из самых обширных сфер жизни современного общества. На данный момент в нем задействовано около пятидесяти миллионов преподавателей и более миллиарда учащихся. Велика социальная роль образования: перспективы человеческого развития во многом зависят от его эффективности, результативности, направленности. С каждым годом отношение к различным видам образования меняется. В современном мире, образование, в первую очередь высшее, рассматривается в качестве ведущего фактора экономического и социального прогресса [1].
Одной из наиболее важных и распространенных задач, возникающих в ходе планирования и оптимизации учебного процесса в учебных заведениях, является составление расписания занятий. Это связано с тем, что от него зависит степень усвоения нового материала студентами, продуктивность работы преподавателей, разумное использование материальных ресурсов: оборудования, аудиторного фонда [2].
На данный момент процесс образования в ВУЗах России стандартизирован и расписание занятий составляется согласно единому учебному плану конкретного университета для специальности, выбранной студентом. Но последние исследования в этой сфере все чаще говорят о необходимости внедрения индивидуализации в образование. Под индивидуализацией понимается организация учебного процесса, учитывающая индивидуальные особенности каждого студента. Это помогает создать оптимальную среду для максимальной реализации возможностей учащегося. Кроме того, индивидуализация влияет на мотивацию, самовыражение, самоанализ [3].
Очевидно, что при большом количестве пожеланий от студентов и преподавателей, ручное составление оптимального расписания невозможно.
Задача автоматической генерации неоднократно решалась для классических случаев. Также осуществлялись попытки ее решения с учетом некоторых особенностей, например, пожеланий преподавателей.
Проблема заключается в том, что существующие алгоритмы генерации расписаний не учитывают различные типы индивидуальных ограничений участников университета в едином формате и не конфигурируются в процессе выполнения. Следовательно, целью данной работы является разработка такого генератора и инструмента, для управления им.
В первой главе будет произведен анализ предметной области, выявлены существующие алгоритмы генерации расписаний и выбран наиболее подходящий для решения поставленной проблемы. Также в этой главе будут рассмотрены существующие решения (аналоги), выделены их преимущества и недостатки.
Вторая глава включит в себя описание реализации генерации расписания выбранным алгоритмом в контексте индивидуализации.
В третьей главе будут описаны структура web-приложения, используемые технологии, функционал, интерфейс пользователя и реализация основных методов.
Четвертая глава содержит результаты тестирования реализованного алгоритма и выводы по каждому тесту.
В ходе выполнения работы были рассмотрены особенности расписания в сфере образования, роль индивидуализации в ней, изучена теория расписаний, проанализированы алгоритмы генерации расписаний и существующие решения. Для генерации учебного расписания в контексте индивидуализации был выбран генетический алгоритм.
Классический генетический алгоритм был адаптирован под предметную область путем учета ограничений, составленных на основе цифровых представлений, индивидуальных планов, рекомендаций и пожеланий участников учебного процесса.
Для настройки алгоритма и управления им было реализовано web- приложение. Оно позволяет заполнять конфигурацию расписания, параметры генетического алгоритма, включать и выключать типы ограничений (как до генерации, так и в ее процессе), сохранять сгенерированные расписания.
Реализованный алгоритм был протестирован на различных типах ограничений. Общий тест включил в себя 140 пожеланий, 80% из которых были выполнены. Это значит, что алгоритм способен учитывать значительную долю пожеланий и рекомендаций от сущностей университета.
