Введение. Вопрос создания оптимального расписания для университета стоит очень давно. Расписание является неотъемлемой частью при планировании учебного процесса, так как без него не может функционировать ни одно учебное заведение. Создание расписания и организация учебного процесса занимает много времени для человека, поскольку необходимо учитывать множество различных факторов, в качестве которых могут выступать комфортные условия обучения у студентов, удобное время проведения занятий для преподавателей, ресурсы университета и т.д. Подходы к решению задач со столь большим количеством учитываемых параметров можно отнести к технологиям больших данных [1,2], а по сложности генерация расписания относится к классу NP-полных задач. Современные технологии позволяют автоматизировать и ускорить этот процесс в тысячи раз. Это стало возможно с появлением эвристических методов, одним из которых является рассматриваемый в данной статье генетический алгоритм. Для таких алгоритмов имеется сильная зависимость под конкретное учебное заведение, что не позволяет сделать универсальную систему. Эти алгоритмы помогают не только автоматизировать создание расписания, но и создать оптимальное расписание с учетом многих предпочтений. В данной обзорной статье будут рассматриваться материалы, взятые из других источников.
Математическая часть. При составлении расписания существуют обязательные и дополнительные, так называемые желательные, требования [3,4,5], которые могут меняться в зависимости от учебного заведения.
Обязательные требования:
- Аудитория должна вмещать всех студентов, обучающихся в текущий период.
- Аудитория должна быть оборудована соответствующим образом.
- Отсутствие не состыковок в расписании.
- Полное выполнение учебного плана.
- У преподавателей и студентов не должно быть больше 3-х лекций в день.
- Желаемое количество пар в день не более 5 (в субботу - не более 3).
Дополнительные (желательные) требования:
- У студентов отсутствуют «окна».
- В начале учебного дня рекомендуется проводить лекционные занятия, затем –практические.
- Минимальное количество переходов между корпусами/аудиториями.
- Пожелания преподавателей.
Для формирования расписания необходимо иметь начальные данные и математическую модель, которая позволит просчитать и избежать накладок по составлению расписания.
Начальная информация — это множества [6,7]:
- Преподаватели
- Читаемые дисциплины
- Группы
- Временные интервалы
- Аудитории
В качестве теоретико-множественной модели можно рассматривать функцию, отображающую декартово произведение множеств на булево множество.
, где 
, будет означать, что по 
дисциплине для группы 
преподавателем 
проводится занятие в 
аудитории во время пары 
. Рассмотрим основные сущности, необходимые для планирования любого расписания в университете:
1. Аудитории. Во всех вузах аудитории делятся на лекционные 
, семинарные 
и лабораторные 
. В исходной информации необходимо учитывать эти факторы, поэтому можно расписать наше множество аудиторий следующим образом:
Деление аудиторий только на три подмножества не всегда является достаточным, так как в аудитории может присутствовать не одна группа, а поток одной специальности или поток, состоящий из различных специальностей, что характерно для лекционных занятий. Поэтому стоит разбить подмножество 
на аудитории с большой вместимостью 
и средней вместимостью 
. Лабораторные занятия нельзя проводить в аудиториях, в которых нет необходимого оборудования. Такие лабораторные аудитории принадлежат к какой-либо кафедре, поэтому разделим наше подмножество 
на 
подмножеств, где – число кафедр.
Таким образом получается:
Каждая аудитория имеет расположение – корпус при наличии нескольких, этаж и сам кабинет, пример 5 – 108, где первая цифра показывает в каком корпусе находится аудитория, 1 – показывает на каком этаже, 08 обозначает номер аудитории. Таким образом для формального описания аудитории введем 3-арный кортеж:
где 
- корпус, 
- номер аудитории, 
- тип аудитории.
2. Временной интервал. Расписание обычно составляется на один семестр, в котором известно количество недель обучения, учебных дней и пар в день. Поэтому каждую составляющую множества T можно обозначить в виде 3-арного кортежа:
где 
– номер недели, 
- номер дня недели, 
- номер пары в учебном дне.
3. Множество, связывающее между собой преподавателей, читаемые дисциплины и группы. При создании расписания в нашем распоряжении есть список преподавателей, учебных групп и проводимых для них занятий. Благодаря этим данным мы можем сделать вывод в каких группах какие предметы должны быть проведены и какими преподавателями. Из-за всех этих связей можно выделить новую структуру – занятие, представляющее собой множество 
.
, 
- преподаватель, 
- дисциплина, 
- группа, 
- признак поточного занятия, 
- признак подгруппы, 
- число занятий, 
-количество пар в неделю, 
- число пар одного занятия, 
- специфика занятия, 
- допустимое подмножество аудиторий.
Таким образом, при составлении расписания нам необходимо три множества 
, которые можно определить следующими векторами:
- номер аудиторий для цикла занятий 
.
- номер пары из цикла первого занятия.
Математическая модель создания расписания для учебного заведения выражается в задаче нелинейного булева программирования с ограничивающими условиями. Такая форма способствует принятию во внимание все условия, предъявляемые к данной модели.
Ограничивающие условия:
- Отсутствие проблем для ведения занятий у преподавателей и групп в допустимых аудиториях.
- Недопустимость «окон» в учебных днях для обучающихся.
- Максимальное число занятий в день не должно превышать указанного порога.
- Аудитория должна соответствовать типу проводимого предмета.
- Полное выполнение учебного плана.
Математическая модель приведённых выше ограничивающих условий очень подробно приведена в статье [8].
Генетический алгоритм и этапы построения модели расписания. Теперь поговорим непосредственно о генетическом алгоритме и его основных этапах реализации. Здесь каждая особь является одним из допустимых вариантов для решения указанной проблемы, а в нашем случае, расписания.
Благодаря математической модели мы определили, что особь будет состоять из двух хромосом: первая - вектор 
, вторая - вектор 
.
В каждой хромосоме имеются гены, которые представлены целом числом, и каждый номер гена соответствует определенному занятию и характеризует его, т.е. в первой хромосоме находится номер аудитории из подмножества допустимых аудиторий для данного занятия, а во второй хромосоме находится время проведения пары из допустимого подмножества временных интервалов.
Алгоритм будет содержать следующие этапы:
- Формирование начальной популяции.
Формирование заданного количества особей происходит в случайном порядке, где поочередно присваиваются первой и второй хромосоме каждого гена значения из допустимых вышеопределенных множеств.
- Селекция особей.
На этом шаге происходит отбор максимально подходящих особей популяции (форм расписания), которые имеют наиболее приемлемые значения функций пригодности по отношению к оставшимся элементам популяции.
Функция пригодности – оценка значений пригодности особей и выбор лучших, более приспособленных особей. Свободные места в данной популяции заполняются в результате следующего шага.
- Скрещивание (кроссинговер).
На данном этапе выполняется оператор кроссинговера – языковой механизм, позволяющий на основе скрещивания хромосом родительских особей создавать хромосомы особей потомков. Для всех отобранных в случайном порядке пар особей разыгрывается позиция гена, также называемая – локус, и происходит замена участков генетического кода между родительскими хромосомами. Общее число генов и порядок их следования в хромосоме не меняется благодаря тому, что мы жестко задавали специфику занятия. После процедуры скрещивания не нужно производить дополнительных проверок на правильность выбора аудиторий или номера пары.
- Мутация.
Данный оператор добавляет некоторое разнообразие в существующую на этом шаге популяцию и, тем самым, расширяет пространство поиска наиболее подходящего варианта расписания путем применения оператора мутации. В алгоритме генерации этот оператор изменяет значение нескольких генов на другие допустимые значения для этого гена. После проведения мутации особи остаются допустимыми по установленным требованиям.
- Проверка условия останова алгоритма.
Полученное в результате прошлых шагов алгоритма поколение называют популяцией потомков, которая заменяет родительскую популяцию, после чего проверяется условие на остановку алгоритма. Благодаря такому условию предлагается достижение некоторого процента приспособленности, так как в течение выполнения алгоритма остаются наиболее приспособленные особи и их количество и качество со временем достигнет нужного уровня. При истинности условия остановки в алгоритме происходит переход к следующему этапу, в противном случае - переход к этапу номер 2 и процесс нахождения оптимального расписания продолжается.
- Выбор максимально подходящей особи.
В финальном поколении выбирается особь, которая максимально удовлетворяет поставленным требованиям к расписанию, что и является решением задачи.
Вывод. По полученным данным, взятым из рассматриваемых источников, видно, что генерация расписания на основе генетических алгоритмов позволяет сократить время создания расписания до нескольких минут, что в сравнении с ручным составлением, которое занимает до нескольких недель, на порядок выше. Помимо этого, такая автоматизация позволяет учитывать интересы обеих сторон: и преподавателей, и студентов [9].
Процесс автоматизации генерации расписания достаточно трудоёмок и энергозатратен, но построив математическую модель с учётом необходимых требований и реализовав программу или программный комплекс с использованием генетического алгоритма один раз, возможно в будущем составлять расписание не за несколько дней, а за несколько минут.