TABU SEARCH WITH EXPLICIT ADAPTIVE GUIDING HEURISTIC FOR THE EXAMINATION TIMETABLING PROBLEM

Ezike J.O.J

Abstract

Tabu Search algorithm (TS) is one of the leading methods for solving the Examination Timetabling Problem (ETP). The challenge with TS which uses only one solution in searching is that it can easily miss some areas of the search space and chose the best solution based on the current search step and position without taking the future steps into consideration. To address these problems, an explicit and adaptive guiding heuristic was proposed for the standard TS algorithm with the goal of enhancing its performance. The standard TS and the TS with the explicit adaptive guiding mechanism, the TS_G algorithm were implement using the Java programing language (version 8.92) with the MySQL database and experimented with data from Bells University of Technology, Ota. Performance of the two algorithms were evaluated using first Order Conflict Counts (OCC), Second OCC and third OCC for students and invigilators respectively, in addition to memory consumption. The TS and TS_G yielded an average first OCC 0.0 and 0.0 students and 0.0 and 0.0 for invigilators. Similarly, TS and TS_G yielded average second OCC of 18.8 and 10.5 for students and, 0.0 and 0.0 for invigilators respectively. Furthermore, TS and TS_G yielded average third OCC of 33375.0 and 9922.1 for students and 0.0 and 0.0 for invigilators, respectively. The TS_G algorithm outperformed the standard TS algorithm with lower conflicts violations.. Read full PDF

Keywords: Tabu Search, Examination, Timetabling, Adaptive Guiding, Heuristics

References

[1] Burke, E.K., et al., Examination timetabling in British universities: A survey., in Practice and Theory of Automated Timetabling: Selected Papers from the 1st International Conference. LNCS 1153. , B. E.K. and R. P., Editors. 1996, Springer-Verlag: Berlin, Heidelberg. p. 76-90.
[2] Gendreau, M. and J. Potvin, Tabu Search, in Handbook of Metaheuristics., M. Gendreau and J. Potvin, Editors. 2010, Springer Science+Business Media, LLC 2010: International Series in Operations Research and Management Sciences 146, New York Dordrecht Heidelberg London.
[3] Zdansky, M. and J. Pozivil. Combination Genetic/Tabu Search Algorithm for Hybrid Flow Shops Optimization. in ALGORITMY 2002 Conference on Scientic Computing. 2002.
[4] Nayak, S.K., S.K. Padhy, and P. S.P., A novel algorithm for dynamic task scheduling. . Future Generation Computer Systems., 2012. 28(5): p. 709-717.
[5] Boizumault, P., Y. Delon, and L. Peridy, Constraint logic programming for examination timetabling. The Journal Of Logic Programming, 1996.
[6] Carter, M.W., G. Laporte, and J.W. Chinneck, A general examination scheduling system. Interfaces, 1994. 24: p. 109-120.
[7] Glover, F., Tabu Search: A Tutorial. Interfaces, 1990. 20: p. 74-94.
[8] Burke, E.K., G. Kendall, and E. Soubeiga, A Tabu-Search Hyperheuristics for Timetabling and Rostering. Journal of Heuristics, 2003. 9: p. 451-470.
[9] Kendall, G. and N.M. Hussin, Tabu Search Hyper-heuristic Approach to the Examination Timetabling Problem at University of Technology MARA], in PATAT 2004, Selected Papers from the 5th International Conference. Lecture Notes in Computer (LNCS) 3616, , E.K. Burke and M. Trick, Editors. 2005, SpringerVerlag Berlin Heidelberg (2005). p. 199-218.
[10]Glover, F., Tabu Search – Part I. ORSA Journal on Computing 1989. 1(3).
[11]Khader, A.T. and A.S. See, Improving Exam Timetabling Solution Using Tabu Search. Journal of Digital Information Management (JDIM), 2005. 3(4): p. 250-253 . .
[12]Abdul Rahman, S., Search methodologies for examination timetabling, 2012, University of Nottingham.
[13]Gendreau, M. An Introduction to Tabu Search. 2002.
[14]White, G.M. and B.S. Xie, Examination Timetables and Tabu Search with Longer-Term Memory, in PATAT
2000, Lecture Notes in Computer Sciences (LNCS) 2079, E. Burke and W. Erben, Editors. 2001 SpringerVerlag Berlin Heidelberg. p. 85-103.
[15]White, G.M., B.S. Xie, and S. Zonjic, Using tabu search with longer-term memory and relaxation to create examination timetables. European Journal of Operational Research, 2004. 153(1): p. 80-91.
[16]Pais, T.C. and P. Amaral, Managing the tabu list length using a fuzzy inference system: an application to exams
timetabling. Annals of Operations Research 2012. 194(1): p. 341-363.
[17]McCollum, B. University Timetabling: Bridging the Gap between Research and Practice. in The Proceedings of the 6 th International Conference on the Practice and Theory of Automated Timetabling (PATAT). 2006.
[18]Qu, R., et al., A Survey of Search Methodologies and Automated System Development for Examination Timetabling. Journal of Scheduling, 2009. 12(1): p. 55 – 89.
[19]Ezike, J.O.J., et al., Generating Feasible and Optimized Timetables using Tabu Search: The Case of Bells University of Technology, Ota. Computing, Information Systems & Development Informatics Journal. , 2018. Vol 9,(1 ): p. 84-104.
[20] Dall’igna Junior, A., et al. Performance and parameterization of the algorithm Simplified Generalized
Simulated Annealing. Genetc and Molecular Biology [online], 2004. 27, 616-622 DOI: https://doi.org/10.1590/S1415-47572004000400024.