Rybnica, Transnistria
Rybnica, Transnistria
Rybnica, Transnistria
Rybnica, Transnistria
GRNTI 50.43 Системы автоматического управления, регулирования и контроля
The article entitled “The mathematical and software of decision support making during the process of formation the schedule of education activities” is devoted to the problem of automating the formation of a classroom schedule in a higher educational institution. The article consists of an introduction, five sections, conclusions and references. The first section provides a justification for the choice of implementation method. The second section is devoted to the description of the algorithms used. The third section indicates the means of implementing a software product, presents an information-logical database model for the “Schedule” system. The fourth section describes the logical structure of the software product. The fifth section presents the results of the implementation and testing of the software product. The purpose of the study is the development and implementation of a software system designed to automate the process of compiling a classroom schedule in the branch of the Transdniestrian State University. T.G. Shevchenko in Rybnitsa. The object of the study is the automation of the formation of the schedule of classrooms. The subject of the research is the implementation of a genetic algorithm as one of the adaptive search methods for solving functional optimization problems in order to automate the generation of a schedule. At the stage of the research of the subject area, the methodology of scheduling in universities was studied. There are not so many developments in the automation of scheduling tasks. This suggests that this task is relevant and unified approaches to its solution still does not exist. A new approach to the implementation of solving the problem of finding the optimal schedule was the application of an expert approach based on the use of a genetic algorithm. The authors describe the feasibility of using the genetic algorithm as one of the adaptive search methods for solving functional optimization problems in order to automate the formation of the schedule. Evaluating the work as a whole, it can be argued that the practical significance and prospects of development of this research direction is obvious.
genetic algorithm; automation of scheduling; information and logical model
Введение
Корректность расписания зависит от того, насколько точно и правильно расставлены дисциплины в сетке часов в соотвествие с психологическими и физиологическими особенностями студентов. При составлении расписания обязательно следует обратить внимание на то, чтобы практические занятия проводились после лекционных, а лабораторные – после практических занятий. Такой подход гарантирует повышение эффективности использования учебного времени. В работе проведено обоснование применения генетического алгоритма как наиболее оптимального из существующих методологий. Обоснованный метод показал свою высокую эффективность при программной реализации.
Цель исследования – разработка и реализация программной системы, предназначенной для автоматизации процесса составления расписания аудиторных занятий в филиале Приднестровского государственного унивеситета им. Т.Г. Шевченко в г. Рыбнице.
Объект исследования – автоматизация формирования расписания аудиторных занятий.
Предмет исследования – реализация генетического алгоритма как один из адаптивных
методов поиска для решения задач функциональной оптимизации с целью автоматизации формирования расписания.
На этапе исследования предметной области была изучена методика составления расписания в вузах. Разработок в области автоматизации задачи составления расписания не так много. Это говорит о том, что данная задача является актуальной и единых подходов к ее решению до сих пор еще не существует. Новым подходом в реализации решения задачи поиска оптимального расписания явилось применение экспертного подхода, основанного на использовании генетического алгоритма.
1. Обоснование выбора метода реализации
Расписание аудиторных занятий – это документ, регламентирующий работу студентов, профессорско-преподавательского состава филиала, всего учебного заведения, распределяющий содержание учебного плана и рабочих программ по календарным дням учебного года и обеспечивающий их реализацию. Разрабатываемое расписание должно удовлетворять педагогическим требованиям, основанным на принципах аналитической дидактики и кибернетической аналогии. Оптимально составленное расписание не должно изменяться в течение семестра или учебного цикла, чтобы не нарушить учтенные в расписании межпредметные связи и выполненные требования [2].
Эффективность и качество учебного процесса во многом зависят от качества расписания аудиторных занятий, формирование расписания целесообразно осуществлять в автоматизированном режиме с использованием персонального компьютера. Это в значительной степени облегчит работу по составлению расписания и повысит его качество. Для этого необходимо формализовать перечисленные требования и реализовать их в соответствии с приведенным разработанным алгоритмом.
Для решения существующей проблемы необходимо построить гибкую и легко адаптируемую систему на основе новых принципов, с использованием современных компьютерных технологий. Необходима система, составляющая расписание в соответствии с выбранными критериями и заданными требованиями, т.е. берущая на себя как можно больше функций человека, чтобы расписание приходилось меньше доводить вручную. Данные возможности должны осуществляться также без изменения исходного кода системы. Для покрытия наиболее типичных случаев необходимо выбрать наиболее оптимальный алгоритм, реализующий задачу составления расписания занятий в вузе. Данная система должна иметь возможность дополнения и изменения существующей базы данных и пользовательского интерфейса. Всё это давало бы возможность задавать в каждом вузе требования, отвечающие его условиям, и с помощью подбора и настройки подходящего алгоритма получать требуемое расписание.
В последнее время для решения большинства задач составления расписания учебных занятий предлагается использовать генетический алгоритм решения квадратичной задачи о назначениях с запретами и целевой функцией специального вида.
Формально задачу составления учебного расписания можно поставить следующим образом. Заданы множество преподавателей P, множество учебных групп K, множество учебных дисциплин U, учебный план, фиксирующий количество часов каждого предмета в каждой группе, множество аудиторий A. Необходимо найти такое расписание, которое бы обслуживало все имеющиеся дисциплины и удовлетворяло требованиям профессорско-преподавательского состава к проведению занятий, а также не имело противоречий относительно аудиторного фонда.
Расписание представляется в виде таблицы. Все участвующие в составлении расписания ячейки пронумерованы от 1 до m (m – общее количество ячеек.) Объекты – предметы, подлежащие вставке в расписание, также нумеруются от 1 до n (n – общее количество объектов), причем количество экземпляров каждого объекта равно количеству часов в неделю данной дисциплины (согласно содержанию учебного плана).
Если структура расписания полностью определена, то количество пронумерованных ячеек таблицы совпадает с количеством дисциплин для расстановки (т.е. m = n = N). Заранее зафиксированная структура расписания позволяет гарантировать отсутствие «окон» в расписании, а также позволяет в какой–то степени учитывать санитарно-гигиенические нормы (оптимальное соотношение учебной нагрузки по дням недели).
Для решения поставленной задачи необходимо ввести в рассмотрение матрицу совместимости предметов S:
(1)
Несовместимость предметов выражается в том, что они используют общий ресурс (учитель или кабинет) и поэтому не могут находится в расписании на одной строке. Предполагается что (так как предмет не может появится на строке с i–м номером дважды).
Кроме этого, необходимо в рассматриваемой задаче вводят матрицу сравнения ячеек R:
(2)
В данной ситуации подлежат сравнению ячейки, расположенные на одной строке.
Переменные задачи также определяются матрицей, где
(3)
Целевая функция задачи составления расписания должна максимально минимизировать количеству несовместимых между собой предметов:
SikRjlxijxkl →min (4)
При формировании целевой функции учтены свойства симметричности матриц S и R. При этом необходимо отметить тот факт, что если для выбранной структуры расписания существует непротиворечивый вариант его составления, то оптимальное значение целевой функции равно 0.
Для нахождения решения в рассмотрение вводится множество I(j) – номера тех ячеек, в которых допускается расположение предмета j (в соответствии с учебным планом или пожеланий преподавательского состава). Тогда основные ограничения задачи выглядят следующим образом:
(5)
Каждый предмет назначается ровно в одну ячейку.
(6)
В каждую ячейку назначается ровно один предмет.
Таким образом, была получена модель задачи о назначениях с «запретами» и квадратичной целевой функцией.
Sik Rjl xij xkl →min (7)
(8)
(9)
xij= (10)
Подобная организация задачи позволяет также предусмотреть возможность не фиксировать границы расписания (например, в определенные дни недели проводится минимум 4 занятия, а 5-е занятие только в какой-то один из них), то ограничения (9) разбиваются на две дополнительные подгруппы.
, (10)
где I1 – номера тех ячеек, которые обязательно должны быть заполнены.
, (11)
где I2 – номера тех ячеек, в которых предметы могут отсутствовать.
Составленная задача относится к классу открытых задач о назначении [5] и сводится к обычной задаче путем введения дополнительных переменных.
Как было указано раньше, задача составления расписания учебных занятий является трудноразрешимой (NP–полной), поэтому для решения задачи и получения оптимального решения рекомендуется использовать генетический алгоритм.
Научно доказано, что генетические алгоритмы особенно эффективны при поиске глобального оптимума, поскольку они осуществляют поиск в широком пространстве решений. Кроме того, преимущество генетического алгоритма заключается в том, что он предоставляет целое множество приближенных к оптимальному решений. Если рассматривать полученные результаты, то в дальнейшем можно организовывать поиск по дополнительным критериям, которые не были учтены на начальной стадии постановки задачи. Например, необходимо минимизировать количество получившихся «окон» для преподавателей.
2. Описание применяемых алгоритмов
Разработанный алгоритм состоит из двух подалгоритмов: составления расписания (рис. 1) и осуществления расстановки видов занятий в расписании по приоритету учебного плана и профессорско-преподавательского состава.
Рис. 1. Схема алгоритма составления расписания
Подалгоритм составления расписания аудиторных занятий включает [5]:
ввод основной входной информации (аудиторного фонда кафедр филиала, сеток часов по курсам направлений, сводных данных для планирования и загрузки аудиторий занятиями (по семестрам));
определения видов расписания аудиторных занятий;
определения продолжительности рабочей недели по нечетной и по четной неделям, исходя из ежедневных аудиторных занятий по две пары и т.д.;
выбора продолжительности рабочей недели, при условии выполнения равномерности учебной нагрузки студентов по неделям семестра и загрузки аудиторной работой по дням недели;
определения свободного для выполнения студентами индивидуальных заданий и подготовки к написанию курсовых проектов и работ.
Расстановка видов занятий в расписании происходит согласно нижеприведенному подалгоритму расстановки видов дисциплин с указанием номеров аудиторий, в которых планируются аудиторные занятия (восьмичасовые занятия; поточные учебные занятия; занятия по курсам (физическое воспитание); лекционные занятия по профилирующим дисциплинам учебного плана; практические, лабораторные и семинарские двухчасовые занятия) [4].
Подалгоритм осуществления расстановки видов занятий в расписании базируется на использовании соответствующего приоритета профессорско-преподавательского состава с указанием наименования дисциплин, фамилий преподавателей, номеров аудиторий (см. рис. 1). Приоритетное право преподавателей филиала на расстановку аудиторных занятий устанавливается в зависимости от занимаемой должности и их основных функциональных обязанностей, например: заместители директора; профессоры кафедр; ведущие преподаватели; преподаватели выпускающих кафедр; преподаватели других кафедр филиала; внешние совместители [3]. Все данные, необходимые для работы алгоритма, будут доступны при взаимодействии с информацией, хранящейся в таблицах разработанной базы данных.
Таким образом, автоматизация процесса составления расписания в филиале ПГУ
им. Т.Г. Шевченко в г. Рыбнице позволит значительно упростить этот сложный процесс, так как в течение долгого периода на практике использовался «ручной» подход к составлению учебного расписания. Он предполагает сбор и разделение на классы входной информации, построение вспомогательных таблиц, непосредственно составление расписания, его проверку и корректировку. При таком подходе составителям проблематично в короткие сроки получить расписание, которое бы учитывало основные аспекты филиала и соответствовало всем предъявляемым требованиям, относящимся как к учебному процессу, студентам, так и к самим преподавателям.
3. Выбор средств реализации программного продукта
Для реализации программного продукта была выбрана среда разработки Microsoft Visual Studio, поставляемая вместе с .NET, которая предоставляет необходимый инструмен-тарий для эффективного и быстрого создания приложений с графическим интерфейсом.
Несмотря на то, что C# и .NET предназначены в первую очередь для web-разработки, их также активно применяют для создания приложений, которые должны устанавливаться на устройстве конечного пользователя, где и будет выполняться вся обработка данных. Разработку таких приложений обеспечивает библиотека Windows Forms, позволяющая проектировать графический интерфейс. Поставляемая вместе со средой библиотека базовых классов обладает достаточным функционалом для решения задач практически любой сложности.
Для разработки и управления базой данных (рис. 2) была выбрана СУБД MySQL. Для разработки модели базы данных был задействован электронный ресурс dbdesigner.net.
Рис. 2. Информационно-логическая модель базы данных для системы «Расписание»
4. Описание логической структуры программного продукта
Формирование расписания происходит непосредственно заместителем директора по учебной работе и подчиняющимся ему учебным отделом. Но для того, чтобы собрать все сведения, необходимые для формирования расписания занятий, методистам учебного отдела приходится взаимодействовать с другими структурными подразделениями филиала (рис. 3).
Рис. 3. Структурная модель предметной области
Основные действия при составлении расписания заместителя директора по учебной работе и движение основополагающих документов, используемых при формировании расписания [1], представлены ниже (рис. 4).
Рис. 4. Функции зам. директора по учебной работе при составлении расписания
При формировании базы данных и создании качественного программного продукта недостаточно учитывать только пожелания заказчика (зам. директора по учебной работе). Важно понимать, какой именно информацией система должна управлять. А для этого нужно знать, какие объекты попадают в предметную область проектируемой информационной системы и какие логические связи между ними существуют. Для формирования такого понимания построена информационно-логическая модель предметной области (рис. 5).
Информационно-логическая модель отображает данные предметной области в виде совокупности информационных объектов и связей между ними. Эта модель представляет данные в общем виде, подлежащие хранению в базе данных.
Рис. 5. Информационно-логическая модель предметной области
Проектирование структуры и архитектуры разработанного программного средства привело к выбору методов и средств реализации. Обоснован выбор среды разработки Microsoft Visual Studio и языка программирования C#. Описана методология формирования расписания и обоснована ее реализация на примере генетического алгоритма. Совокупность представленной структурной (см. рис. 3), функциональной (см. рис. 4) и информационно-логической (см. рис. 5) моделей после определения связей между объектами позволяет получить информационно-логическую модель разрабатываемой базы данных, не требующую дальнейших преобразований для создания реляционной базы данных, отвечающей требованиям нормализации.
5. Реализация и тестирование программного продукта
Работа программы начинается с ввода и отображения входной информации, содержащей данные о направлениях, кафедрах, преподавателях, группах и аудиторном фонде. В процессе работы программного продукта обрабатывается индивидуальная нагрузка преподавателей по кафедрам. К выходной информации относится окончательно сформированное расписание аудиторных занятий, которое можно экспортировать в документ Excel для дальнейшей работы.
Разработанный в программе алгоритм постоянно взаимодействует с сервером, на котором размещена разработанная база данных MySQL, обращаясь к основным таблицам: нагрузки ППС, преподавателей, академических групп, кафедр и направлений (рис. 6).
Рис. 6. Главное окно пользовательского интерфейса
Процесс составления расписания зависит от многих факторов, обуславливающих структуру и качество расстановки занятий. Для того, чтобы обеспечить оптимальное распределение предметов в сетке часов, необходимо строго учитывать специфику филиала.
Одним из главных ограничивающих условий, влияющих на процесс составления расписания, является шестидневный рабочий график преподавателей. В то время, когда в филиале использовался ручной способ составления расписания, он предполагал, что для большей части преподавателей, для которых университет – основное место работы, распределение дисциплин будет происходить в пятидневный срок, а на субботу будут вынесены занятия для преподавателей – внешних совместителей. Одно из требований заказчика заключалось в том, чтобы предлагаемая программа формировала расписание подобным образом.
При разработке была предусмотрена возможность смены количества рабочих дней и предложен выбор для указания их количества на текущий момент (рис. 7).
Рис. 7. Панель управления в разделе «Расписание»
Помимо этого, программа предусматривает возможность выбора количества пар, которое можно проводить в любой день недели. Но главные функции выполняются нажатием на соответствующие кнопки (на панели размещены три кнопки (см. рис. 7), отвечающие за определенные манипуляции над расписанием).
Кнопка «Сформировать» позволяет сформировать расписание согласно выбранным заранее данным о количестве рабочих дней, пар, номеру семестра, для которого планируется составить расписание и введенному году обучения.
Результат работы программы представлен на рисунке 8. Готовое расписание, по желанию пользователя, может быть экспортировано не только в файл формата Excel, но и размещён на сайт учебного заведения.
Рис. 8. Окно сообщения об окончании экспорта данных на сайт филиала
Выводы
Результатом выполненного исследования является разработанный программный продукт, обеспечивающий автоматическое формирование расписания аудиторных занятий. Разработанный программный продукт динамически формирует около ста оптимальных вариантов расстановки занятий по курсам и академическим группам. Созданные варианты, получаемые при помощи генетического алгоритма составления расписания, обрабатываются в программе путем подсчета значений целевой функции (fitness function). Идеальный вариант результата работы алгоритма, когда значение целевой функции равняется нулю, то есть в расписании полностью отсутствуют окна, как у академических групп, так и у преподавателей. В случае если подобный вариант расстановки занятий в предлагаемых результатах отсутствует, то пользователю будет предложен вариант, значение целевой функции которого будет минимальным.
В итоге, разработанный программный продукт на основе введенных данных, а также оптимизирующих параметров расчета, позволяет получить наиболее правильный и отвечающий основным требованиям филиала вариант расписания аудиторных занятий. Дальнейшее его развитие может подразумевать разработку отчетности и ручную корректировку пользователем с элементом автоматической проверки расписания на корректность.
1. Automatic scheduling of educational institutions [Electronic resource] / YouTube - Access mode: https://www.youtube.com/ watch? V = wFsqrX1a810.
2. The activities of the university and the faculty at the credit-modular organization of the educational process [Electronic resource] / Factors that determine the correctness of the formation of the schedule of classroom classes in universities - Access mode: http://pandia.ru/text/78/016/11164.php.
3. Erunov B.P. Some issues of formation of the educational process management system [Electronic resource] / B.P. Erunov, I.I. Morkovin. - Technology of the educational process: Interuniversity scientific method. Conf, Orenburg: OGBBS, 2001. - c. 55. - The mode of access to the report: http://vestnik.osu.ru/ 2001_3 / 7.pdf.
4. Kucherenko Y.M. Formation of the optimal schedule of classroom classes in the Rybnitsa branch of the PGU named T.G. Shevchenko / L. Y. Kozak, Y.M. Kucherenko, I.A. Dubinin // Michael-Arkhangelsk readings: X international scientific-practical. conf. - 2015. - №3. P. 81-84.
5. Collection of regulations on the organization of the educational process in PGU named T.G. Shevchenko. – Tiraspol: publishing house of Transnistrian University, 2014.
6. Scheduling at the university [Electronic resource] / Recommendations for scheduling studies - Access mode: http: // irinaonina. narod.ru/5/5_1_8.html.
