Solving the Teacher Assignment-Course Scheduling Problem by a Hybrid Algorithm
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.
[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.
[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.
@article{"International Journal of Mechanical, Industrial and Aerospace Sciences:60167", author = "Aldy Gunawan and Kien Ming Ng and Kim Leng Poh", title = "Solving the Teacher Assignment-Course Scheduling Problem by a Hybrid Algorithm", 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.", volume = "1", number = "9", pages = "516-6", }
