Разработка программы автоматизированного составления расписания в школе на основе генетического алгоритма

Краткое вступление

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

Цель работы

Разработка программы составления расписания на основе генетического алгоритма с учётом большого числа входных параметров и ограничений.

Задачи

1. Выбрать метод и описать алгоритм решения многокритериальной задачи оптимизации для составления расписания.
2. Реализовать и протестировать алгоритм многокритериальной оптимизации в виде программы.
3. Провести сравнительный анализ полученных результатов с действующим расписанием в школе.

Описание работы

При создании расписания необходимо учитывать множество противоречащих друг другу факторов: от наличия аудиторного фонда до пожеланий педагогов. Задача ручного составления расписания при этом усложняется. Автоматизация процесса поможет решить проблему создания расписания в условиях повышения требований к качеству учебного процесса. К важнейшим критериям качества программного продукта можно отнести: удобный интерфейс, гибкость настройки, эффективность алгоритма поиска, функции составления отчётов. Многие решают вышеизложенную задачу с помощью расстановки ячеек расписания по каким-то определённым правилам, которые гарантировали бы соответствие расписания требованиям. Но не всегда удаётся достигнуть желаемого результата. Существующие решения основаны на методах линейной оптимизации, которые позволяют получать «черновые решения», требующие существенных доработок специалистом. В настоящем проекте реализован другой подход: каждый вариант расписания есть некоторый способ распределения уроков по сетке, который будет оцениваться оптимизируемой «общей функцией». «Общая функция» композируется из ранжируемых критериальных функций. Каждая критериальная функция отвечает за определённое свойство: сокращение количества переходов между кабинетами для учителей или учеников, привязка уроков к кабинетам и т. д. Критериальные функции были определены в результате анализа требований администрации и СанПиН, анкетирования учителей и учащихся. Обычно в образовательной организации придерживаются принципа «менторства», т. е. учитель ведёт те же классы, что и в прошлом году. Поэтому исходными данными в программе являются именно чёткие установки, например, у какого класса с каким учителем математики должно быть определённое количество уроков. Рассмотрев различные алгоритмы оптимизации, выбрали генетический алгоритм. Он гибок, прост в реализации, но требует больших вычислительных мощностей и не имеет конечного времени работы, поскольку основан на случайном выборе. В терминах этого алгоритма проект выглядит так: ген − урок в сетке расписания, генотип − вариант расписания, фенотип − значение «Общей функции» от генотипа. Далее использованы следующие термины: особь − численный фенотип и генотип, популяция − вектор особей. Для реализации генетического алгоритма был выбран язык программирования Rust; утилиты, генерирующие конфигурации и обрабатывающие исходные данные, написаны на Python.

Оснащение и оборудование, использованное при создании работы

Для разработки использованы программы IntelliJ IDEA + IntelliJ Rust. Оборудование для тестовых запусков программы выдано системными администраторами: сервер с процессором Xeon и ОС Windows.

Существенные результаты

1. Разработан программный комплекс автоматизации составления расписания.
2. Создана документация по критериальным функциям и программному обеспечению.
3. Получено несколько вариантов расписания.

Перспективы использования результатов работы

Планируется:

1. оптимизировать существующий код с учётом новых предпочтений;
2. протестировать программу в одном из корпусов нашей школы;
3. реализовать Web-интерфейс для удобства конечного пользователя;
4. реализовать поддержку динамически подключаемых критериальных функций.

Сотрудничество с вузом/учреждением при создании работы

ЗАО «КРОК»