Научный журнал
Современные наукоемкие технологии
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 0,940

МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ФОРМИРОВАНИЯ РАСПИСАНИЯ ЭКЗАМЕНОВ ВУЗА

Клеванский Н.Н. 1 Мавзовин В.С. 1
1 ФГБОУ ВО «Саратовский государственный аграрный университет имени Н.И. Вавилова»
Формирование расписания экзаменов вуза может быть сформулировано как задача комбинаторной оптимизации. Задача формирования расписания экзаменов является оптимизационной задачей, которая состоит в распределении множества экзаменов во множестве временных промежутков при соблюдении множества ограничений. Задача является NP-полной и обычно решается с применением эвристических методов. В статье представлены базовые концепции решения задачи формирования экзаменов вуза. Эти концепции реализуют ресурсо-ориентированный подход. Процедура планирования экзаменов использует две последовательно применяемые схемы генерации расписаний. В каждой схеме используются два правила приоритетов – процедур получения решений с использованием многокритериального и многовекторного ранжирования теории принятия решений. Первая схема обеспечивает получение начальных расписаний. Вторая схема оптимизирует начальные решения. Когнитивность кругового представления расписания экзаменов способствовала разработке нового подхода к оптимизации. Основным критерием для оптимизационных процедур предложен критерий равномерности потребления ресурсов. В качестве такого критерия использовано среднеквадратичное отклонение интервалов между экзаменами от средних значений. Приведенные экспериментальные данные демонстрируют способность предлагаемого подхода к получению расписаний достаточно высокого качества.
расписание
заявка
экзамен
схема генерации расписания
правило приоритетов
среднеквадратичное отклонение
методы ранжирования
1. Qu R., Burke E.K., McCollum B. Adaptive automated construction of hybrid heuristics for exam timetabling and graph coloring problems // European Journal of Operational Research. – 2009. – № 198. – Р. 392–404.
2. Malkawi M., Hassan M.A. Hassan O.A. A New Exam Scheduling Algorithm Using Graph Coloring // The International Arab Journal of Information Technology. – 2008. – Р. 80–87.
3. Burke E.K., Bykov Y., Newall J.P., Petrovic S. A time predefined local search approach to exam timetabling problems // IIE Transactions. – 2004. – № 36(6). – Р. 509–528.
4. Abdullah S., Ahmadi S., Burke E.K., Dror M., McCollum B. A tabu based large neighborhood search methodology for the capacitated examination timetabling problem // Operations Research. – 2007. – № 58. – Р. 1494–1502.
5. Caramia, M., Dell’Olmo, P., Italiano, G.F., Novel local-search-based approaches to university examination timetabling // INFORMS Journal of Computing. – 2008. – № 20(1). – Р. 86–99.
6. Eley M. Ant algorithms for the exam timetabling problem. In E.K. Burke & H. Rudovа (Eds.), LNCS: Vol. 3867. Practice and theory of automated timetabling (Patat 2006), 2007. – Р. 364–382. Berlin: Springer.
7. Kahar M.M., Kendall G. A great deluge algorithm for a real-world examination timetabling problem // Journal of the Operational Research Society. – 2013. – Vol.67, № 3. – Р. 116–133.
8. Pillay N., Banzhaf W. An informed genetic algorithm for the examination timetabling problem // Applied Soft Computing. – 2010. – № 10. – Р. 457–467.
9. Thompson J.M., Dowsland K.A. A robust simulated annealing based examination timetabling system // Computer Operational Research. – 1998. – vol. 25. – Р. 637–648.
10. Burke E.K., Eckersley A.J., McCollum B., Petrovic S., Qu R. Hybrid variable neighborhood approaches to university exam timetabling // European Journal of Operational Research. – 2010. – № 206(1). – Р. 46–53.
11. Ho W., Dey P.R., Higson H.T. Multiple criteria decision-making techniques in higher education // International journal of educational management. – 2006. – No. 20(5). – Р. 319–337.
12. Клеванский Н.Н. Парадигма формирования расписаний // Journal of Advanced Research in Technical Science. – 2017. – № 6. – С. 70–75.
13. Клеванский Н.Н. Алгоритмы формирования расписания занятий высших учебных заведений // Фундаментальные исследования. – 2017. – № 10–3. – С. 454–458.
14. Klevanskiy N.N., Antipov M.A., Krasnikov A.A. Cognitive aspects of timetable visualization: support decision making. В сборнике: Сер. «12th International Symposium Intelligent Systems, INTELS’2016». – 2017. – № 103. – P. 94–99.
15. Клеванский Н.Н., Антипов М.А., Красников А.А. Многокритериальная обработка в задачах расписаний // Journal of Advanced Research in Technical Science. – 2016. – № 2. – С. 62–67.

Задача формирования расписания экзаменов является задачей комбинаторной оптимизации, а по своей сложности относится к классу NP-полных задач. Последнее требует для своего решения применения таких эвристических методов, как раскраска графа [1, 2], поиск с запретами [3–5], алгоритмы муравьиных колоний [6], метод «великого» потопа [7], эволюционные алгоритмы [8] и другие [9, 10]. Наиболее близким к предлагаемому в статье способу решения задачи представляется многокритериальный подход [11].

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

Целью данной статьи является представление эвристик в программном решении задачи формирования расписания экзаменов российского вуза.

Аналогично задаче расписания занятий [13] расписание экзаменов связано с распределением трех ресурсов – студенческого контингента, преподавателей и аудиторий. Исходными данными являются формируемые для всех экзаменов сессии заявки с указанием группы, преподавателя и требуемой или желаемой аудитории. Для решения задачи использованы конструктивная эвристика формирования начального расписания SGS1 и оптимизационная эвристика SGS2.

Введем необходимые в математическом моделировании обозначения.

Исходные данные задачи:

klev01.wmf, klev02.wmf, klev03.wmf – множества академических групп, преподавателей и аудиторий;

klev04.wmf – множество заявок на прием экзаменов;

klev05.wmf – множество таймслотов – временных интервалов приема экзаменов, однозначно определяющих номер смены – tn, день недели – td и ее номер – ts.

«Классическая» организация экзаменационной сессии предполагает ее трехнедельную продолжительность с двумя сменами в день, включая воскресенье. В этом случае klev06.wmf, а nt = 42.

Исходные расчетные данные задачи:

klev07.wmf, klev08.wmf, klev09.wmf – количества заявок i-й группы, i-го преподавателя и i-й аудитории;

Переменные задачи:

klev10.wmf – множество экзаменов расписания;

ni, nr – количества включенных и не включенных в начальное расписание экзаменов;

klev11.wmf, klev12.wmf, klev13.wmf – количества включенных в начальное расписание экзаменов i-й группы, i-го преподавателя или i-й аудитории;

Таблица 1

Оценки загруженности заявок на прием экзаменов

i-й группы

i-го преподавателя

i-й аудитории

klev14.wmf (1)

klev15.wmf (2)

klev16.wmf (3)

wi – количество экзаменов в таймслоте ti интервала расписания сессии;

klev17.wmf – номер таймслота проведения i-го экзамена k-й группы при «классической» организации экзаменационной сессии;

klev18.wmf – интервал в таймслотах между i-м и (i + 1)-м экзаменами k-й группы. Для последнего экзамена группы (i + 1)-м экзаменом принимается первый экзамен с увеличением его номера на величину nt.

Для экзаменационной сессии использовано круговое представление (рис. 1), когнитивность [14] которого позволила ввести две оценки равномерности расписания экзаменов.

klev1.tif

Рис. 1. Круговое представление экзаменационной сессии: 1 – кольцевые расписания экзаменов групп; 2 – таймслоты расписания; 3 – экзамены групп; 4 – первые включенные в расписание экзамены групп

Кольцевая оценка равномерности определяет распределение экзаменов группы в своем кольце представления. Радиальная оценка равномерности определяет распределение экзаменов в таймслотах представления. Выражения для определения кольцевых и радиальных оценок равномерности представлены в табл. 2.

Таблица 2

Оценки равномерности экзаменов

k-й группы

i-го таймслота

klev19.wmf (4)

klev20.wmf (5)

Критерий равномерности i-го экзамена расписания k-й группы

klev21.wmf. (6)

Критерии равномерности расписания экзаменов определяются двумя среднеквадратичными отклонениями (табл. 3).

Таблица 3

Критерии равномерности

расписания группы

расписания

klev22.wmf (7)

klev23.wmf (8)

Введем булевы обозначения занятости группы qg, преподавателя ql и аудитории qa.

klev24.wmf klev25.wmf

klev26.wmf

Эвристика SGS1 (формирование начального расписания экзаменов) состоит в цикличном выборе наиболее загруженной заявки и ее включении в расписание так, чтобы минимизировать критерий равномерности группы включаемого экзамена

klev27.wmf (9)

при обязательных ограничениях

klev28.wmf, (10)

klev29.wmf, klev30.wmf, klev31.wmf, (11)

klev32.wmf. (12)

Целевая функция (9) обеспечивает наибольшую возможную равномерность экзаменов группы последней заявки. Ограничение (10) гарантирует включение всех заявок в начальное расписание. Неравенства ограничений (11) исключают возможность одновременного участия любой группы, преподавателя или аудитории более чем в одном экзамене расписания. Ограничение (12) обеспечивает необходимый интервал между ближайшими экзаменами любой группы в начальном расписании при «классической» организации экзаменационной сессии.

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

klev33.wmf. (13)

Обратное многокритериальное ранжирование [15] векторов (13) определяет самую загруженную заявку, которая становится очередным кандидатом dni+1 на включение в начальное расписание. Далее в эвристике SGS1 реализуются следующие действия. Если включаемый в начальное расписание экзамен является первым для группы, то он включается в первый таймслот с минимальным количеством экзаменов и для группы фиксируется множество таймслотов сессии (рис. 2) для размещения остальных экзаменов группы. Выделение этого множества осуществляется на основе ограничения (12). Если экзамен не первый, то из множества выделенных таймслотов выбирается первый с наименьшим значением оценки ki.

klev2.tif

Рис. 2. Диапазоны допустимых таймслотов: 1 – первый включенный в расписание экзамен группы; 2 – допустимые таймслоты для начального расписания; 3 – допустимые таймслоты для оптимизации расписания

Если nr > 0, то переход к следующему циклу конструктивной эвристики. На рис. 3 представлено начальное расписание экзаменов для 50 групп, студенты которых сдают по 5 экзаменов. Программное решение реализовано для «классической» организации экзаменационной сессии. По периметру кругового представления (рис. 3) указаны количества программно определенных экзаменов в каждом таймслоте начального расписания. Критерий равномерности полученного расписания составляет KS = 26,93 %.

klev3.wmf

Рис. 3. Начальное расписание экзаменов

Эвристика SGS2 (оптимизация расписания экзаменов) состоит в цикличном выборе наиболее неравномерного экзамена и изменении расписания klev34.wmfдля минимизации критерия равномерности расписания (8) при обязательных ограничениях (10, 11) и уточнении ограничения (12).

klev35.wmf. (14)

Каждый цикл оптимизации начинается переопределением оценок равномерности (4, 5) и формированием множеств первых и вторых оценок равномерности экзаменов расписания.

klev36.wmf, (15)

klev37.wmf. (16)

Многовекторным ранжированием [15] определяется самый неравномерный экзамен расписания следующим образом. Ранги, получаемые многокритериальным ранжированием векторов (15, 16), формируют множество векторов рангов:

klev38.wmf. (17)

Многокритериальное ранжирование векторов (17) определяет самый неравномерный экзамен, становящийся очередным кандидатом на перестановку в расписании. Далее, как и в эвристике SGS1 определяется таймслот для перестановки. Работа эвристики SGS2 завершается при невозможности дальнейшего улучшения расписания экзаменационной сессии. На рис. 4 представлен один из вариантов оптимального расписания экзаменов. Критерий равномерности расписания составляет KS = 3,58 %, что существенно меньше аналогичного критерия начального расписания. Следует также отметить уменьшение количества аудиторий, требуемых для приема экзаменов.

klev4.wmf

Рис. 4. Оптимальное расписание экзаменов

Заключение

Авторы считают что:

– разработан подход к формированию расписания экзаменов вуза с использованием двух последовательно применяемых эвристик;

– приведенная модель для «классической» организации экзаменационной сессии может быть трансформирована для других типов организации сессии.


Библиографическая ссылка

Клеванский Н.Н., Мавзовин В.С. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ФОРМИРОВАНИЯ РАСПИСАНИЯ ЭКЗАМЕНОВ ВУЗА // Современные наукоемкие технологии. – 2018. – № 5. – С. 97-102;
URL: https://top-technologies.ru/ru/article/view?id=36998 (дата обращения: 29.03.2024).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1,674