В статье рассмотрена проблема построения расписания занятий в образовательном учреждении. В более широком контексте эта проблема актуальна для различных сфер человеческой деятельности: задачи, связанные с расписанием (графиками и путями движения) автомобильного, воздушного, водного и железнодорожного транспорта, распределением загрузки оборудования в технологических процессах и т.д.
Задача расписания представляет собой комбинаторную NP-полную задачу [6], для решения которой необходимо распределить занятия по множеству имеющихся аудиторий с учетом их вместимости и доступному временному пространству. Помимо этого, к учебному расписанию предъявляется множество нелинейных критериев и требований, часто противоречащих друг другу, что делает задачу определения целевой функции нетривиальной и плохо выражаемой в виде взвешенной суммы критериев.
Современное укрупнение образовательных учреждений и требования, предъявляемые к допустимой нагрузке, на практике приводят к появлению новых специфичных критериев качества расписания и ограничений, таких как допустимое предельное время перехода между аудиториями, принадлежность к той или иной учебной смене или ограниченность по количеству лекций в течение одного дня, не рассматриваемых в большинстве других моделей [1–4].
Вследствие представленных сложностей для решения рассматриваемой задачи рационально использовать приближенные алгоритмы, которые позволяют за приемлемое время найти квазиоптимальное решение. В работе предлагается использовать алгоритмы метаэвристик, которые объединяют основные эвристические подходы и представляют обобщенные схемы решения задач оптимизации [11]. Благодаря высокоуровневому описанию метаэвристические методы не привязаны к конкретным задачам и могут быть применены к широкому кругу проблем, в то же время остается возможным адаптировать низкоуровневые элементы к спецификам конкретной предметной области для достижения большей эффективности.
Выбор метаэвристического алгоритма и его параметров для решения конкретной задачи зависит прежде всего от целевой функции и ограничений, которые определяют пространство поиска [9].
Описание проблемы исследования
В рассматриваемой задаче имеются так называемые жесткие ограничения, т.е. ограничения, невыполнение которых приводит к недопустимости решения. В качестве примера нарушения такого ограничения можно привести расписание, в котором в один момент времени преподаватель должен вести несколько занятий. Возможность получения таких решений создает некорректные области в пространстве поиска, которые необходимо либо полностью исключить из рассмотрения, либо обрабатывать особым образом, чтобы в конечном итоге получить допустимое расписание.
В первом случае необходимо сконструировать начальное допустимое решение, после чего производить его «безопасную» модификацию при помощи специальных операторов, избегающих недопустимых решений [13]. Для задачи составления расписания такой подход был применен в работе [3]. В качестве недостатков следует отметить сложность построения начального решения, и еще большую сложность реализации операторов, которые бы приводили только к допустимым результатам и при этом оставляли достижимым все корректное пространство поиска.
Другим подходом является допущение присутствия вариантов решения, которые не удовлетворяют жестким ограничениям, но при этом их оценка занижается при помощи штрафных функций [13]. При этом под штрафной функцией понимают функцию, которая отражает степень нарушения определенного ограничения. Данный метод основывается на том, что наличие решений, не удовлетворяющих жестким ограничениям, положительно влияет на поиск допустимых решений в будущем, уменьшая количество разрывов в пространстве поиска. В этом случае удается избежать многих сложностей возникающих в предыдущем подходе, однако возникает проблема адекватной оценки недопустимых решений.
По причине присутствия в большинстве метаэвристических алгоритмов процедур локального поиска, очень важными факторами, влияющими на эффективность работы, являются непрерывность и гладкость пространства поиска [14]. Присутствие данных факторов не является достаточным условием для успешной работы алгоритмов, однако может способствовать более скорому достижению оптимума.
Нелинейность и противоречивость множества требований, накладываемых на учебное расписание, создают сложную структуру пространства поиска, для которого характерна многоэкстремальность. Для успешной работы в таком пространстве используемый алгоритм не должен концентрироваться на локальных минимумах, что достигается путем настройки параметров метаэвристик, определяющих соотношение интенсификации и диверсификации.
Для сглаживания переходов между допустимыми и недопустимыми решениями зададим показатель выполнения жестких требований как расстояние, получаемое из соотношения количества занятий с невыполненными требованиями к количеству занятий, удовлетворяющих им. Тогда при оценке расписания минимизацию полученного расстояния можно представить в виде одного из критериев оптимизации.
Для обеспечения непрерывности и гладкости пространства поиска в областях допустимых решений важно, чтобы малые изменения потенциального решения приводили к малым изменениям значения целевой функции [14]. Однако достигнуть этого в полной мере крайне сложно по причине большой связности компонент, составляющих расписание, а также специфики некоторых требований, однако минимизация количества возможных «скачков» и «разрывов» может оказать положительный эффект на скорости оптимизации.
Математическая модель задачи
Для формализации задачи построения расписания введем следующие обозначения:
|
G |
– Множество учебных групп. |
|
F |
– Множество потоков обучения |
|
L |
– Множество ведущих занятия преподавателей. |
|
D |
– Множество изучаемых дисциплин. |
|
C |
– Множество типов учебных занятий (лекционное занятие, лабораторное или практическое занятие, физическая подготовка и другое). |
|
A |
– Множество учебных аудиторий. |
|
W |
– Множество учебных дней. Вид множества зависит от принятой в учебном заведении структуры расписания. При «понедельном» расписании |
|
J |
– Множество учебных пар (временных дискретных позиций в течение дня для проведения занятий). Чаще всего данное множество представляется в виде интервала натуральных чисел от 1 до tmax (максимального номера пары/урока в учебном заведении). |
, то есть каждый поток может состоять из одной или более групп, принадлежащих множеству G, что определяется целесообразностью объединения групп в потоки и зависит от изучаемой дисциплины 
и типа проводимого занятия 
.
. При делении учебных недель на «нижнюю» и «верхнюю» 
. В общем случае, элементы множества могут принимать значения от 1 до 366 (количество дней високосного года) при отсутствии в расписании повторяющихся участков.В приведенных обозначениях реализуемый учебный план P, для которого должно быть составлено расписание, будет представлять разреженное множество элементов 
из пространства 
, а множество пространственно-временных слотов T для размещения занятий – элементами 
. Таким образом, нам необходимо найти такое отображение 
, которое наилучшим образом удовлетворяло бы ряду естественных и искусственных ограничений, наложенных на такое отображение. Для этого разделим задачу на две подзадачи:
1. Распределение только временных позиций (то есть элементов множества 
) с учетом ограничений по количеству аудиторного фонда, но абстрагируясь от конкретных аудиторий и их свойств.
2. Подбор конкретных аудиторий для полученного на предыдущем этапе распределения с учетом дополнительных ограничений.
Такое разделение позволяет существенно сократить пространство поиска, что положительно сказывается на времени решения [3].
Тогда итоговая структура расписания для первой подзадачи будет представлена трехмерной бинарной матрицей:
где 
– что описывает,
– количество планируемых занятий,
n – количество дней во временном пространстве расписания,
o – количество временных единиц (пар) в одном дне,
– идентификатор занятия,
– порядковый номер дня во временном пространстве расписания,
– порядковый номер временной единицы (пары) в пределах дня.
Каждый элемент матрицы T1 представляет бинарную переменную, которая равна 1, если занятие i проходит в j-й день в i-й временной единице, и 0 в иных случаях.
Организация метрического пространства для второй подзадачи имеет большую сложность, что обусловлено большим разнообразием параметров учебных аудиторий. Наиболее важными факторами, влияющими на качество распределения второго этапа, являются местоположение аудиторий и наличие в них средств, необходимых для проведения занятий.
Будем считать, что исходными данными для выполнения данной подзадачи являются множество учебных аудиторий A, а также множество занятий с определенными временными позициями E, каждый элемент которого представляет кортеж (w, p).
Для формирования структуры расписания предлагается провести разделение множества аудиторий на типы, при этом под типом подразумевается класс аудиторий, имеющих эквивалентные средства для проведения занятий. Пусть Ai – множество аудиторий одного типа, при этом 
, где m – мощность множества типов. Для многих учебных заведений можно провести более глубокую декомпозицию, однако такое разделение зависит от специфик конкретного учреждения и выходит за рамки данной статьи.
Далее множество аудиторий необходимо кластеризовать по признакам местоположения. В качестве таких признаков можно использовать географические координаты, включающие: широту, долготу и высоту. Пусть Aj – множество аудиторий одного кластера, при этом 
, где n – количество кластеров.
В итоге структура расписания для второй подзадачи будет представлена четырехмерной бинарной матрицей:
где 
– что это,
m – мощность множества типов,
n – количество кластеров местоположения,
o = 
количество планируемых занятий,
– идентификатор типа аудитории,
– порядковый номер кластера местоположения,
– идентификатор запланированного занятия,
p = 
максимальное количество аудиторий типа i в кластере j,
– множество аудиторий типа i из кластера j,
– порядковый номер аудитории в множестве 
.
Оценка качества расписания
Одним из подходов к оценке качества решения является определение величины, отражающей отклонение от некого идеала. Известно, что к расписанию предъявляется множество требований различного рода. Каждое требование можно представить в роли оптимизационного критерия, значение которого будет определяться соответствующей штрафной функцией, отражающей отклонение от идеального выполнения требования. Тогда задача составления расписания сводится к многокритериальной оптимизации множества штрафных функций [12]:
,
где r – расписание,
fi – штрафная функция i-го критерия,
n – количество критериев,
R – множество расписаний.
Довольно часто требования к расписанию являются противоречивыми, вследствие чего не существует решения, в котором бы достигался минимум для всех критериев одновременно. Вследствие этого в задачах составления расписаний часто применяют понятие парето-оптимальности, которое основывается на бинарном отношении доминирования [3]. Стоит отметить, что парето-оптимальные расписания не сравнимы между собой, а их количество в теории является бесконечным, поэтому на практике рассматривается решение задачи в локальном или глобальном смысле. В первом случае производится поиск только одного решения из некоторой области Парето-множества, при этом возникает сложность выбора этой области, во втором случае множество ограничивается числом точек, достаточно покрывающим весь Парето-фронт, а последующий выбор используемых решений может осуществляться экспертом. Можно использовать алгоритм, описанный в [8].
Для задачи составления учебного расписания (особенно в больших организациях) необходимость решения в глобальном смысле сомнительна:
– во-первых, большое число критериев требует значительных вычислительных затрат для достаточного покрытия всего Парето-фронта;
– во-вторых, некоторые критерии сильно различаются по степени своей значимости, что делает множество полученных результатов заведомо бесполезным;
– в-третьих, большое количество полученных решений требует усилий экспертов для выбора итогового результата, что уменьшает эффективность автоматизации процесса в целом.
Вследствие этого больший интерес представляет решение задачи в локальном смысле, для которого необходимо изначально определить единственное направление оптимизации среди множества критериев.
Для решения многокритериальных задач в локальном смысле применяются различные методы скаляризации, заключающиеся в сведении задачи к однокритериальной, при помощи некоторой вспомогательной функции. В большинстве работ, целевая функция представляет собой взвешенную сумму штрафов [1, 4, 10]. В общем виде такая функция выглядит следующим образом:
,
где r – расписание,
fi – штрафная функция i-го критерия,
ωi – вес штрафа i-го критерия,
n – количество критериев,
R – множество расписаний.
Критерии оптимизации расписания
|
Иерархия критерия |
Описание критерия |
Объект. / Субъект. |
Критич. / Качест. |
||
|
Целостность расписания |
Субъект в одну временную позицию участвует только в одном занятии |
Объект. |
Критич. |
||
|
В аудитории в одной временной позиции происходит ограниченное число занятий (число зависит от аудитории) |
Объект. |
Критич. |
|||
|
Пригодность аудиторий |
Наличие средств обучения |
Наличие в аудитории необходимого для потока количества мест |
Объект. |
Критич. |
|
|
Наличие специального оборудования и программного обеспечения |
Объект. |
Критич. |
|||
|
Приемлемость времени перехода |
Время перехода между аудиториями смежных занятий не превышает время перерыва между этими занятиями |
Объект. |
Критич. |
||
|
Время перехода между аудиториями смежных занятий минимально |
Объект. |
Качест. |
|||
|
«Справедливость» расписания |
Соблюдена минимальная разница выполнения критериев для всех субъектов с учетом важности субъекта |
Объект. |
Качест. |
||
|
Качество организации времени |
В течение недели |
Возможность участия субъекта при проведении занятия в определенный день |
Субъект. |
Критич. |
|
|
Отсутствие свободных дней, смежных с учебными («Окна в неделе») |
Субъект. |
Качест. |
|||
|
В течение дня |
Отсутствие свободных временных позиций, смежных с занятыми в течение дня («Окна») |
Субъект. |
Качест. |
||
|
Расположение занятий в одной половине дня (принадлежность к смене) |
Субъект. |
Качест. |
|||
|
Качество организации нагрузки |
Объем |
Отсутствие единственного занятия в день |
Субъект. |
Качест. |
|
|
Отсутствие превышения максимального количества лекций в день |
Субъект. |
Качест. |
|||
|
Отсутствие превышения максимального количества занятий в день |
Субъект. |
Качест. |
|||
|
Распределение |
В течение недели |
Равномерное чередование дисциплин |
Субъект. |
Качест. |
|
|
Соответствие распределения нагрузки недельной динамике работоспособности человека |
Субъект. |
Качест. |
|||
|
В течение дня |
Проведение лекций перед другими типами занятий |
Субъект. |
Качест. |
||
|
Занятия с физическими нагрузками расположены последними |
Субъект. |
Качест. |
|||
В данном подходе можно выделить два существенных недостатка. Первый заключается в невозможности охвата вогнутых областей Парето-фронта [7], в результате чего в ходе оптимизации некоторые недоминируемые решения могут стать недостижимыми. Второй недостаток связан со сложностью подбора весовых коэффициентов или полной непригодностью такого подхода в виду нелинейности рассматриваемых критериев.
В работе [4] авторы задействуют аппарат нечеткой логики для вывода результирующей оценки расписания. Все требования группируются по степени важности на 4 приоритета, после чего экспертом задается набор правил вида «если требования высокого приоритета выполнены, выше среднего выполнены, среднего не выполнены, низкого не выполнены, то качество расписания ниже среднего». На основе данных правил и суммы штрафов для каждого приоритета производится нечеткий вывод конечного результата.
Данный подход позволяет более гибко производить оценку расписания с учетом различных приоритетов, однако полностью сводит критерии из одной группы (приоритета) в один класс эквивалентности, не учитывая их нелинейность и разнородность. Этой проблемы можно было бы избежать, сделав число групп равным числу критериев, однако количество правил, необходимых для осуществления оценки, растет экспоненциально и доходит до неприемлемых на практике значений.
Для минимизации числа правил и более точного формирования итоговой оценки предлагается ввести иерархичную структуру критериев, основываясь на том, что ряд критериев имеет общие черты, позволяющие объединить их в группу более высокого уровня. При этом система нечеткого вывода будет задействована для вычисления оценки составных критериев, начиная от низшего уровня, пока не будет получена итоговая оценка всего расписания. Таким образом, гибкость подхода с использованием нечеткой логики будет направлена на вычисление оценки для трудносравнимых разнородных критериев, а проблема запредельного числа правил решится благодаря малой численности элементов каждого из составного критерия.
Для функционирования предлагаемой системы оценки качества расписания необходимо составить иерархическую структуру критериев. Пример такой структуры представлен в таблице. Все критерии в предложенной иерархии разделены на критичные и качественные. Первые представляют собой жесткие ограничения, невыполнение которых приводит к недопустимости расписания. Вторые влияют исключительно на качественную составляющую оценки. Кроме того, каждый критерий является либо субъективным, либо объективным. Как правило, субъективные критерии имеют разную важность в зависимости от субъекта. Данную особенность можно учитывать при разработке автоматизированной системы в виде возможности учета предпочтений каждого из субъектов (например, предпочтения по парам или месту проведения занятий).
Основой системы является база нечетких правил, отражающая эмпирические знания экспертов, принимающих участие в ее составлении. Каждое правило имеет вид «Если условие, то заключение», где условие и заключение являются нечеткими высказываниями, которые могут состоять из нескольких лингвистических переменных, соединенных конъюнкцией или дизъюнкцией.
Так, например, для вычисления показателя выполнения критерия «Качество организации времени в течение дня» необходимо определить условие, включающее две лингвистические переменные C1 = «Критерий отсутствия окон», C2 = «Критерий принадлежности к определенной смене» и заключение, включающее одну лингвистическую переменную С3 = «Качество организации времени в течение дня». В случае хранения информации о расписании в БД запросы можно реализовывать способом, описанным в [5]. Множеством допустимых значений переменных С1 и С2 является {«Выполнен», «Не выполнен»}, а допустимых значений переменной С3 – {«Отличное», «Хорошее», «Удовлетворительное», «Неудовлетворительное»}. При этом для каждого значения лингвистической переменной должна быть определена функция принадлежности, которая отражает степень принадлежности входного четкого значения к нечеткому множеству:
,
где X – четкое множество входных значений.
Множество входных значений может быть представлено количеством окон в расписании, процентным соотношением занятий первой и второй смены, минимальным промежутком времени между повторением одной и той же дисциплины и т.п.
В итоге база экспертных правил для вычисления показателя выполнения критерия «Качество организации времени в течение дня» будет содержать 4 правила вида: «если критерий отсутствия окон выполнен и критерий принадлежности занятий к необходимой смене выполнен, то качество организации времени отличное». Число правил определяется по формуле
N = PC,
где C – количество лингвистических переменных условия,
P – количество допустимых значений переменных условия.
К преимуществам данного подхода можно отнести высокую гибкость и простоту настройки процедуры оценивания для человека. Из недостатков следует отметить хоть и приемлемое, но достаточно большое количество экспертных правил, которое необходимо задать до функционирования системы.
Заключение
В работе рассмотрены проблемы построения единого учебного расписания, что особенно актуально в условиях создания в современной России крупных образовательных центров, имеющих в своем составе межкафедральные и межфакультетские лаборатории общего пользования. Укрупнение образовательных учреждений приводит к появлению специфичных критериев качества расписания, таких как ограничение времени перехода между аудиториями, ограничение количества занятий определенного типа в течение дня и так далее.
С учетом этих критериев разработана математическая модель расписания на основе теории множеств и критерии оценки качества расписания, полученного на основе такой модели. Рассмотрены 18 наиболее значимых критериев, влияющих на качество расписания. Формулировка критерия с использованием лингвистических переменных рассмотрена на примере критерия «Качество расписания в течение дня». Предложенные критерии классифицированы и сведены в иерархическую структуру, которая в дальнейшем позволит упростить разработку автоматизированных программных комплексов составления расписаний.
Работа выполнена при финансовой поддержке РФФИ – проекты № 16-01-00390, № 16-01-00391.