УДК 004.023

Обзор видов ограничений и различных методов планирования и оптимизации расписания в учебных заведениях

Головизов Денис Иванович – студент магистратуры направления «Информатика и вычислительная техника» Самарского государственного технического университета

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

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

Расписание занятий имеет важнейшее значение в организации учебного процесса. От грамотно составленного расписания зависит полнота творческой отдачи и трудовой ритм преподавателей, а также успешность обучения студентов [1].

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

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

Таблица 1. Мягкие и жесткие ограничения.

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

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

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

1. Жадный рандомизированный адаптивный поиск (GRASP – Greedy Randomized Adaptive Search).

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

2. Алгоритм имитации отжига (SA – Simulated Annealing).

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

3. Поиск с запретами (TS – Tabu Search).

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

4. Генетический алгоритм (GA – Genetic Algorithm).

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

Система штрафов является механизмом, позволяющим регулировать процесс оптимизации расписания [2].

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

В таблице 2 приведены сводные данные некоторых из алгоритмов оптимизации составления расписания [3].

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

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

Список литературы

1. Масляев Д. А. Cовременное состояние задачи автоматизации составления оптимального учебного расписания в вузе / Вестник Сыктывкарского университета. Серия 1: Математика. Механика. Информатика. 2022. Выпуск 1 (42). – С. 23-40.
2. Яндыбаева Н.В. Генетический алгоритм в задаче оптимизации учебного расписания ВУЗа // Современные наукоемкие технологии. – 2009. – № 11. – С. 97-98.
3. Кохендерфер У. Алгоритмы оптимизации. – Вильямс, 2020. – 528 с. – ISBN: 978-5-907144-76-7.