Концептуальная модель задачи составления учебного расписания в вузе

Задача автоматического составления учебного расписания в вузе является актуальной в свете повышения требований к качеству учебного процесса со стороны всех его участников – преподавателей, студентов, учебного заведения. История задачи и возможные методы ее решения представлены в работах [1–6]. Современные программные средства часто составляют оптимальное расписание только по одному из критериев (например, отсутствию «окон»), чего недостаточно на практике. В реальных условиях требуется учитывать массу условий и требований, которые предъявляются участниками учебного процесса. Расписание в вузах часто составляется вручную [7; 8].

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

Материалы и методы

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

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

Концептуальная модель задачи составления учебного расписания в вузе можно ближе друг к другу по временным интервалам. Более подробно про постановку задачи см. [8–10].

Предполагается, что аудитории учебного заведения могут располагаться в нескольких корпусах, между которыми студентам и преподавателям необходимо переходить и тратить на это время (время на переходы известно). Также предполагается, что в день может быть не более определенного количества пар занятий (5 пар).

Определены обязательные (жесткие) ограничения (в скобках указаны обозначения ограничений):

• •    (HA1) в расписании должны быть все занятия, которые находятся в учебной программе каждой группы;

• •    (HA2) в одно и то же время в одной и той же аудитории не могут проходить два различных занятия;

• •    (HA3) преподаватель в один временной интервал может проводить только одно занятие;

• •    (HA4) у группы (подгруппы или потока) в один временной интервал в расписании может быть только одно занятие; у подгрупп одной группы могут быть занятия в одно время; занятия у группы и у потока с ее участием или у группы и ее подгруппы не должны пересекаться;

• •    (HA5) все студенты группы (подгруппы или потока) должны помещаться в отведенную для занятия аудиторию;

• •    (HA6) для проведения некоторых занятий требуются определенные аудитории (например, физическая культура проводится в спортивном зале); аудитория должна соответствовать типу занятия;

• •    (HA7) какое-либо время на подготовку аудитории к занятию не требуется;

• •    (HA8) временные интервалы, в которые заняты преподаватели (это ограничение обозначим HA81), аудитории (HA82) и группы (HA83) использовать для проведения занятий нельзя; такие временные интервалы указаны заранее;

• •    (HA9) преподаватель может пожелать установить свои занятия по определенной дисциплине компактно;

• •    (HA10) лекционные занятия по определенной дисциплине могут идти перед практическими занятиями (и/или лабораторными работами) по желанию преподавателя;

• •    (HA11) расписание должно учитывать необходимое время на переход между корпусами для групп/подгрупп/потоков и преподавателей.

Желательные (мягкие) ограничения, относящиеся к учебным группам:

• •    (SB1) количество «окон» в расписании групп должно быть минимальным;

• •    (SB2) нагрузка на группы по дням должна быть равномерной в течение всего цикла планирования;

• •    (SB3) минимизация числа переходов между корпусами для учебных групп.

Желательные (мягкие) ограничения, относящиеся к преподавателям:

• •    (SC1) количество «окон» в расписании преподавателей должно быть минимальным;

• •    (SC2) должно быть удовлетворено как можно большее число требований преподавателя к аудиториям (например, наличие ноутбука, проектора и др.);

• •    (SC3) минимизация числа переходов между корпусами для преподавателей;

Вестник Российского нового университета

Серия «Сложные системы: модели, анализ и управление». 2025. № 3

• •    (SC4) нагрузка на преподавателей должна быть равномерной в течение всего цикла планирования.

Желательные (мягкие) ограничения, относящиеся к учебному заведению:

• •    (SD1) количество незанятых мест в аудиториях, в которых проводятся занятия, должно быть минимальным.

Отметим, что часть ограничений из списка обязательных может быть сформулирована в виде желательных (что и наблюдается в работах других авторов). Ограничение HA8 может звучать так: максимизировать количество пар, на которых удовлетворены требования занятости для преподавателей (обозначим SA81), групп и аудиторий.

Часть ограничений из списка желательных может быть сформулирована как обязательные. Ограничение SB1 может звучать так: не должно быть «окон» в расписании групп (обозначим HB1). Ограничение SC1 в форме обязательного ограничения: не должно быть «окон» в расписании преподавателей (обозначим HC1). Ограничение SC2 в обязательной форме: должны быть удовлетворены все требования преподавателей к аудиториям (обозначим HC2).

Результаты

Проведем сравнение нашей модели с некоторыми наиболее важными для исследования моделями других авторов. Обозначим задачу из диссертации М.Г. Маслова [11] буквой A , задачу из диссертации Амера Ю. Абухании [12] – B , задачу Г.Ф. Низамовой [13] – С , задачу Фираса М. Асвада [14] – D (по данным задачам также см. [15]). В Таблице приведено наличие тех или иных ограничений и частных критериев (желательных ограничений) в рассмотренных моделях. Обратим внимание на то, что одно и то же ограничение в разных задачах может быть отнесено к разным видам ограничений – обязательным либо желательным. Однако при этом будут различаться модели и алгоритмы построения оптимального расписания и сами оптимальные расписания. Отметим также, что потоки и подгруппы присутствуют во всех рассматриваемых моделях, кроме модели D .

Таблица

Наличие обязательных и желательных ограничений в различных моделях

Ограничения	Модели
	A	B	C	D
Наличие потоков	+	+	+	–
Наличие подгрупп	+	+	+	–
Обязательные ограничения нашей модели
HA1	+	–	+	–
HA2	+	–	+	+
HA3	+	+	+	+
HA4	+	+	+	+
HA5	+	+	–	–
HA6	+	+	+	+
HA7	+	+	+	–
HA81	+	+	–	–

Концептуальная модель задачи составления учебного расписания в вузе

Продолжение таблицы

Ограничения	Модели
	A	B	C	D
HA82	+	–	–	–
HA83	+	+	–	–
HA9	–	–	–	–
HA10	–	–	–	–
HA11	–	+	+	–
Обязательные ограничения, которых нет в нашей модели
HB1	–	–	+	–
HC1	+	–	–	–
Желательные ограничения нашей модели
SB1	+	+	–	–
SB2	+	–	+	+
SB3	–	+	–	–
SC1	+	+	+	+
SC2	–	–	+	+
SC3	–	+	–	–
SC4	–	–	–	–
SD1	+	+	–	–
Желательные ограничения, которых нет в нашей модели
SA81	+	–	+	+

Источник: таблица составлена автором.

Стоит отметить, что ни в одной из рассмотренных моделей обязательные требования HA9 и HA10 не применяются.

В диссертационной работе М.Г. Маслова [11] перечислены различные виды критериев:

• 1)    критерии требований перечислительного типа. Пример: максимизация числа требований преподавателей на временные интервалы для их занятий;

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

Ограничения и частные критерии, которые совпадают с нашей моделью, можно посмотреть в Таблице (столбец A ). Модель предполагает наличие потоков и подгрупп.

К ограничениям, которых нет в нашей модели, относятся следующие:

• •    должно выполняться указанное распределение по неделям;

• •    у преподавателей должны отсутствовать «окна» (HC1) ;

• •    число пар в день у каждой группы не может превышать определенного количества;

• •    количество пар для преподавателя в определенный день ограничено;

Вестник Российского нового университета

Серия «Сложные системы: модели, анализ и управление». 2025. № 3

К частным критериям, которых нет в нашей модели, относятся:

• •    число дней, в которые у учебных групп все занятия проходят в одном корпусе (без перехода между корпусами), должно быть максимальным;

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

В диссертации Ю.А. Амера Абухании [12] рассматривается задача составления расписания учебных занятий вуза (University Course Timetabling Problem – UCTP). Помимо математической, разработаны реляционная (информационная) и формально-языковая модели (алгоритмическая).

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

Все статические жесткие ограничения, перечисленные в рассматриваемой модели, присутствуют также в представленной модели. Динамические ограничения также есть в нашей модели (HA3, HA4, HA11).

«Жесткие» ограничения: запрет на размещение в одном таймслоте двух учебных единиц; невозможность студентам переместиться из одной аудитории в другую между парами из-за нехватки времени.

Качество расписания оценивается по степени нарушения «мягких» ограничений. Для подсчета качества расписания применяется метод аддитивной свертки частных критериев с нормирующими коэффициентами.

В качестве частных критериев, которых нет в нашей модели, выступают:

• •    количество занятий лекционного типа, которые поставлены не в утренние часы;

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

Обязательное ограничение HA7, видимо, подразумевается. Ограничения HA9 и HA10 в рассматриваемой модели отсутствуют. В модели [12] не учитывается такой важный критерий, как равномерность учебного расписания для групп (SB2). Также не учитываются требования преподавателей к аудиториям (SC2). Кроме того, в модели учитывается тот факт, что лекции лучше ставить в утреннее время и что можно превысить максимально допустимое количество пар в день. Обязательное требование HA8 присутствует только в вариантах HA81 и HA83 (возможная занятость учебной группы не рассматривается).

В диссертационном исследовании Г.Ф. Низамовой [13] рассматривается задача составления учебного расписания в образовательных системах массового обучения. Ограничения и частные критерии, которые совпадают с нашей моделью, можно посмотреть в Таблице (столбец C ). Из таблицы видно, что достаточно много ограничений нашей модели – HA5, HA81-HA10, SB1, SB3, SC3-SD1 – отсутствует в рассматриваемой модели. Ограничение HA8 присутствует только в плане учета пожеланий преподавателей (H81), но не студентов (HA82) и занятости аудиторий (HA83). Ограничение HA7 явно не прописано, но оно подразумевается в модели.

К ограничениям, которых нет в нашей модели, относится:

• •    отсутствие «окон» в расписании групп (HB1); при этом для преподавателей отсутствие «окон» в модели – желательный критерий (SC1.

Концептуальная модель задачи составления учебного расписания в вузе

К частным критериям, которых нет в нашей модели, относится следующий:

• •    различные виды занятий должны проводиться в разные по времени (более ранние или более поздние) временные интервалы; например, лекции желательно проводить в начале учебного дня и др. по другим видам занятий.

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

Математическая модель учитывает наличие потоков и подгрупп. Аудитории делятся на большие, средние, малые и лабораторные.

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

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

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

В диссертационном исследовании [14] рассматривается задача составления расписания занятий вуза с использованием генетического алгоритма. Отмечено, что задача планирования и распределения ресурсов является многокритериальной, поскольку интересы участников учебного процесса многообразны. Ограничения и желательные требования, которые совпадают с нашей моделью, можно посмотреть в Таблице (столбец D ). В рассматриваемой модели отсутствуют некоторые важные ограничения и критерии, которые присутствуют в нашей модели, например, HA5, HA7-HA11, SB1, SC3, SC4, SD1. Присутствует ограничение на максимальное количество пар в день для группы. В модели, представленной в [14], также имеются специфические ограничения, которые характерны для вузов Ирана. Отметим также, что в этой модели отсутствуют потоки и подгруппы (студенты организованы только в группы).

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

• •    периодом планирования является неделя, «числитель» и «знаменатель» в расписании отсутствуют;

• •    женщины и мужчины занимаются отдельно, у них разные занятия.

Существенным отличием рассматриваемой модели от нашей является то, что в ней нет деления на «числитель» и «знаменатель».

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

Ни в одной из рассмотренных работ не представлен весь набор ограничений нашей задачи, не представлено ограничение компактного размещения занятий (HA9) и ограничение на то, что лекции должны предшествовать практическим и лабораторным занятиям

Вестник Российского нового университета

Серия «Сложные системы: модели, анализ и управление». 2025. № 3

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

Обсуждение

В статье рассмотрены задачи из диссертации М.Г. Маслова [11], Амера Ю. Абуха-нии [12], Г.Ф. Низамовой [13], М. Асвада Фираса [14]. Нами были проанализированы ограничения схожих задач других авторов и составлена Таблица их сравнения с ограничениями нашей модели.

В задаче М.Г. Маслова существует ограничение на отсутствие «окон» в расписании преподавателя (HC1); ограничение выполнения указанного распределения занятий по неделям; ограничение на количество пар в день для группы, которых нет в нашей задаче. Также присутствуют частные критерии, которых нет в нашей модели. Однако в нашей задаче достаточно много ограничений (HA9–HA11, SB3, SC2-SC4), которых нет в задаче М.Г. Маслова.

В задаче Ю.А. Амера Абухании содержатся статические ограничения (их можно учесть до составления расписания), которые также присутствуют в нашей задаче. Но в нашей модели есть ограничения (HA1, HA2, HA82, HA9, HA10), которых нет в модели автора. Не все желательные ограничения нашей задачи присутствуют в задаче Ю.А. Амера Абухании (см. Таблицу). Кроме того, в рассматриваемой задаче есть частные критерии, которых нет в нашей модели, такие как количество лекционных пар не в утреннее время; суммарное превышение количества пар в день относительно максимального.

Достаточно много ограничений нашей модели (HA5, HA81-HA10, SB1, SB3, SC3-SD1) отсутствуют в модели Г.Ф. Низамовой. В модели есть ограничение HB1 (отсутствие «окон» в расписании групп), которое у нас сформулировано в желательной форме (SB1); а также ограничение на максимальное количество пар для группы в день. Кроме того, есть желательное ограничение на то, что некоторые виды занятий нужно проводить в определенное время (например, лекции в начале учебного дня).

В задаче М. Асвада Фираса отсутствует достаточно много ограничений (HA5, HA7-HA11, SB1, SC3, SC4, SD1), которые есть в нашей задаче. Есть и специфические ограничения, которые присущи учебным заведениям Ирана.

Ни в одной из представленных для сравнения задач не встречается ограничение на компактное размещение занятий (HA9), а также ограничение, при котором лекции по дисциплине должны проходить раньше, чем практические занятия (HA10).