Введение

Процесс формирования учебных расписаний в современных образовательных организациях представляет собой сложную многокритериальную задачу, требующую учёта значительного объёма разнородных данных и множества ограничений. К таким ограничениям относятся нормативные требования, доступность преподавателей и аудиторий, особенности учебных планов, распределение учебной нагрузки, а также предпочтения участников образовательного процесса. Усложнение структуры образовательных программ, рост числа учебных групп и дисциплин приводят к увеличению трудоёмкости и снижению эффективности ручного составления расписаний [1].

Задача автоматического составления учебного расписания относится к классу NP-трудных задач комбинаторной оптимизации, характеризующихся экспоненциальным ростом числа возможных вариантов размещения занятий с увеличением размерности задачи [2]. Формально данная задача может быть представлена как задача удовлетворения ограничений (Constraint Satisfaction Problem, CSP) с последующей оптимизацией по набору критериев, отражающих качество сформированного расписания [3].

В этих условиях особую актуальность приобретает исследование методов оптимизации, применяемых при автоматическом составлении учебных расписаний, и разработка подходов, позволяющих получать качественные решения за приемлемое время. Целью настоящего исследования является анализ существующих методов оптимизации задачи составления учебных расписаний, классификация ограничений и обоснование целесообразности применения комбинированного подхода к её решению.

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

1. Системный анализ процесса составления расписаний и классификация ограничений

1.1. Системный анализ процесса составления расписаний

Процесс автоматического составления учебных расписаний может рассматриваться как сложная система, включающая множество взаимосвязанных элементов. Основными элементами данной системы являются учебные группы, преподаватели, дисциплины, учебные занятия, временные интервалы, аудитории и учебные периоды. Каждый из этих элементов обладает собственными характеристиками и участвует в формировании итогового расписания [4].

Связи между элементами системы формируются в рамках образовательного процесса. Учебные группы изучают определённые дисциплины в соответствии с учебным планом, дисциплины закрепляются за преподавателями, а занятия по дисциплинам должны проводиться в аудиториях, соответствующих требованиям по вместимости и оборудованию. Кроме того, каждое занятие должно быть назначено на определённый временной интервал. Таким образом, процесс формирования расписания представляет собой задачу согласованного распределения множества взаимосвязанных сущностей [5].

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

1.2. Классификация ограничений

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

Жёсткие ограничения представляют собой условия, которые должны соблюдаться в обязательном порядке. Нарушение таких ограничений приводит к формированию некорректного расписания, которое не может быть использовано в реальном учебном процессе. К числу типичных жёстких ограничений относятся ограничения по времени (ни один преподаватель, ни одна учебная группа и ни одна аудитория не могут быть задействованы одновременно в двух и более занятиях), ограничения по аудиторному фонду (вместимость аудитории должна быть не меньше численности группы; тип аудитории должен соответствовать типу проводимого занятия), ограничения по нагрузке (все часы учебной нагрузки, закреплённые за группами и преподавателями, должны быть распределены в расписании), а также нормативные ограничения (занятия не могут назначаться во временные слоты, не входящие в установленный режим работы учебного заведения) [7].

Мягкие ограничения, в отличие от жёстких, не являются строго обязательными для соблюдения, однако их учёт позволяет повысить качество составленного расписания. Нарушение мягких ограничений не делает расписание недопустимым, но снижает его удобство или эффективность. К таким ограничениям могут относиться предпочтения преподавателей (желательные дни и временные слоты для проведения занятий), равномерность нагрузки (отсутствие «окон» у учебных групп и преподавателей; равномерное распределение занятий по дням недели), а также компактность расписания (минимизация переходов между корпусами в течение одного учебного дня) [8].

При автоматическом составлении расписаний мягкие ограничения обычно учитываются в виде критериев оптимизации, позволяющих выбирать наиболее предпочтительное решение среди множества допустимых вариантов. Особую сложность в задаче составления расписаний представляют конфликты ограничений, возникающие в ситуациях, когда выполнение одного ограничения затрудняет или делает невозможным выполнение другого [9].

2. Обзор методов оптимизации задачи составления расписаний

2.1. Детерминированные методы

К числу детерминированных методов относятся методы полного перебора и методы ветвей и границ. Метод полного перебора предполагает рассмотрение всех возможных вариантов размещения занятий, однако его применение на практике ограничено экспоненциальным ростом числа комбинаций. Для задачи составления расписания с n занятиями, m временными слотами и k аудиториями общее число вариантов составляет , что при реальных размерах задачи (сотни занятий, десятки слотов и аудиторий) делает полный перебор практически неосуществимым [10].

Метод ветвей и границ позволяет существенно сократить пространство поиска за счёт отсечения заведомо неоптимальных решений. Данный метод строит дерево решений и использует оценочные функции для определения границ, позволяющих отсекать ветви, не содержащие оптимального решения. Однако при увеличении размерности задачи эффективность метода ветвей и границ также снижается, поскольку размер дерева поиска остаётся экспоненциальным в худшем случае [11].

2.2. Эвристические методы

Эвристические методы основываются на использовании правил и стратегий, позволяющих направлять процесс построения расписания без гарантии нахождения глобально оптимального решения. Одним из распространённых подходов является жадный алгоритм, при котором занятия последовательно размещаются в наиболее подходящие временные слоты с учётом текущего состояния системы ограничений [12].

Жадный алгоритм обеспечивает высокую скорость работы и способен построить допустимое решение, удовлетворяющее всем жёстким ограничениям, за линейное или полиномиальное время. Однако выбор локально оптимальных решений на каждом шаге может привести к субоптимальному итоговому результату. Для повышения качества решения применяются различные стратегии упорядочивания занятий перед размещением, например, сортировка по убыванию сложности (количество групп, требуемая вместимость аудитории, недельная нагрузка) [13].

2.3. Метаэвристические методы

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

Генетические алгоритмы моделируют процессы естественного отбора и эволюции. В рамках данного подхода каждое расписание представляется в виде особи (хромосомы), а процесс оптимизации включает операции селекции, кроссинговера и мутации. Целевая функция определяет «приспособленность» решения и учитывает степень нарушения мягких ограничений. Данный метод позволяет эффективно исследовать большое пространство решений, однако требует настройки параметров (размер популяции, вероятность мутации, критерий остановки) и может обладать высокой вычислительной сложностью [15].

Метод имитации отжига основан на аналогии с физическим процессом охлаждения металлов. Алгоритм допускает временное ухудшение решения с целью выхода из локальных минимумов, постепенно снижая вероятность таких переходов. Это позволяет находить более качественные решения по сравнению с простыми эвристиками, особенно при наличии сложных конфликтов ограничений [16].

Методы локального поиска предполагают последовательное улучшение текущего решения путём внесения небольших изменений, таких как перестановка занятий или изменение временных слотов. К данной группе относятся алгоритмы восхождения на холм, табу-поиск и различные гибридные подходы. Их основным преимуществом является относительная простота реализации и высокая скорость сходимости, однако они могут застревать в локальных оптимумах [17].

2.4. Методы целочисленного линейного программирования

В последние годы активно применяются методы, основанные на формализации задачи в виде целочисленного линейного программирования (Integer Linear Programming, ILP). В рамках данного подхода задача представляется системой линейных ограничений и целевой функции, а решение находится с использованием специализированных оптимизационных решателей (CPLEX, Gurobi, OR-Tools). Данный метод обеспечивает строгое математическое обоснование и способен находить оптимальные решения для задач ограниченной размерности, однако его применение ограничено вычислительными ресурсами при больших размерах задачи [18].

2.5. Сравнительный анализ методов оптимизации

Сравнительный анализ основных методов оптимизации представлен в таблице 1.

Таблица 1

Сравнительный анализ методов оптимизации

Анализ представленных данных позволяет сделать вывод о том, что для задач составления учебных расписаний реальной размерности наиболее целесообразным является применение комбинированного подхода, сочетающего преимущества различных методов. На первом этапе может применяться эвристический алгоритм для быстрого построения допустимого расписания, удовлетворяющего всем жёстким ограничениям. На втором этапе рекомендуется использовать метаэвристические методы или локальный поиск для улучшения качества решения с учётом мягких ограничений [19].

3. Математическая модель задачи составления расписания

3.1. Формализация задачи

Задача автоматического составления учебного расписания может быть формализована следующим образом. Пусть задано множество учебных поручений , где каждое поручение  характеризуется преподавателем , дисциплиной , учебными группами , типом занятия  и недельной нагрузкой  (в академических часах). Каждое поручение требует размещения  занятий в неделю.

Множество временных слотов  представляет собой фиксированные интервалы времени проведения занятий (например, пары в определённые дни недели). Множество аудиторий  характеризуется вместимостью cap( ) и типом оборудования.

Жёсткие ограничения формализуются как условия, которые должны выполняться для любого допустимого расписания:

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

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

Тип аудитории: аудитория  должна соответствовать типу занятия  (например, лекционная, компьютерный класс, лаборатория).

Недоступность ресурсов: если преподаватель , группа g или аудитория  недоступны в слоте , назначение в данный слот запрещено.

Полнота нагрузки: все поручения из множества P должны быть размещены в расписании.

3.2. Целевая функция оценки качества расписания

Для оценки качества расписания с учётом мягких ограничений предлагается следующая целевая функция:

, где P — оценка предпочтения преподавателя (положительное значение для предпочтительных слотов, отрицательное для нежелательных); G — добавляемое количество окон (разрывов между занятиями одного ресурса в течение дня); L — номер пары, отражающий штраф за позднее занятие; S — признак занятия в субботу; C — избыточная вместимость аудитории (разность между вместимостью аудитории и численностью группы); T — текущая дневная нагрузка преподавателя; R — суммарная дневная нагрузка учебных групп; Wp, Wg, Wl, Ws, Wc, Wt, Wr — соответствующие весовые коэффициенты, определяемые пользователем в зависимости от приоритетов образовательной организации.

Целевая функция является аддитивной свёрткой частных критериев качества и позволяет гибко настраивать характер формируемого расписания путём изменения весовых коэффициентов. При Wp > Wg система будет отдавать предпочтение удовлетворению пожеланий преподавателей, при Wg > Wp — минимизации окон и т.д.

3.3. Процедура оптимизации

Предлагаемая процедура оптимизации включает следующие этапы:

Подготовка исходных данных: сбор информации о преподавателях, группах, дисциплинах, аудиториях, временных слотах, ограничениях недоступности и предпочтениях.

Формирование начального допустимого решения: применение жадного алгоритма с эвристическим упорядочиванием поручений по убыванию сложности. На каждом шаге для текущего поручения перебираются все допустимые пары (временной слот, аудитория) и выбирается вариант с максимальным значением целевой функции.

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

Проверка соблюдения жёстких ограничений: валидация полученного расписания на отсутствие конфликтов ресурсов и нарушений нормативных требований.

Оценка качества: расчёт значений частных критериев и общей оценки расписания.

Завершение процесса при достижении заданного критерия остановки (временного ограничения или стабилизации результата).

4. Обсуждение результатов

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

Метаэвристические методы (генетические алгоритмы, имитация отжига, локальный поиск) обеспечивают компромисс между качеством решения и вычислительными затратами. Генетические алгоритмы эффективны для исследования большого пространства решений, но требуют тщательной настройки параметров. Метод имитации отжига хорошо справляется с локальными оптимумами, однако скорость сходимости зависит от выбора функции охлаждения. Локальный поиск обеспечивает быстрое улучшение решения, но подвержен застреванию в локальных оптимумах.

Методы целочисленного линейного программирования обеспечивают строгое математическое обоснование и способны находить оптимальные решения для задач ограниченной размерности. Однако для задач составления расписаний реальных образовательных организаций (сотни занятий, десятки групп и преподавателей) применение ILP-решателей может потребовать значительных вычислительных ресурсов и времени.

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

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

Заключение

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

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

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

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

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