A Modified Event Grouping Based Algorithm for The University Course Timetabling Problem

Velin Spasov Kralev, Radoslava Stankova Kraleva, Sachin Kumar

Abstract


This paper presents a study of a modified event grouping based algorithm (MEGB) for university course timetabling problem (UCTP). Multiple models to describe the problem and multiple approaches to solving it are pointed out. The main idea of the modification is that through reduction on the generated solutions the execution time of the standard event grouping based algorithm (EGB) will be reduced, too. Also, an implementation of the modified algorithm based on the described approach is presented. The methodology, conditions and the aims of the experiment are described. The experimental results are analyzed and conclusions are made. When increasing the number of the groups, the execution time of the MEGB algorithm increases and equates with the execution time of the EGB algorithm. The best results are obtained with the first 30% of the groups formed. In these groupings, the execution time of the MEGB algorithm is much less than the execution time of the EGB algorithm. This is because, in the EGB algorithm, every change in the event ordinance creates a new timetable, and all events are repositioned on it. This process is optimized by creating a partial timetable, whereby the ordinance of events in groups before the current does not change. In addition, a comparative analysis between the MEGB algorithm and two other algorithms for UCTP, respectively a genetic algorithm with the local search method (GALS) and a local search algorithm based on chromatic classes (CCLS) is made as well. The obtained results show that the MEGB algorithm and the CCLS algorithm generate better solutions for smaller input data sets, while the GALS algorithm generates better solutions for larger input data sets. However, in terms of the execution time, it was ascertained that the GALS algorithm runs slowest among the others.

Keywords


university course timetabling problem; local search; genetic algorithm; modified event grouping based algorithm.

Full Text:

PDF

References


H. Babaei, J. Karimpour, and A. Hadidi, "A survey of approaches for university course timetabling problem," Computers and Industrial Engineering, vol. 86, pp. 43-59, 2015.

S. Even, A. Itai, and A. Shamir, "On the complexity of timetable and multi-commodity flow problems," SLAM Journal of computing, vol. 5(4), pp. 691-703, 1976.

K. Y. Junn, J. H. Obit, and R. Alfred, "The Study of Genetic Algorithm Approach to Solving University Course Timetabling Problem," Lecture Notes in Electrical Engineering, vol. 488, pp. 454-463, 2018.

A. R. Komijan, and M. N. Koupaei, "A mathematical model for university course scheduling: a case study," International Journal of Technical Research and Applications, vol. 19, pp. 20-25, 2015.

R. Chen, and H. Shih, "Solving university course timetabling problems using constriction particle swarm optimization with local search," Algorithms, vol. 6, pp. 227-244, 2013.

M. S. Kohshori, and M. S. Abadeh, "Hybrid genetic algorithms for university course timetabling," International Journal of Computer Science Issues, vol. 9(2), pp. 446-455, 2012.

V. Kralev, "A model for the university course timetabling problem," International journal "Information technologies & knowledge", vol. 3(3), pp. 276-289, 2009.

M. Traykov, S. Angelov, and N. Yanev, "A New Heuristic Algorithm for Protein Folding in the HP Model," Journal of Computational Biology, vol. 23(8), pp. 662-668, Aug. 2016.

F. I. Sapundzhi and M. S. Popstoilov, "Optimization algorithms for finding the shortest paths," Bulgarian Chemical Communications, vol. 50, special issue B, pp. 115-120, 2018.

K. Y. Junn, J. H. Obit, and R. Alfred, "A constraint programming approach to solving university course timetabling problem (UCTP)," Advanced Science Letters, vol. 23(11), pp. 11023-11026, 2017.

H. S. Theng, A. B. Bin Md Sultan, and N. Mohd Ali, "Multiple-hybrid case-based reasoning approach for university course timetabling problem," Journal of Theoretical and Applied Information Technology, vol. 72(2), pp. 164-178, 2015.

T. Song, S. Liu, X. Tang, X. Peng, and M. Chen, "An iterated local search algorithm for the University Course Timetabling Problem," Applied Soft Computing Journal, vol. 68, pp. 597-608, 2018.

J. A. Soria-Alcaraz, E. Özcan, J. Swan, G. Kendall, and M. Carpio, "Iterated local search using an add and delete hyper-heuristic for university course timetabling," Applied Soft Computing Journal, vol. 40, pp. 581-593, 2016.

J. H. Obit, K. Y. Junn, and R. Alfred, "Performance comparison of linear and non-linear great deluge algorithms in solving university course timetabling problems," Advanced Science Letters, vol. 23(11), pp. 11027-11030, 2017.

V. Kralev, and R. Kraleva, "Variable neighborhood search based algorithm for university course timetabling problem," proceedings of the Fifth international scientific conference, FMNS-2013, pp. 202-214, 2013.

K. Patrick, and Z. Godswill, "Greedy ants colony optimization strategy for solving the curriculum based university course timetabling problem," British Journal of Mathematics & Computer Science, vol. 14(2), pp. 1-10, 2016.

M. Mazlan, M. Makhtar, A. F. K. A. Khairi, M. A. Mohamed, and M. N. A. Rahman, "Ant colony optimisation for solving university course timetabling problems," International Journal of Engineering and Technology (UAE), vol. 7(2), pp. 139-141, 2018.

K. Y. Junn, J. H. Obit, and R. Alfred, "Comparison of simulated annealing and great deluge algorithms for university course timetabling problems (UCTP)," Advanced Science Letters, vol. 23(11), pp. 11413-11417, 2017.

S. Zheng, L. Wang, Y. Liu, and R. Zhang, "A simulated annealing algorithm for university course timetabling considering travelling distances," International Journal of Computing Science and Mathematics, vol. 6(2), pp. 139-151, 2015.

M. X. Zhang, B. Zhang, and N. Qian, "University course timetabling using a new ecogeography-based optimization algorithm," Natural Computing, vol. 16(1), pp. 61-74, 2017.

S. E. Soliman and A. E. Keshk, "Memetic algorithm for solving university course timetabling problem," International Journal of Mechanical Engineering and Information Technology, vol. 3(8), pp. 1476-86, 2015.

V. Kralev, "A genetic and memetic algorithm for solving the university course timetabling problem," International journal "Information theories & applications", vol. 16(3), pp. 291-299, 2009.

V. Kralev, and R. Kraleva, "A local search algorithm based on chromatic classes for university course timetabling problem," International Journal of Advanced Computer Research, vol. 7(28), pp. 1-7, 2017.

V. Kralev, R. Kraleva, and B. Yurukov, "An event grouping based algorithm for university course timetabling problem," International Journal of Computer Science and Information Security, vol. 14(6), pp. 222-229, 2016.

R. P. Badoni, D. K. Gupta, and P. Mishra, "A new hybrid algorithm for university course timetabling problem using events based on groupings of students," Computers & industrial engineering, vol.78, pp. 12–25, 2014.

V. Kralev, R. Kraleva, and N. Siniagina, "An integrated system for university course timetabling," Proceedings of the third international scientific conference – FMNS2009, vol. 1, pp. 99-105, 2009.




DOI: http://dx.doi.org/10.18517/ijaseit.9.1.6488

Refbacks

  • There are currently no refbacks.


Published by INSIGHT - Indonesian Society for Knowledge and Human Development