В ПГНИУ создали программу для составления "идеального" расписания

Ученые ПГНИУ предложили и описали новый подход к составлению учебного расписания в школе на основе «генетических» алгоритмов. Теперь для занятий расписание можно генерировать автоматически, без «окон» и с учетом занятости преподавателей.

Применяя знания комбинаторики, дискретной математики и теории графов, доцент кафедры математического обеспечения вычислительных систем механико-математического факультета ПГНИУ Алексей Городилов и студент той же кафедры Роман Макурин создали алгоритм составления учебного расписания. Этот алгоритм может адаптироваться к условиям конкретного учебного заведения. На его основе авторы создали программу, которая была проверена на реальных данных и показала корректность и преимущества ее использования.

Сейчас существуют программы для составления учебного расписания (например, aSc Расписание, ХроноГраф), но они обладают недостатками: перегруженным интерфейсом, неудобством ввода исходной информации, составлением не оптимального расписания. Кроме того, во многих учебных заведениях стараются учесть индивидуальные предпочтения преподавателей (методические дни, отсутствие первых и последних уроков), но программы не могут этого учесть, и диспетчерам зачастую приходится вручную корректировать итог работы.

«Составление "идеального" расписания – это сложная комбинаторная задача, которую чаще всего решали с помощью приближенных алгоритмов. Мы в своей работе опирались на генетический алгоритм, который успешно применяют в задачах с множеством критериев. Тестировали мы свою систему на учебном плане реальной школы – 15 классов, 29 учителей, 438 уроков. У каждого класса нагрузка по 28–30 уроков в неделю. При применении алгоритма расписание не содержит "окон"», – рассказал разработчик.
 
Далее ученые планируют улучшать продукт: увеличить число критериев, по которым можно осуществить настройку алгоритма, реализовать пользовательский интерфейс для изменения критериев оптимальности и создать возможность корректировки расписания вручную с помощью перетаскивания (Drag&Drop).

Ранее мы сообщали, что Алексей Городилов совместно с магистрантом мехмата создали обучающую систему с автоматической генерацией задач для контроля знаний и навыков студентов «ALIS».

Пресс-служба