Scientific journal
Modern high technologies
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 1,021

HIGH SCHOOL EXAM TIMETABLING PROBLEM

Klevankyi N.N. 1 Mavzovin V.S. 1
1 Saratov State Agrarian University named after N.I. Vavilov
Формирование расписания экзаменов вуза может быть сформулировано как задача комбинаторной оптимизации. Задача формирования расписания экзаменов является оптимизационной задачей, которая состоит в распределении множества экзаменов во множестве временных промежутков при соблюдении множества ограничений. Задача является NP-полной и обычно решается с применением эвристических методов. В статье представлены базовые концепции решения задачи формирования экзаменов вуза. Эти концепции реализуют ресурсо-ориентированный подход. Процедура планирования экзаменов использует две последовательно применяемые схемы генерации расписаний. В каждой схеме используются два правила приоритетов – процедур получения решений с использованием многокритериального и многовекторного ранжирования теории принятия решений. Первая схема обеспечивает получение начальных расписаний. Вторая схема оптимизирует начальные решения. Когнитивность кругового представления расписания экзаменов способствовала разработке нового подхода к оптимизации. Основным критерием для оптимизационных процедур предложен критерий равномерности потребления ресурсов. В качестве такого критерия использовано среднеквадратичное отклонение интервалов между экзаменами от средних значений. Приведенные экспериментальные данные демонстрируют способность предлагаемого подхода к получению расписаний достаточно высокого качества.
High school exam timetabling (HSETT) can be formulated as a combinatorial optimization problem. Examination timetabling problem is an optimization problem which consists in assigning a set of exams to a set of contiguous time slot, satisfying a set of constraints. The problem falls in the category of the NP-complete problems and is usually tackled using heuristic methods. In the paper basic concepts for HSETT are presented. These concepts are realized resource-based approach. The HSETT procedure can be solved efficiently by two schedule generation schemes. Each scheme includes two heuristic solution-finding procedures based on priority rules. The priority rules use multi-criteria, multi-vector and hyper-vector ranking of decision support theory. First scheme produce initial timetables. The second scheme optimizes the initial solutions. Circular timetable visualizations are provoked a new approach to exam timetable optimization. The basic criterion for optimization operations is demanded as criterion of resource equability. The latter is equal a root-mean-square deviation from a middle value of exam intervals. The experimental results demonstrate that the proposed approach is able to produce good quality timetable.
timetable
demand
examination
schedule generation scheme
priority rule
root-mean-square deviation
ranking methods

Задача формирования расписания экзаменов является задачей комбинаторной оптимизации, а по своей сложности относится к классу 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. Оптимальное расписание экзаменов

Заключение

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

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

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