A time-predefined approach to course timetabling
DOI:
https://doi.org/10.2298/YJOR0302139BKeywords:
combinatorial optimisation, metaheuristic, local search, timetablingAbstract
A common weakness of local search metaheuristics, such as Simulated Annealing, in solving combinatorial optimization problems, is the necessity of setting a certain number of parameters. This tends to generate a significant increase in the total amount of time required to solve the problem and often requires a high level of experience from the user. This paper is motivated by the goal of overcoming this drawback by employing "parameter-free" techniques in the context of automatically solving course timetabling problems. We employ local search techniques with "straightforward" parameters, i.e. ones that an inexperienced user can easily understand. In particular, we present an extended variant of the "Great Deluge" algorithm, which requires only two parameters (which can be interpreted as search time and an estimation of the required level of solution quality). These parameters affect the performance of the algorithm so that a longer search provides a better result - as long as we can intelligently stop the approach from converging too early. Hence, a user can choose a balance between processing time and the quality of the solution. The proposed method has been tested on a range of university course timetabling problems and the results were evaluated within an International Timetabling Competition. The effectiveness of the proposed technique has been confirmed by a high level of quality of results. These results represented the third overall average rating among 21 participants and the best solutions on 8 of the 23 test problems. .References
Aarts, E., and Lenstra, J.K., Local Search in Combinatorial Optimization, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Chichester, 1997.
Abramson, D., "Constructing school timetables using simulated annealing: Sequential and parallel algorithms", Management Science, 37(1) (1991) 98-113.
Abramson, D., Krishnamoorthy, M., and Dang, H., "Simulated annealing cooling schedules for the school timetabling problem", Asia-Pacific J. of Operational Research, 16 (1999) 1-22.
Appleby, J.S., Blake, D.V., and Newman, E.A., "Techniques for producing school timetables on a computer and their application to other scheduling problems", The Computer Journal, 3 (1960) 237-245.
Burke, E.K., and Petrovic, S., "Recent research directions in automated timetabling", European Journal of Operational Research, 140 (2) (2002) 266-280.
Burke, E.K., Bykov, Y., Newall, J., and Petrovic, S., "A time pre-defined local search approach to exam timetabling problems", accepted for publication in IIE Transaction on Operations Engineering (2004).
Carter, M.W., and Laporte, G., "Recent developments in practical examination timetabling", in: E. Burke, M. Carter (eds.), The Practice and Theory of Automated Timetabling II: Selected Papers (PATAT'97). Lecture Notes in Computer Science, Vol. 1408, Springer-Verlag, Berlin, Heidelberg, New York, 1998, 3-19.
Cheng, C., Kang, L., Leung, N., and White G.M., "Investigations of a constraint logic programming approach to university tametabling", in: E. Burke, P. Ross (eds.), The Practice and Theory of Automated Timetabling: Selected Papers (ICPTAT'95). Lecture Notes in Computer Science, Vol. 1153, Springer-Verlag, Berlin, Heidelberg, New York, 1996, 112-129.
Colorni, A., Dorgio, M., and Maniezzo, V., "Genetic algorithms and highly constrained problems: The time-table case", in: G. Goos, J. Hartmanis (eds.), Parallel Problem Solving from Nature, Springer-Verlag, 1990, 55-59.
Cooper, T.B., and Kingston, J.H., "The solution of real instances of the timetabling problem", The Computer Journal, 36 (7) (1993) 645-653.
Davis, L., and Rutter, L., "Schedule optimization with probabilistic search", Proceedings of the 3rd IEEE Conference on Artificial Intelligence Applications (Orlando, Florida, USA, Feb. 1987), IEEE1987, 1987, 231-236.
Dowsland, K., "Simulated Annealing", in: C.R. Reeves (ed.), Modern Heuristic Techniques for Combinatorial Problems, Blackwell, 1993, 20-69.
Dueck, G., and Scheuer, T., "Threshold accepting: A general purpose optimization algorithm appearing superior to Simulated Annealing", Journal of Computational Physics, 90 (1990) 161-175.
Dueck, G., "New optimization heuristics. The Great Deluge algorithm and the record-to-record travel", Journal of Computational Physics, 104 (1993) 86-92.
Elmohamed, M.A.S., Coddington, P., and Fox, G., "A Comparison of annealing techniques for academic course scheduling", in: E. Burke, M. Carter (eds.), The Practice and Theory of Automated Timetabling: Selected Papers (PATAT '97). Lecture Notes in Computer Science, Vol. 1408, Springer-Verlag, Berlin Heidelberg, New York, 1998, 92-112.
Gueret, G., Jussien, N., Boizumault, P., and Prins, C., "Building university timetables using constraint logic programming", in: E. Burke, P. Ross (eds.): The Practice and Theory of Automated Timetabling: Selected Papers (ICPTAT '95). Lecture Notes in Computer Science, Vol. 1153. Springer-Verlag, Berlin Heidelberg, New York, 1996, 130-145.
Hertz, A., "Tabu search for large scale timetabling problems", European Journal of Operational Research, 54 (1991) 39-47.
Hu, T.C., Kahng, A.B., and Tsao, C.W., "Old bachelor acceptance: A new class of nonmonotone threshold accepting methods", ORSA Journal on Computing, 7(4) (1995) 417-425.
Kirkpatrick, S., Gellat, J.C.D., and Vecci, M.P., "Optimization by simulated annealing", Science, 220 (1983) 671-680.
Koulmas, C., Antony, S.R., and Jaen, R., "A survey of simulated annealing applications to operations research problems", Omega International Journal of Management Science, 22 (1994) 41-56.
Laporte, G., and Desroches, S., "The problem of assigning students to course sections in a large engineering school", Computers and Operations Research, 13 (4) (1986) 387-394.
Melicio, F., Caldeira, P., and Rosa, A., "Solving the timetabling problem with simulated annealing", Proceedings of the First International Conference on Enterprise Information Systems (ICEIS'99), 1999, 272-279.
Paechter, B., Cumming, A., Norman, M.G., and Lucian, H., "Extensions to a memetic timetabling system", in: E. Burke, P. Ross (eds.), The Practice and Theory of Automated Timetabling: Selected Papers (ICPTAT '95). Lecture Notes in Computer Science, Vol. 1153, Springer-Verlag, Berlin Heidelberg, New York, 1996, 251-265.
Schaerf, A., "Tabu search techniques for large high-school timetabling problems", Proceedings of the 13th American Conference on Artificial Intelligence (AAAI-96), Portland, Oregon, USA August 1996, 363-368.
Schaerf A., "A survey of automated timetabling", Artificial Intelligent Review, 13 (1999) 87-127.
Ueda, H., Ouchi, D., Takahashi, K., and Miyahara, T., "A co-evolving timeslot/room assignment genetic algorithm technique for university timetabling", in: E. Burke, W. Erben (eds.), The Practice and Theory of Automated Timetabling III: Selected Papers (PATAT 2000). Lecture Notes in Computer Science, Vol. 2079, Springer-Verlag, Berlin, Heidelberg, New York, 2001, 48-63.
International Timetabling Competition home page: http://www.idsia.ch/Files/ttcomp2002/
Downloads
Published
Issue
Section
License
Copyright (c) 2003 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
