УДК 658.512.2:681.3.06

Скалозуб В.В, Нечай В. Я.,  Разумов С.Ю.

Днепропетровский национальный университет железнодорожного транспорта им. акад. В. Лазаряна.

АВТОМАТИЗАЦИЯ СОСТАВЛЕНИЯ РАСПИСАНИЯ
ЗАНЯТИЙ ВЫСШИХ УЧЕБНЫХ ЗАВЕДЕНИЙ
ГЕНЕТИЧЕСКИМИ АЛГОРИТМАМИ

В работе представлены специализированные генетические алгоритмы (ГА), основанные на использовании ЛПt-последовательностей, предназначенные для решения задачи составления расписания занятий высших учебных заведений.

Проблема составления расписания занятий сводится к сложной комбинаторной задаче высокой размерности. Для ее решения предложены специализированные ГА и соответствующее программное обеспечение. Особенностью метода решения является предаставление задачи составления расписания в форме модели задачи о назначении с дополнительными ограничениями. Здесь использование специализированных ГА позволяет автоматизировать процесс составления расписания занятий и добиться повышения его качества.

Исходными данными для применения ГА являются: учебный план и учебная нагрузка преподавателей (дисциплина; вид занятий; количество часов в неделю; список групп; преподаватель). Каждая ячейка сетки расписания рассматривается как исполнитель работ и характеризуется такими параметрами, как номер недели, день недели, номер ленты, номер аудитории.

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

Хромосомы могут содержать недопустимые значения «генов», при которых одновременно в одной и той же группе могут проводить занятий разные преподаватели, т.е. популяция может содержать недопустимые решения. Во избежание недопустимых значений «генов» вводится оценка хромосомы fitness-функцией, которая задается суммой «штрафов», определяющихся при декодировании хромосомы. Целью генерации популяции является составление расписание занятий с минимальным значением функции приспособленности. В работе использованы ЛПt-последовательности для операций мутации, кроссовера и инверсии. Цель данной модификации - повышение эффективности поиска, разнообразив элементы с наилучшими свойствами; не позволить преждевременно закончить процесс эволюции.

Метод автоматизированного составления расписаний занятий на основе модели задачи о назначении с ограничениями, применением ГА программно реализован и апробирован для отдельных учебных подразделений ВУЗа.