Ключевые слова: учебный план, генетический алгоритм, составление расписания занятий, диаграмма классов, группа, учебная дисциплина.
Составление расписания, как одна из составляющих организации учебного процесса, регламентирует трудовой ритм, влияет на творческую отдачу преподавателей, поэтому его можно рассматривать как фактор оптимизации использования ограниченных ресурсов — преподавательского состава и аудиторного фонда. Поскольку все факторы, влияющие на расписание, практически невозможно учесть, а интересы участников учебного процесса разнообразны, задача составления расписания является многокритериальной с нечетким множеством факторов. Решение таких задач, как правило, осуществляется в два этапа: получение оптимального (с точки зрения используемых критериев) варианта и его дальнейшая обработка человеком (диспетчером) с целью максимального учета неформализованных факторов.
В данной статье описан процесс и приведены результаты разработки системы, использующей генетический алгоритм для составления расписания высшего учебного заведения (ВУЗ). В полученное расписание могут быть внесены изменения диспетчером для устранения возможных неучтенных факторов [1].
Задача составления расписания ВУЗа характеризуется мягкими и жесткими ограничениями [2]. Мягкие ограничения — это те, которые можно нарушить при составлении расписания, однако исходные данные все еще учтены, чего нельзя сказать о жестких ограничениях. При нарушении жестких ограничений расписание нельзя считать допустимым для дальнейшего анализа и внесения изменений. Пространство поиска решений для задачи составления расписаний большое, но возможными считаются решения, которые не нарушают жесткие ограничения, а также по возможности удовлетворяют мягким ограничениям. В результате должно быть выбрано оптимальное из возможных решений. Перечислим учитываемые в данной статье мягкие и жесткие ограничения.
Мягкие ограничения:
– более или менее одинаковая нагрузка предоставляется всем группам;
– выполнение учебного плана для каждой группы.
Жесткие ограничения:
– один преподаватель не может вести занятия в двух группах одновременно;
– группа не может иметь более одного занятия одновременно.
Необходимо построить расписание, обеспечивающее проведение всех занятий с минимальным количеством «окон» для студентов, которое удовлетворяет требованиям учебного плана, утвержденного Министерством образования и науки Украины.
Входными данными в задаче составления расписания учебных занятий являются:
а) множество преподавателей;
б) множество учебных групп;
в) множество учебных дисциплин для каждой группы
г) учебный план, который каждой учебной группе ставит в соответствие количество часов по каждому из предметов, которые изучаются.
Основой для составления расписания служит учебная дисциплина, которая имеет следующие свойства: название дисциплины, учебная группа, в которой он преподается, ФИО преподавателя, специализирующегося на этой дисциплине. Расписание представляет собой таблицу, ячейки которой также пронумерованы специальным образом. Предварительно фиксируется структура будущего расписания, то есть указываются ячейки, которые не будут участвовать в построении расписания (выходные, праздничные дни, каникулы). Также, предварительно указывается количество занятий в день. Если количество ячеек, участвующих в расписании, в точности равно количеству учебных часов в неделю в данной группе, то это будет гарантировать отсутствие «окон» в учеников.
В разрабатываемой программе диспетчер имеет возможность:
– ввести\отредактировать данные о группе;
– ввести\отредактировать данные об учебном плане;
– ввести\отредактировать данные о преподавателях;
– получить готовые варианты расписания.
На этапе проектирования были составлены диаграмма последовательности и диаграмма классов для разрабатываемой системы составления расписания ВУЗа.
На рисунке 1 показана диаграмма последовательности, которая отображает участвующие во взаимодействии объекты и последовательность сообщений, которыми они обмениваются.
Диспетчер вводит через Excel файл данные о группе, учебном плане, преподавателях и сохраняет их. Для запуска приложения необходимо открыть папку с исполняемым файлом и ввести команду в командную строку. После введения команды, приложение запускается, берёт, введенные диспетчером, данные и использует их для отработки генетического алгоритма для составления расписания ВУЗа. В результате работы приложения обновляется Excel файл с расписанием. Диспетчер получает сообщение об успехе выполнения программы.
Рису. 1. диаграмма последовательности
Диаграмма классов (рис. 2) показывает основные классы разрабатываемой системы составления расписания ВУЗа и их методы.
Рис. 2. Диаграмма классов
Рассмотрим каждый из классов подробнее.
Класс GetData.java предназначен главным образом для получения входных данных от пользователя через файл Excel и предоставления их рабочим классам генетического алгоритма для составления расписания.
Класс StudentGroup.java имеет идентификатор, название группы студентов, количество дисциплин, массив названий дисциплин и количество часов обучения, необходимых для каждой дисциплины в неделю. Он также содержит идентификаторы преподавателей, закрепленных за этими дисциплинами.
Класс Teacher.java предназначен для хранения информации о преподавателе: идентификатор, имя, дисциплины, которые он/она может преподавать.
Класс Subject.java содержит информацию о дисциплине: название, список преподавателей, которые могут преподавать эту дисциплину.
Класс Slot.java является основной единицей генетического алгоритма. Он представляет собой единую характеристику гена. Для задачи составления расписания слот — это одна ячейка в расписании.
Класс TimeTable.java содержит массив слотов. Это класс для генерации новых слотов сначала для каждой учащейся группы.
Класс Gene.java это основной компонент хромосомы и состоит из последовательности номеров слотов. Представляет собой вариант расписания для одной учебной группы.
Класс Chromosome.java является массивом генов, который подвергается кроссоверу и мутации, для создания лучших вариантов расписания.
Класс Fitness.java представляет собой критерий качества хромосомы или функцию приспособленности.
Класс SchedulerMain.java является классом генетического алгоритма, который вызывает другие классы, а также вызывает методы для кроссовера и мутации.
После этапа проектирования была выполнена программная реализация системы, которая составляет расписания для ВУЗа с помощью генетического алгоритма. На рисунке 3 изображена структура программы.
Рис. 3. Структура программы
Для начала диспетчеру нужно заполнить файл с входными данными определенного формата. На рисунке 4 и 5 изображена структура файла inputData.xlsx.
Рис. 4. Входные данные группы
На первом листе «Группа» каждый столбец содержит информацию о группе. В первой строке указывается название группы. В остальных строках — название дисциплины и количество часов в неделю, причем одна ячейка соответствует одной дисциплине. Формат записи в ячейку такой: «Название_дисциплины Количество_пар_в_неделю», например, «ООП 2».
Второй лист файла inputData.xlsx содержит информацию о преподавателях, где одна строка соответствует одному преподавателю. В первом столбце указывается фамилия и инициалы преподавателя, в последующих — названия дисциплин, которые он может вести. Важно, чтобы названия дисциплин на обоих листах совпадали.
Рис. 5. Входные данные преподавателя
Для пользователя был сформирован исполняемый файл, который следует запускать следующим образом. В папке, где находится исполняемый файл, открываем командную строку и вводим команду «java -jar GA_SchedulerMaker-1.0.jar». На рисунке 6 изображен результат работы программы — файл TimeTable.xlsx, который обновляется после каждого запуска программы.
Рис. 6. Результат работы программы
Для каждой группы создан отдельный одноименный лист. Каждый столбец соответствует одному дню недели, в строках указывается название предмета и фамилия преподавателя. Сотруднику учебного отдела предоставляется возможность выбрать лучший вариант расписания.
Выводы
Спроектирована и реализована система, использующая генетический алгоритм для составления расписания высшего учебного заведения. Предусмотрена возможность диалога между системой и пользователем: система предлагает варианты расписания, а окончательное решение принимает методист учебного отдела.
Преимуществом использования генетического алгоритма перед другими методами составления расписания является учет структурных особенностей объектов расписания (преподаватели, группы, дисциплины), между которыми существуют сильные связи, обусловленные спецификой организации учебного процесса.
Литература:
- Muller, T. Some Novel Approaches to Lecture Timetabling / T. Muller // In Proceedings of the 4th Workshop of Constraint Programming for Decision and Control, CPDC'2002. Gliwice. − September 2002.
- Абухания, А. Ю. Модели, алгоритмы и программные средства обработки информации и принятия решений при составлении расписаний занятий на основе эволюционных методов: специальность 05.13.01 «»: диссертация на соискание ученой степени кандидата технических наук / Абухания Амер Юсеф;. — Новочеркасск, 2016. — 231 c. — Текст: непосредственный.
