Literature review for the topic of automation of scheduling classes and exams in higher education institutions

Introduction. Schedules of classes and exams are crucial components in the training process organization. Their quality directly affects the successful mastering of learning materials and ensures physical and psychological health of the educational process participants. The influence of educational systems features on the problem setting and solving methods under timetabling is considered. The emphasis is upon the timetabling problems in the higher education systems. Materials and Methods. The analytical study results of a number of the Russian and foreign sources on methods and algorithms of the classes and exams timetabling automation are described. These techniques and algorithms are compared from the standpoint of modern system-analysis methods. Schedule is considered as part of the educational process support system, and, in its turn, has features of the system combining such objects as students, teachers, disciplines, and classrooms. The application of the system analysis methods allows allocating essential features of the implemented systems of timetabling, classifying and evaluating them. Research Results. It is found that the tasking of classes scheduling and exams timetabling are practically equivalent and include the timetable quality criterion, soft and hard constraints. Russian sources contain detailed studies of various tasks of the classes timetabling. At the same time, no papers devoted to developing methods and algorithms for the examination schedules are found among these sources. However, foreign sources are largely devoted to the examination schedules. Graph theory methods, heuristic and hybrid optimization algorithms, linear integer programming techniques, system analysis methods, and other modern techniques of discrete mathematics are applied to solve the problems in hand. Discussion and conclusions. In general, in one and the same institution, the dimension, as well as the solution to the examination scheduling problem is less complicated than the classes scheduling. In connection with the expansion of the individualization of the learning process in the Russian educational system, the improvement of the research methods and algorithms relevance for constructing exams schedule is expected.

расписание экзаменов, расписание занятий, NP-полные задачи, автоматизация, ограничения, exam timetable, class schedule, NP-complete problems, automation, constraints

1. Moiseenko, N.A. Transformatsionnoe obuchenie i kholisticheskiy podkhod v informatsionno-obrazovatel'noy srede tekhnicheskogo vuza. [Transformational learning and holistic approach to information-educational environment of technical university.] Engineering Journal of Don, 2013, vol. 27, no. 4, pp. 80 (in Russian).

2. Anisimova, G.B., Romanenko, M.V. IS avtomatizatsii formirovaniya uchebno-metodicheskikh materialov v usloviyakh reformy vysshey shkoly. [IP automation of teaching materials formation under conditions of higher school reform.] Engineering Journal of Don, 2013, vol. 27, no. 4, pp. 265 (in Russian).

3. Klevansky, N.N., Krasnikov, A.A. Zadacha formirovaniya kalendarnykh grafikov mul'tiproektnogo planirovaniya. [Task of generating multi-project schedule charts.] Reports of Military Sciences Academy, 2013, no. 3 (58), pp. 89–93 (in Russian).

4. Klevansky, N.N., Kravtsov, E.F. Matematicheskoe modelirovanie formirovaniya nachal'nykh mnogoperiodnykh raspisaniy. [Mathematical modeling for initial multiperiodic timetable.] Vestnik Saratov State Technical University, 2009, vol. 3, no. 1, pp. 100–106 (in Russian).

5. Klevansky, N.N., Mikhailova, M.M. Podkhody k formirovaniyu raspisaniy dlya ierarkhiy zayavok. [Approaches to request hierarchies scheduling.] Reports of Military Sciences Academy, 2012, no. 5 (54), pp. 77–82 (in Russian).

6. Klevansky, N.N., Kashin, S.S. Formirovanie raspisaniya zanyatiy universiteta s ispol'zovaniem metodov ranzhirovaniya. [Solving the university course timetabling problems by the use of ranking methods.] Vestnik Saratov State Technical University, 2010, no. 4 (49), pp. 143–150 (in Russian).

7. Baltak, S.V., Sotskov, Y.N. Postroenie raspisaniy uchebnykh zanyatiy na osnove raskraski vershin grafa. [Generating course timetabling on the basis of vertex graph coloring.] Informatics, 2006, no. 3, pp. 58–69 (in Russian).

8. Zimin, S.N. Sostavlenie uchebnogo raspisaniya, ispol'zuya teoriyu grafov. [Timetabling with the use of graph theory.] Modern High Technologies, 2007, no. 11, pp. 89–90 (in Russian).

9. Astakhova, I.F., Kurchenkova, T.V. Razrabotka informatsionnoy sistemy postroeniya raspisaniya. [Development of information system for timetabling.] Matematika. Obrazovanie. Ekologiya. Gendernye problemy: mat-ly mezhdunar. konf. [Mathematics. Education. Ecology. Gender issues: Proc. Int. Conf.] Moscow: Progress-Traditsiya, 2001, vol. 2, pp. 287–290 (in Russian).

10. Astakhova, I.F., Firas, A.M. Sostavlenie raspisaniya uchebnykh zanyatiy na osnove geneticheskogo algoritma. [Drawing up the schedule of studies on the basis of genetic algorithm.] Proceedings of Voronezh State University. Series: Systems analysis and information technologies, 2013, no. 2, pp. 93–99 (in Russian).

11. Korobkin, А.А. Ispol'zovanie agregativnogo geneticheskogo algoritma dlya sostavleniya raspisaniya. [Use of aggregate genetic algorithm for schedule drawing up.] Proceedings of Voronezh State University, 2009, vol. 5, no. 11, pp. 184– 186 (in Russian).

12. Korobkin, А.А, Astakhova, I.F. Razrabotka modeley informatsionnoy sistemy postroeniya raspisaniya. [Development of models of the timetabling information system.] Sovremennye problemy matematiki i matematicheskogo modelirovaniya: mat-ly III mezhdunar. nauch. konf. [Modern problems of mathematics and mathematical modeling: Proc. III Int. Sci. Conf.] Voronezh: Nauchnaya kniga, 2009, Part 2, pp. 156 (in Russian).

13. Nizamova, G.F. Matematicheskoe i programmnoe obespechenie sostavleniya raspisaniya uchebnykh zanyatiy na osnove agregativnykh geneticheskikh algoritmov: avtoref. dis. … kand. tekhn. nauk. [Mathematical and software support for training agenda timetabling based on the aggregative genetic algorithms: Cand.Sci. (Eng.) diss., author’s abstract.] Ufa, 2006, 17 p. (in Russian).

14. Semenyuta, I.S. Sistemnyy analiz i optimizatsiya tekhnologicheskogo protsessa avtomatizatsii sostavleniya raspisaniya zanyatiy vuza s determinirovannymi ogranicheniyami: avtoref. dis. … kand. tekhn. nauk . [System analysis and optimization of university timetabling automation process with deterministic constraints: Cand.Sci. (Eng.) diss., author’s abstract.] Krasnodar, 2011, 24 p. (in Russian).

15. Babkina, T.S. Zadacha sostavleniya raspisaniy: reshenie na osnove mnogoagentnogo podkhoda. [Scheduling problem: solution based on multi-agent approach.] Business Informatics, 2008, no. 1, pp. 23–28 (in Russian).

16. Milekhina, T.V. Povyshenie effektivnosti klasternykh sistem obrabotki informatsii pri reshenii optimizatsionnykh zadach (na primere zadachi sostavleniya raspisaniya zanyatiy): avtoref. dis. … kand. tekhn. nauk. [Improving the efficiency of clustered data processing systems for solving optimization problems (scheduling problem case): Cand.Sci. (Eng.) diss., author’s abstract.] Moscow, 2011, 23 p. (in Russian).

17. Aswad, F.-M. Modeli sostavleniya raspisaniya zanyatiy na osnove geneticheskogo algoritma na primere vuza Iraka: avtoref. dis. … kand. tekhn. nauk. [Scheduling training sessions based on genetic algorithm for Iraqi university: Cand.Sci. (Eng.) diss., author’s abstract.] Voronezh, 2013, 16 p. (in Russian).

18. Ilyinskiy, V.V. Sostavitel'raspisaniya.rf. Komp'yuternaya programma dlya sostavleniya raspisaniya zanyatiy. [Sostavitelraspisaniya.rf. A computer program for timtabling.] Available at: http://www.составительрасписания.рф (accessed: 28.01.17) (in Russian).

19. Berson, M.G. Raspisanie 98 XP-1.0.2010. Kompleks programm. Ofitsial'nyy sayt razrabotchika programmnogo obespecheniya dlya uchebnykh organizatsiy. [Schedule 98 XP-1.0.2010. Complex of programs. Official website of software developer for educational institutions] Available at: http://www.markberson.ru (accessed: 28.01.17) (in Russian).

20. Gubenko, I.O. Prilozhenie AVTORaspisanie. Laboratoriya MMIS. [AVTORaspisanie application. Laboratory of MMIS.] Available at: http://www.mmis.ru/Default.aspx?tabid=160 (accessed: 28.01.17) (in Russian).

21. Zavyalov, А.М., Novikov, A.V. Avtomatizatsiya zadachi sostavleniya uchebnogo raspisaniya. [Automation of problem of timetable making.] Sistemnyy analiz v nauke i obrazovanii, 2009, no. 1, pp. 1–20 (in Russian).

22. Ayob, M, et al. Intelligent Examination Timetabling Software. Procedia Social and Behavioral Sciences, 2011, no. 18, pp. 600–608.

23. Hosny, M., Al-Olayan, M. A Mutation-Based Genetic Algorithm for Room and Proctor Assignment in Examination Scheduling. Science and Information Conference. London, 2014, pp. 260–268.

24. AISharafat, W.-S., AISharafat, М.-S. Adaptive Steady State Genetic Algorithm for Scheduling University Exams. International Conference on Networking and Information Technology. Manila, 2010, pp. 70–74.

25. Innet, S. A Noval Approach of Genetic Algorithm for Solving Examination Timetabling Problems: a case study of Thai Universities. 13th International Symposium on Communications and Information Technologies (ISCIT). Surat Thani, 2013, pp. 233–237.

26. To, T.-V., Win, S.-S. Clustering Approach to Examination Scheduling. 3rd International Conference on Advanced Computer Theory and Engineering (ICACTE). Chengdu, 2010, vol. 5, pp. 228–230.