Hybrid approach to solving of the automated timetabling problem in higher educational institution = Гібридний підхід до розв’язання задачі автоматизованого складання розкладу вищого навчального закладу

Abstract

У роботі описано гібридний підхід до розв’язання задачі автоматизованого складання розкладу вищого навчального закладу на основі методу мурашиних колоній, генетичного алгоритму та методу деформованого багатогранника. Метод мурашиної колонії є основою даного алгоритму, що формує початкову популяцію для генетичного алгоритму. Комбінація даного метода з генетичним алгоритмом та методом деформованого багатогранника спрямована на усунення таких недоліків даного метода як невизначеність часу збіжності алгоритму та сильна залежність результатів роботи методу від початкових параметрів пошуку, які зазвичай підбираються експериментально. Метод деформованого багатогранника використовується для знаходження параметрів методу мурашиних колоній. Використання генетичного алгоритму дозволяє зменшити час роботи алгоритму та збільшити ймовірність попадання в глобальний оптимум. Складання розкладу навчального процесу у вищому навчальному закладі (ВНЗ) є важливою складовою системи забезпечення навчального процесу, оскільки від якості розкладу залежить комфорт учасників навчального процесу та його якість і ефективність, отже, розроблення методів генерації комп’ютерного розкладу є актуальною темою. Предметом дослідження є адаптивні методи автоматичного складання розкладу ВНЗ. Мета роботи – розроблення гібридного підходу до розв’язання задачі автоматизованого складання розкладу вищого навчального закладу. Результати – розробка та дослідження гібридного методу та програмна реалізація системи складання розкладу навчального процесу в університеті з використанням розглянутих методів.

The paper describes a hybrid approach to solving of the automated timetabling problem in higher educational institution based on the ant colony optimization, the genetic algorithm, and the Nelder–Mead method. The ant colony method is the basis of this algorithm, which forms the initial population for the genetic algorithm. The combination of this method with the genetic algorithm and the Nelder–Mead method reduces time of the convergence of an algorithm and eliminates the strong dependence of the results on the initial search parameters, which usually are selected experimentally. The Nelder–Mead method is used to find the parameters of the ant colony optimization method. Use of the genetic algorithm allows for reducing of algorithm running time and increasing of global optimum finding probability. The educational process timetabling in higher school is an important component of the educational process assurance system, since the schedule quality determines the comfort of the educational process participants and its quality and effectiveness. Therefore, the development of methods for computer-aided timetable generation is an important challenge. The subject of study is adaptive methods of automated university timetabling. The objective of the work is development of a hybrid approach to addressing the problem of automated timetabling in university. The results are development and research of a hybrid method and software for university timetabling that been implemented this method