ГИБРИДНЫЙ АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ СОСТАВЛЕНИЯ ОПТИМАЛЬНОГО УЧЕБНОГО РАСПИСАНИЯ
Галузин Константин Станиславович, Столбов Валерий Юрьевич
Пермский государственный технический университет
Рассмотрена задача автоматизации составления оптимального учебного расписания в рамках разработанной информационной системы «Школа». Задача поставлена как задача распространения нечетких ограничений с приоритетами. Предложен гибридный алгоритм решения задачи, основанный на методах теории нечетких множеств, математического программирования и методах распространения ограничений.
обсудить на форуме
написать автору
Цель работы — автоматизация составления оптимального учебного расписания в рамках разработанной информационной системы «Школа»[1].
Предлагаемая постановка задачи отличается от встречавшихся ранее в литературе[2] гибкостью в отражении требований диспетчеров, учетом предпочтений преподавателей и учебных групп, учетом многокритериальности задачи оптимизации. Учтена возможная нечеткость в формулировке ограничений, предпочтений и целевых функций, что позволяет применить аппарат теории нечетких множеств и сформулировать задачу как задачу распространения нечетких ограничений с приоритетами.
Для учета сложного распорядка учебного процесса (подгруппы и т.д.) вводятся понятия обобщенных преподавателей, групп и аудиторий. Допустимым назовем расписание, удовлетворяющее четырем жестким ограничениям: каждый преподаватель, группа и аудитория не могут быть задействованы дважды в один момент времени, и должны выполняться требования их недоступности в некоторые периоды времени.
Критерии качества составляемого расписания специфичны для каждого образовательного учреждения, поэтому кроме двух общих критериев оптимальности (учет интересов учащихся и преподавателей) должны быть сформулированы наборы частных критериев оптимальности.
Количество ресурсов (аудиторий, преподавателей, групп), требуемое для проведения каждого часа занятий, известно заранее, поэтому задачу можно декомпозировать и решать в два этапа: на первом этапе составляется расписание занятий по времени, на втором производится назначение аудиторий с применением метода ветвей и границ.
Допустимость решений на первом этапе обеспечивается решателем, основанным на методах распространения ограничений и математического программирования, и поддерживающим глобальные ограничения в процессе поиска, управляемом эвристиками, что важно для получения качественных допустимых расписаний.
Оптимизация полученных решений в интерактивном режиме обеспечивается применением методов локального поиска, управляемых метаэвристикой, имитирующей физический процесс охлаждения.
Для доказательства близости полученных решений к глобальному оптимуму реализован также полный метод решения, основанный на сочетании методов ветвей и границ, математического программирования и распространения ограничений.
Разработанный модуль обладает высокой универсальностью и может применяться диспетчерами для автоматизации составления учебного расписания в образовательных учреждениях различного типа.
Литература:
- Галузин К.С., Столбов В.Ю. Разработка модуля для автоматизации составления оптимального учебного расписания в рамках единой информационной системы образовательного учреждения//Известия Белорусской инженерной академии,- 2003.-№1(15)/2.-С.90-92
- Harald Meyer auf’m Hofe. Nurse rostering as constraint satisfaction with Fuzzy Constraints and Inferred Control Strategies, In DIMACS Series in Discrete Mathematics and theoretical computer science, 2000, pages 257-272.