HYBRID APPROACH TO SOLVING OF THE AUTOMATED TIMETABLING PROBLEM IN HIGHER EDUCATIONAL INSTITUTION
DOI:
https://doi.org/10.26906/SUNZ.2020.2.060Keywords:
Multi-Objective Optimization, Ant Colony Optimization, Genetic Algorithm, Nelder–Mead Method, Timetable, TimeslotAbstract
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 methodDownloads
References
Khasukhadzhiyev A.S., Sibikina I.V. Obobshchennyy algoritm sostavleniya raspisaniya v vuze s uchetom novykh trebovaniy federal'nykh gosudarstvennykh obrazovatel'nykh standartov // Vestnik Astrakhan. gos. tekhn. un-ta. Ser. upravleniye, vychisl. tekhn. inform., 2016, No 3. Pp. 78–86.
PATAT Conferences. URL: https://patatconference.org.
Dvoryankin A.M. Chalyshev V.S. Obzor metodov sostavleniya raspisaniya vuzov // Izv. VolgGTU. Seriya Aktual'nyye problemy upravleniya, vychislitel'noy tekhniki i informatiki v tekhnicheskikh sistemakh: mezhvuz. sb. nauch. st., 2011. Vyp. 11, No 9. Pp. 110-113.
Tomashevsʹkyy V .M. Novikov YU.L., Kaminsʹka P .A. Skladannya rozkladiv zanyatʹ u dystantsiynykh systemakh navchannya // Visnyk Natsionalʹnoho tekhnichnoho universytetu Ukrayiny "Kyyivsʹkyy politekhnichnyy instytut". Ser.: Informatyka, upravlinnya ta obchyslyuvalʹna tekhnika, 2010. Vyp. 52. Pp. 118-130.
Lagosha B.A., Petropavlovskaya A.V. Kompleks modeley i metodov optimizatsii raspisaniya zanyatiy v vuze // Ekonomika i matematicheskiye metody, 1993. No 4. Pp. 48-56.
Bania Kumar Rubul, Duarah, Pinkey. Exam Time Table Scheduling using Graph Coloring Approach // International Journal of Computer Sciences and Engineering, 2018. No 6. Pp. 84-93.
Bezginov A.N. Tregubov S.YU. Obzor sushchestvuyushchikh metodov sostavleniya raspisaniy // Informatsionnyye tekhnologii i programmirovaniye. Mezhvuzovskiy sbornik statey, M., 2005. Vypusk 2 (14).
Leite Nuno, Melicio Fernando, Rosa Agostinho. A fast simulated annealing algorithm for the examination timetabling problem // Expert Systems with Applications, 2018. Vol. 122.
Astakhova I.F., Firas A.M. Sostavleniye raspisaniya uchebnykh zanyatiy na osnove geneticheskogo algoritma // Vestnik VGU, seriya: Sistemnyy analiz i informatsionnyye tekhnologii, 2013. No 2. Pp. 93 – 99.
Zhukova M.YU., Al'-Gabri V.M. Avtomatizatsiya postroyeniya raspisaniya ekzamenov VUZa s ispol'zovaniyem geneticheskogo algoritma // Inzhenernyy vestnik Dona, 2017. No3.
Boyko O.M. Evolyutsiyna tekhnolohiya rozvʺyazuvannya zadachi skladannya rozkladiv navchalʹnykh zanyatʹ // Shtuchnyy intelekt, 2006. No 3. Pp. 341 – 348.
Mulyava I. YA. Systema formuvannya rozkladu navchalʹnoho zanyatʹ z vykorystannyam subʺyektyvnykh perevah // International scientific journal, 2016. No 7. Pp. 22-27.
Ustenko S.V., Bibko O.O. Vykorystannya metodu murashynoyi koloniyi dlya rozvʺyazannya optymizatsiynykh zadach. Naukovyy visnyk NLTU Ukrayiny, vyp. 25, vyp. 3, Berezenʹ, 2015. Pp. 351-359.
Thepphakorn T, Pongcharoen P, Hicks C. An ant colony based timetabling tool // International Journal of Production Economics, 2014, No 149(3). Pp. 131-144.
Yurchak I.YU., Moskovych T.R. Doslidzhennya henetychnykh alhorytmiv ta zastosuvannya yikh v avtomatyzovaniy systemi rozpodilu navantazhennya dlya vykladachiv i studentiv. URL: http://eom.lp.edu.ua/sntk/doc/ksm2018/moskovytch.pdf.
