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

Глава 3. Алгоритмы автоматического составления расписания 
3.1. 
Существующие алгоритмы для автоматического составления 
расписания 
Самым простым в реализации алгоритмом автоматического составления 
расписания является алгоритм полного перебора, при котором по данным, хранящихся в 
базе данных, необходимо пробежаться не один раз. Т.е. определяется текущий класс и для 
него составляется расписание, потом следующий и так далее, причем постоянно проверяя 
занятость кабинета и учителя, а при выборе предмета «физкультура» еще и занятость 
спортзалов. 
Рисунок 8. Блок-схема алгоритма перебора для автоматического составления расписания 
Данный алгоритм хорошо подходит только при небольшом количестве данных по 
классам, учителям, кабинетам и предметам. Т.е. идеально подходит для начальных школ, 
в которых учеба проходит на 1-4 параллелях. Для составления расписания в средних 
образовательных учреждениях (учеба во всех параллелях с 1 по 11) данный алгоритм 
потребует в несколько раз больше времени из-за большего количества данных по 
учителям, аудиториям, классам и предметам. Даже при условии использования данных в 
виде объединенного кортежа, состоящего из атрибутов класс, предмет, учитель, базовая 

---

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

---

19 
алгоритмом, основной фишкой которой является скрещивание особей. Он содержит 
несколько шагов:
1) создание новой популяции (создание несколько видов расписания случайным 
образом); 
2) размножение (при котором новая особь унаследует черты своего родителя, 
размножаются все особи); 
3) мутация (замена некоторых параметров как номер кабинета и последовательности 
уроков в конкретном учебном дне); 
4) отбор (выбор более подходящих вариантов расписания для дальнейшего 
использования генетического алгоритма). 
Для алгоритма с нейросетями потребуется большое количество мощности и огромное 
количество данных для ее обучения правильно составлять расписание занятий для 
средних общеобразовательных учреждений, чего на данный момент нет. Поэтому 
использование нейросетей для автоматического составления расписания занятий на 
данный момент не рассматривается. Вместо этого предлагается использовать для решения 
данной задачи алгоритм, основанный на других рассмотренных ранее.