Привет, Хабр! Я хочу рассказать о том, как я создал программу для составления расписаний учебных заведений — СуперЗавуч.

Введение

СуперЗавуч — современная программа для составления расписаний уроков школ, лицеев и колледжей. Программа позволяет создать расписание за несколько минут и имеет много параметров для конфигураций.

Идея

Идея состояла в создании приложения, которое берёт на себя всю рутину по составлению расписания занятий — быстро, с минимумом действий со стороны пользователя и с максимально качественным итоговым результатом.

Проблема составления расписаний

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

Аналоги

Существует много аналогов, которые также позволяют составить школьное расписание. Но скорее всего они будут платными или очень плохо справляться со своей задачей.

1С Автоматизированное составление расписания: платная лицензия и сложный интерфейс.

Хронограф: бесплатная версия ограничена по количеству классов и функциям.

ProRector: Платное специализированное решение.

Конечно, это не все примеры, но суть вы уловили — программы либо платные, либо с очень урезанным функционалом.

Подробнее о программе СуперЗавуч

Архитектура

Интерфейс программы СуперЗавуч написан на Python 3.11, в качестве библиотеки была использована PyQt5. Алгоритм, позволяющий составлять расписание, написан на C++ для достижения большей производительности.

Гайд, как пользоваться программой

Интерфейс разделён на 10 меню: настройки, классы, учителя, кабинеты, ИИ, константы, группы, запуск, просмотр, экспорт. Пользователь проходит по данным вкладкам последовательно, заполняя требуемую информацию.

В данном меню пользователь вводит базовые настройки (кол‑во рабочих дней, макс. кол‑во уроков, кол‑во параллелей и так далее), для каждого предмета вводится его имя и сложность, а для каждой параллели — кол‑во классов в ней и смена, в которой она учится.

Для каждого класса выставляется количество уроков, которое преподаётся классу в неделю.

Позволяет создавать группы кабинетов, например, группа «Английский язык», в которой будут указаны все кабинеты, в которых он проводится.

В данном меню задаются учителя, их свободное время, предметы и классы, в которых они преподают. Также указываются кабинеты, в которых проводятся уроки.

ИИ‑ассистент может объяснить работу программы, изменять и работать с составленным расписанием, а также импортировать расписание из многих форматов.

Позволяет для определённых классов устанавливать определённые уроки в нужное время, которые не будут изменяться алгоритмом.

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

В меню указываются веса алгоритма, определяющие важность каждого значения и, конечно, сам запуск алгоритма.

Позволяет просмотреть только что составленное расписание относительно классов и относительно учителей.

В данном меню указываются временные промежутки уроков для отображения их в таблице. Кнопки позволяют экспортировать расписание в Excel относительно учителей и классов.

Алгоритм

Я перебрал несколько способов, чтобы создать алгоритм для составления расписаний. В итоге я остановился на температурном отжиге (с использованием графов).

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

Алгоритм основан на том, чтобы минимизировать «значение» полученного в эту итерацию расписания. «Значение» вычисляется как сумма всех параметров, которые могут быть улучшены, таких как кол‑во «окон» у классов и учителей, равное кол‑во суммарной сложности уроков каждый день, окна в расписаниях профильных классов и так далее

Программа позволяет указать веса каждого из параметров, что позволяет регулировать важность отдельных изменений.

Результат

В итоге была реализована программа, позволяющая удобно составлять расписания занятий, работать с классами, учителями, кабинетами, профилями, заморозкой уроков. В СуперЗавуч реализован ИИ‑ассистент, помогающий с составлением расписания. А также реализован алгоритм составления расписаний, основанный на температурном отжиге. Программа написана на Python с использованием PyQt5, алгоритм написан на C++.

Программа составила расписания для моей школы за 2 минуты, при этом в школе 80 учителей и 40 классов. Также в расписание около 130 «окон» у учителей, что в среднем 2 «окна» в неделю.

Ссылки

Я создал сайт, где можно скачать программу, а также здесь находится полная документация по использованию программы. Также ссылка на телеграм‑канал и на GitHub‑репозиторий.