Solving the Teacher Assignment-Course Scheduling Problem by a Hybrid Algorithm

Authors: Aldy Gunawan, Kien Ming Ng, Kim Leng Poh

Abstract:

This paper presents a hybrid algorithm for solving a timetabling problem, which is commonly encountered in many universities. The problem combines both teacher assignment and course scheduling problems simultaneously, and is presented as a mathematical programming model. However, this problem becomes intractable and it is unlikely that a proven optimal solution can be obtained by an integer programming approach, especially for large problem instances. A hybrid algorithm that combines an integer programming approach, a greedy heuristic and a modified simulated annealing algorithm collaboratively is proposed to solve the problem. Several randomly generated data sets of sizes comparable to that of an institution in Indonesia are solved using the proposed algorithm. Computational results indicate that the algorithm can overcome difficulties of large problem sizes encountered in previous related works.

Keywords: Timetabling problem, mathematical programming model, hybrid algorithm, simulated annealing.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1076700

References:

[1] S. Even, A. Itai, and A. Shamir, "On the complexity of timetable and multicommodity flow problems," SIAM Journal of Computing, vol.5, pp. 691-703, 1976.
[2] M.W. Carter, and G. Laporte, "Recent developments in practical course timetabling," (1998), in Practice and Theory of Automated Timetabling II, Lecture Notes in Computer Science, vol.1408, ed by E. Burke, and M. Carter, New York: Springer-Verlag, pp. 3-19, 1998.
[3] R.A. Valdes, E. Crespo, and J.M. Tamarit, "Design and implementation of a course scheduling system using Tabu Search," European Journal of Operational Research, vol.137, pp. 512-523, 2002.
[4] S. Daskalaki, T. Birbas, and E. Housos, "An integer programming formulation for a case study in university timetabling," European Journal of Operational Research, vol.153, pp. 117-135, 2004.
[5] D. Abramson, M. Krishnamoorthy, and H. Dang, "Simulated annealing cooling schedules for the school timetabling problem," Asia-Pacific Journal of Operational Research, vol.16, pp. 1-22, 1999.
[6] J. Puchinger, and G.R. Raidl, "Combining metaheuristics and exact algorithms in combinatorial optimization: a survey and classification," in IWINAC 2005, Lecture Notes in Computer Science, vol.3562, ed by J. Mira and J.R. Alvarez, New York: Springer-Verlag, pp. 41-53, 2005.
[7] R. Weare, E. Burke, and D. Elliman, "A hybrid genetic algorithm for highly constrained timetabling problems," University of Notthingham, Computer Science Technical Report No. NOTTCS-TR-1995-8, 1995.
[8] S. Petrovic, and Y. Yang, "Case-based initialisation of metaheuristics for examination timetabling," in Multidisciplinary Scheduling, Theory and Applications, ed by G. Kendall, E. Burke, S. Petrovic, and M. Gendreau, New York: Springer-Verlag, pp. 289-308, 2005.
[9] M. Chiarandini, and T. St├╝tzle, "A landscape analysis for a hybrid approximate algorithm on a timetabling problem," TU Darmstadt, Technical Report AIDA-03-05, 2003.
[10] T.A. Duong, and K.H. Lam, "Combining constraint programming and simulated annealing on university exam timetabling," in Proceedings of International Conference RIVF-04, Hanoi, February 2004, pp. 205-210.
[11] L.T.G Merlot, N. Boland, B.D. Hughes, and P.J. Stuckey, "A hybrid algorithm for the examination timetabling problem," in Practice and Theory of Automated Timetabling IV, Lecture Notes in Computer Science, vol.2740, ed by E. Burke, and M. Carter, New York: Springer- Verlag pp. 207-231, 2002.
[12] M. Chiarandini, M. Birattari, K. Socha, and O. Rossi-Doria, "An effective hybrid algorithm for university course timetabling," Journal of Scheduling, vol.9, no.5,pp. 403-432, 2006.
[13] A. Gunawan, K.M. Ng, and K.L. Poh, "A mathematical programming model for a timetabling problem," in Proceedings of the International Conference on Scientific Computing, Nevada, 2006.
[14] A. Gunawan, K.M. Ng, and K.L. Poh, "An improvement heuristic for the timetabling problem (Accepted for publication)," International Journal of Computational Science, vol 1,no 2, pp. 162-178, 2007.
[15] S. Kirkpatrick, C.D. Gellatt, and M.P. Vecchi, "Optimization by simulated annealing," Science, vol 220, pp. 671-680, 1983.