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

Авторы: Безгинов А.Н., Трегубов С.Ю.

Источник: Научная библиотека КиберЛенинка

УДК 517.977.58

А. Н. Безгинов, С. Ю. Трегубов КОМПЛЕКС АЛГОРИТМОВ ПОСТРОЕНИЯ РАСПИСАНИЯ ВУЗА

ЧАСТЬ 1. СИСТЕМА ОЦЕНКИ КАЧЕСТВА РАСПИСАНИЯ НА ОСНОВЕ НЕЧЕТКИХ МНОЖЕСТВ,

ОСОБЕННОСТИ АЛГОРИТМА ПОИСКА ОПТИМАЛЬНОГО РАСПИСАНИЯ

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

A new approach for evaluating the quality of University timetables is proposed. This approach uses a multicriterion expert system with two quality indexes: the average penalty imposed on timetabling and highest penalty imposed on one of the constraints. The system based on a series of intelligible rules and use the algorithms of fuzzy logic for getting the final evaluation of timetabling was created. An algorithm for searching a set of Pareto optimal timetables based on the Pareto simulated annealing algorithm is constructed.

Ключевые слова: составление расписания вуза, оценка качества расписания, нечеткая логика, парето-имитации отжига.

Key words: university course timetabling, evaluating the quality of timetable, fuzzy logic, Pareto simulated annealing.

Введение

Задача построения расписания занятий для вуза относится к классу NP-полных многокритериальных оптимизационных задач. Ввиду неэффективности точных методов для решения задач данного класса при разработке систем автоматизированного составления расписаний занятий применяют эвристические методы, с помощью которых найти оптимальное решение (даже если понятие «оптимального» решения четко определено), как правило, невозможно. В рассматриваемом же случае ситуация усугубляется многокритериальностью задачи. В настоящей работе под «оптимальным» мы будем понимать любое парето-оп-тимальное решение. Соответственно, обобщенно назначение создаваемого алгоритма составления расписания вуза сформулируем так: алгоритм должен обеспечивать поиск некоторого подмножества множества парето-оптимальных решений, причем совокупность найденных решений должна быть, во-первых, обозримой для диспетчера, использующего алгоритм, и, во-вторых, отображать характер всего парето-множества.

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

1) построение одного или множества опорных допустимых расписаний;

2) оценка качества данного расписания;

3) поиск подмножества парето-оптимальных расписаний путем последовательного изменения текущего расписания (или множества расписаний) в направлении его (их) улучшения в соответствии с принятыми показателями качества.

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

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

1. Система оценки качества расписания

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

Сформулируем качественное понимание «справедливости» расписания: будем называть его справедливым, если среди субъектов — участников учебного процесса нет такого, чьи интересы учтены значительно хуже других. Тогда вместо одного скалярного показателя качества расписания целесообразно использовать два:

• средневзвешенную оценку штрафов за полное или частичное невыполнение требований, предъявляемых к расписанию;

• наибольший штраф среди штрафов, назначаемых за полное или частичное невыполнение требований участников расписания.

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

1) смысловой функцией, которая дает обобщенную характеристику отклонения текущего расписания от ситуации идеального выполнения требования;

2) лингвистической переменной «приоритет требования», например с множеством значений T = {«высокий», «средний», «низкий»};

3) весом требования ю е [0,1];

4) областью допустимых значений смысловой функции;

5) целевой функцией требования смысловой функции. При этом полагаем, что требования, целевые функции которых в изучаемом расписании равны 1, полностью не выполнены, 0 — полностью выполнены.

Отметим, что семантика термина «целевая функция» в настоящей работе отличается от семантики, принятой в алгоритмах четкой скалярной оптимизации. Здесь «четкие» целевые функции dr(zr), которые соответствуют различным требованиям, это только промежуточные конструкции при построении обобщенных показателей качества расписания, позволяющие формализовать предпочтения субъектов — участников расписания. В целом же алгоритм итерационного построения подмножества парето-оптимальных расписаний строится в рамках методологии нечетких алгоритмов.

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

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

Для исследования эффективности предложенного подхода, включающего систему оценки расписания на базе нечетких предикатных правил и алгоритм поиска множества парето-оптимальных расписаний на основе PSA, в среде C++ был разработан программный комплекс формирования оптимального расписания. С помощью генератора тестовых задач составления расписания, входящего в состав указанного программного комплекса, было порождено большое количество тестовых задач различной размерности (по числу I занятий в неделю) и сложности (по характеру нежестких требований к расписанию со стороны субъектов — участников расписания). Зависимость доли P от числа занятий I оценивалась на основе анализа всего множества тестовых задач и задач, при решении которых нежесткие требования субъектов — участников расписания были выполнены полностью. Пример такой зависимости показан на рисунке 2.

Пример иллюстрирует то, что созданный программный комплекс достаточно успешно справляется с задачей поиска расписания, удовлетворяющего трудно совместимым требованиям субъектов — участников расписания. Долю задач, в которых не удается полностью выполнить все требования участников, в принципе можно было бы уменьшить, изменив подходящим образом некоторые исходные данные задачи и запустив процесс поиска заново. Дополнительно эффективность предложенного подхода была подтверждена при решении реальных задач составления расписания для филиала ГОУ МГИУ в Сергиевом Посаде. В филиале имеется 29 групп студентов, обучающихся по четырем специальностям, 73 преподавателя и 17 аудиторий. Проведенные вычислительные эксперименты показали, что разработанному программному комплексу для построения оптимального расписания этого вуза требуется ~1,5 часа вычислительного времени на компьютере с процессором ЛМБ ЛШ1оп64 3800+. При этом экспертами, участвующими в вычислительных экспериментах, было отмечено, что в итоговых расписаниях все требования, выделенные ими как высокоприоритетные, были удовлетворены в максимально возможном объеме.

Заключение

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

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

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

1. Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы. М., 2004.

2. Безгинов А. Н., Трегубов С. Ю. Система оценки расписания на основе нечетких множеств || Известия МГИу. 2007. № 1 (б). С. 2 — S.

3. Czyak P., Hapke M., Jaszkiewicz A. Application of the Pareto-simulated annealing to the multiple criteria shortest path problem I Institute of Computing Science, Poznan University of Technology. Poznan, 1994.

4. Jaszkiewicz A. Multiple objective metaheuristic algorithms for combinatorial optimization | Poznan University of Technology. Poznan, 2001.

5. Kirkpatrick S., Gelatt C. D., Vecchi M. P. Optimization by simulated annealing // Science. 1983. Vol. 220, N4598. P. 671 — 680.

6. Serafim P. Simulated annealing for multiple objective optimization problems // Multiple criteria decision making: proc. of the Xth intern. conf. Taipei, 1994. P. 283 — 292.

Об авторах

Анатолий Николаевич Безгинов — д-р техн. наук, проф., филиал Московского государственного индустриального университета, г. Сергиев Посад, e-mail: mail@spf-mgiu.ru.

Сергей Юрьевич Трегубов — ассист., филиал Московского государственного индустриального университета, г. Сергиев Посад, e-mail: s.tregubov@gmail.com. Научная библиотека КиберЛенинка: http://cyberleninka.ru/article/n/kompleks-algoritmov-postroeniya-raspisaniya-vuza-chast-1-sistema-otsenki-kachestva-raspisaniya-na-osnove-nechetkih-mnozhestv#ixzz2V3X0H86z