Научный журнал

Фундаментальные исследования

ISSN 1812-7339

"Перечень" ВАК

ИФ РИНЦ = 1,674

• Авторы
• Резюме
• Файлы
• Ключевые слова
• Литература

Клеванский Н.Н. 1

---

1 ФГБОУ ВО «Саратовский государственный аграрный университет имени Н.И. Вавилова»

Формирование расписания занятий вуза является широко известной и достаточно обсуждаемой проблемой. Проблема связана с распределением трех ограниченных ресурсов системы – студентов, преподавателей и аудиторий в определенных промежутках времени с соблюдением соответствующих ограничений. Задача формирования расписания занятий вуза является NP-полной. В статье представлены основные концепции и подходы в реализации задач расписаний высших учебных заведений. Процедура планирования занятий использует две последовательно применяемые схемы генерации расписаний, реализованных в среде СУБД. Формирование начального расписания по первой схеме с использованием критерия наилучшего распределения ресурсов является базовым для следующей схемы – этапа оптимизации. Каждая схема генерации расписаний включает два правила приоритетов – процедур получения решений с использованием многокритериального, многовекторного и гипервекторного ранжирования. Предложены основные критерии в задачах выбора при формировании и оптимизации расписаний высших учебных заведений – критерии загруженности и равномерности ресурсов системы.

Статья в формате PDF

0 KB

расписание

заявка

занятие

схема генерации расписания

правило приоритетов

методы ранжирования

1. Клеванский Н.Н. Формирование расписания занятий высших учебных заведений // Образовательные ресурсы и технологии. – 2015. – № 1. – С. 34–44.

2. Клеванский Н.Н. Метаэвристики формирования расписаний // Мехатроника, автоматика и робототехника. – 2017. – № 1. – С. 85–88.

3. Клеванский Н.Н., Кашин С.С. Формирование расписания занятий университета с использованием методов ранжирования // Вестник Саратовского государственного технического университета. – 2010. – № 4 (49). – С.143–150.

4. Сафронов В.В. Основы системного анализа: методы многовекторной оптимизации и многовекторного ранжирования: монография. – Саратов: Научная книга, 2009. – 329 с.

5. Bello G.S., Rangel M.C., Boeres M.C.S. An approach for the class/teacher timetabling problem, in: Proceedings of the 7th International Conference on the Practice and Theory of Automated Timetabling (PATAT’08), 2008. – Р. 1–6.

6. Browning T.R., Yassine A.A. Resource-Constrained Multi-Project Scheduling: Priority Rule Performance Revisited. International Journal of Production Economics. – 2010. – № 126 (2). – Р. 212–228.

7. da Fonseca G.H.G., Santos H.G., Toffolo T.A.M., Brito S.S., Souza M.J.F. GOAL solver: a hybrid local search based solver for high school timetabling // Annals of Operations Research. – 2014. – Р. 1–21.

8. Luca Di Gaspero, Andrea Schaerf., Hybrid Local Search Techniques for the Generalized Balanced Academic Curriculum, In Proceedings of HM. – Berlin: Springer-Verlag, 2008. – Р. 146–157.

9. Post G., Ahmadi S., Daskalaki S., Kingston J.H., Kyngas J., Nurmi C., Ranson D. An XML format for benchmarks in High School Timetabling // Annals of Operations Research. – 2012. – № 194(1). – Р. 385–397.

10. Raghavjee R., Pillay N. A comparison of genetic algorithms and genetic programming in solving the school timetabling problem, in: Fourth World Congress on Nature and Biologically Inspired Computing (NaBIC 2012), IEEE. Р. 98–103.

11. Shambour M.K.Y., Khader A.T., Kheiri A., Ozcan E. A two stage approach for high school timetabling, in: Lee, M., Hirose, A., Hou, Z.G., Kil, R.M. (Eds.), Neural Information Processing. Springer Berlin Heidelberg. volume 8226 of Lecture Notes in Computer Science, 2013. – Р. 66–73.

Формирование расписания занятий является одной из основных и наиболее сложных задач автоматизации управления учебным процессом вуза. В связи с большими различиями организации высшего образования в разных странах сделана попытка стандартизации ограничений для задач расписаний [9]. При учете всех ограничений, включая NP-полноту задачи, на передний план выходят эвристические методы, такие как имитация отжига [7], поиск с запретами [5, 8], эволюционные алгоритмы [10, 11]. В основе эвристик мультипроектного планирования находятся схемы формирования расписаний (SGS – schedule generation scheme) и правила приоритетов (PR – priority rules) [6]. Приоритетами являются критерии для определения очередности конкурирующих по ресурсам работ/проектов. В исследованиях по формированию расписаний вузов подобных подходов не обнаружено. Для решения задачи формирования расписания занятий вуза предложены эвристики, основанные на критериях загруженности и равномерности использования ресурсов [1, 3].

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

Задача формирования расписания занятий вуза является задачей распределения трех ресурсов – студенческого контингента, преподавателей и аудиторий при проведении трех видов занятий: занятие одной группы с одним преподавателем; занятие нескольких групп с одним преподавателем – занятие потока; занятие одной группы с несколькими преподавателями – занятия подгрупп группы.

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

Исходными данными для формирования расписания занятий являются заявки групп, в которых указывается студенческий контингент, преподаватель, дисциплина, вид занятия и требуемые или желаемые аудитории с набором признаков. Основной признак аудитории – вместимость. Дополнительными признаками могут быть требуемое оборудование – лабораторное, компьютерное, мультимедийное и т.п. Аудитория в заявке группы может иметь «пустое» значение – Null, заменяемое конкретным значением при формировании расписания. Студенческий контингент в заявке группы представлен группой, потоком и подгруппой. В зависимости от вида занятия поток и подгруппа могут иметь значения Null. Заявки групп формируются для каждой «пары» занятий каждой группы для двух недель расписания. На основе заявок групп перед началом формирования расписания формируются заявки занятий, далее заявки, структура которых в зависимости от типа занятия имеет различный характер.

Для формирования расписания занятий высшего учебного заведения использованы две последовательно применяемые схемы генерации расписаний [2]:

- конструктивная эвристика SGS1 – стратегия формирования начального расписания;

- оптимизационная эвристика SGS2 – стратегия оптимизация расписания.

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

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

– множество академических групп;

P, R – множества потоков и подгрупп академических групп;

– множество преподавателей;

– множество аудиторий;

– множество заявок групп, где:

– p – конкретный поток или – NULL;

– r – конкретная подгруппа или – NULL;

– l – конкретный преподаватель или – NULL;

– a – конкретная аудитория или NULL.

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

nt – общее число таймслотов интервала расписания.

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

N – количество занятий расписания;

– множество заявок на проведение занятий;

, – подмножество групп i-ой заявки;

– количество заявок i-ой группы;

– количество заявок i-ого преподавателя;

– количество заявок i-ой аудитории.

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

– множество занятий расписания;

индекс занятия – порядковый номер включения занятия в начальное расписание;

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

– количество занятий i-ой группы, включенных в начальное расписание;

– количество занятий i-ого преподавателя, включенных в начальное расписание;

– количество занятий i-ой аудитории, включенных в начальное расписание;

Таблица 1

Оценки загруженности

nt – количество таймслотов для включения заявки в начальное расписание занятий;

wk – количество занятий k-ой группы в интервале расписания;

– количество занятий k-ой группы на i-ой «паре» в интервале расписания;

– количество фактических учебных дней k-ой группы в интервале расписания;

– количество занятий k-ой группы j-ого учебного дня расписания;

, – количество повторяющихся и не повторяющихся по времени занятий k-ой группы в j-ом и (j + 7)-ом учебных днях интервала расписания.

Таблица 2

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

Значение оценки присваивается всем занятиям i-ой «пары» k-ой группы. Значение оценки присваивается всем занятиям j-ого учебного дня k-ой группы. Значение оценки присваивается всем занятиям j-ого и (j + 7)-ого учебных дней k-ой группы.

Критерий равномерности i-ого занятия расписания:

. (7)

Критерий равномерности расписания k-ой группы:

, (8)

где nd – количество «пар» в день.

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

Стратегия SGS1 (формирование начального расписания занятий) состоит в цикличном выборе очередной заявки dni+1 и ее включении в расписание так, чтобы минимизировать критерии равномерности групп последнего включаемого занятия

(9)

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

(10)

(11)

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

SGS1 содержит два правила приоритетов PR11 и PR12, а в каждом цикле осуществляется:

- подготовка исходных данных для правила PR11 – переопределение оценок загруженности групп, преподавателей и аудиторий, а также критериев загруженности заявок занятий, не включенных в начальное расписание;

- в правиле PR11 осуществляется выбор наиболее загруженной заявки занятия среди занятий, не включенных в начальное расписание;

- подготовка исходных данных для правила PR12 – определение критериев равномерности начального расписания в таймслотах для включения выбранной правилом PR11 заявки в начальное расписание занятий;

- в правиле PR12 определяется таймслот для включения выбранной правилом PR11 заявки с обеспечением наибольшей равномерности потребления ресурсов системы.

Рассмотрим применение стратегии SGS1 и правил приоритетов PR11 и PR12.

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

(12)

(13)

(14)

Для определения самой загруженной заявки в правиле PR11 применяется многовекторное ранжирование, заключающееся в следующем [2, 4]. Обратное многокритериальное ранжирование векторов (12–14) порождает множества рангов заявок по загруженности групп, преподавателей и аудиторий, формирующие множество векторов рангов заявок

(15)

Старшая по рангу заявка, полученная прямым многокритериальным ранжированием векторов (15), является самой загруженной при принятых оценках и критериях загруженности. Она становится очередным кандидатом dni+1 на включение в начальное расписание.

Для заявки dni+1 определяется множество всех возможных в соответствии с обязательными ограничениями таймслотов расписания . Оценки равномерности (4–6) групп заявки dni+1 для каждого из таймслотов формируют три множества множеств первых, вторых и третьих многовекторных компонент критериев равномерности.

(16)

(17)

(18)

Для нахождения таймслота tk, обеспечивающего наибольшую равномерность расписаний групп заявки dni+1, правило PR12 должно реализовать гипервекторное ранжирование критериев равномерности (16–18) заключающееся в следующем.

Прямое многокритериальное ранжирование каждого из множеств векторов (16–18) порождает три множества рангов критериев расписаний каждой группы.

(19)

(20)

(21)

Прямое многокритериальное ранжирование каждого из множеств векторов (19–21) порождает три множества рангов занятий для разных таймслотов , формирующие множество векторов рангов занятий

. (22)

Прямое многокритериальное ранжирование векторов (22) определяет доминирующий вектор, индекс k которого определяет искомый таймслот, в котором будет проводиться занятие заявки dni+1. Если nr > 0, то переход к следующему шагу формирования начального расписания.

Стратегия SGS2 (оптимизация расписания занятий) состоит в цикличном выборе очередного занятия и изменении расписания , которое минимизирует критерии равномерности групп последнего переставляемого занятия (9) при обязательных ограничениях (11).

В схеме SGS2 используются два правила приоритетов PR21 и PR22. Правило PR22 эквивалентно правилу PR12, поэтому в каждом цикле SGS2 осуществляется:

- подготовка исходных данных для правила PR21 – переопределение оценок равномерности расписаний групп, а также критериев равномерности занятий расписания;

- в правиле PR21 осуществляется выбор наиболее неравномерного занятия расписания;

- дальнейшие действия совпадают с действиями схемы SGS1.

Рассмотрим применение стратегии SGS2 и правила приоритетов PR21

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

(23)

(24)

(25)

Для определения самого неравномерного занятия в правиле PR21 применяется многовекторное ранжирование, заключающееся в следующем. Многокритериальное ранжирование векторов (23–25) порождает множества рангов занятий, формирующие множество векторов рангов

. (26)

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

Заключение

Автор считает новыми следующие положения и результаты:

– введены многовекторные критерии загруженности заявок и равномерности занятий расписания;

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

– использование правил приоритетов базируется на методах ранжирования теории принятия решений.

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