Методы решения задачи о планировании расписания учебных занятий: дипломная работа / Дарья Владимировна Вусик; БГУ, Факультет прикладной математики и информатики, Кафедра дискретной математики и алгоритмики; науч. рук. Молочко И. П.

Abstract

РЕФЕРАТ Дипломная работа, 34 страницы, 1 иллюстрация, 10 таблиц, 4 источника, 4 приложения. Ключевые слова: СОСТАВЛЕНИЕ РАСПИСАНИЙ, ЦЕЛОЧИСЛЕННОЕ ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ, ЭВРИСТИКИ ЛОКАЛЬНОГО ПОИСКА, МОДЕЛЬ ЦЛП, ИМИТАЦИЯ ОТЖИГА, АЛГОРИТМ LOCAL-MIP, ОПТИМИЗАЦИЯ. Объект исследования: алгоритмы и методы для автоматизированного составления учебных расписаний. Предмет исследования: разработка и анализ эффективности решателя HiGHS в комбинации с эвристиками локального поиска. Цель работы: исследование возможностей решателя HiGHS и модифицированных эвристик для решения задач составления расписаний, а также разработка ЦЛП модели , учитывающей реальные требования образовательного процесса. Методы исследования: формализация задачи в виде целочисленной линейной модели, интеграция эвристик (Local-MIP, имитация отжига) в решатель HiGHS, проведение вычислительных экспериментов с различными конфигурациями алгоритмов, сравнительный анализ времени решения, качества и допустимости расписаний. Результаты: разработана ЦЛП модель для составления учебных расписаний, учитывающая ограничения по аудиториям, преподавателям, группам и временным слотам; Реализованы две дополнительные версии алгоритма Local-MIP: Local-MIP с приоритезацией бинарных переменных и гибридная версия с имитацией отжига; Все вариации эвристик были интегрированы в решатель HIGHS; Проведено тестирование на задачах различных масштабов и проведен сравнительный анализ результатов тестирования. Области применения: разработанные методы могут быть использованы в системах автоматизации составления расписаний для учебных заведений, корпоративных тренингов и других сфер, где требуется баланс между качеством решений и временными ограничениями.