Abstract
The exam timetabling problem faces the problem of scheduling exams within a limited number of available periods. The main objective is to balance out student’s workload by distributing the exams evenly within the planning horizon. Ant colony approaches have been proven to be a powerful solution approach for various combinatorial optimization problems. In this paper a Max-Min and a ANTCOL approach will be presented. Its performance is compared with other approaches presented in the literature and with modified graph coloring algorithms.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Carter, M., Laporte, G., Lee, S.: Examination timetabling algorithmic strategies and applications. Journal of the Operational Research Society 47, 373–383 (1996)
Garey, M., Johnson, D.: Computers and intractability: a guide to the theory of NP-completness. W. H. Freeman and Company, New York (1979)
Carter, M., Laporte, G.: Recent developments in practical examination timetabling. In: Burke, E.K., Ross, P. (eds.) PATAT 1995. LNCS, vol. 1153, pp. 3–21. Springer, Heidelberg (1996)
Colorni, A., Dorigo, M., Maniezzo, V.: Distributed optimization by ant colonies. In: Proceedings of the first european conference on artificial life, pp. 134–142. Elsevier Science Publishers, Amsterdam (1992)
Dorigo, M., Di Caro, G., Gambarella, L.: Ant algorithms for discrete optimization. Artificial Life 5, 137–172 (1999)
Stützle, T., Hoos, H.: \(\mathcal{MAX-MIN}\) Ant Systems. Future Generation Computer System 16, 889–914 (2000)
Socha, K., Sampels, M., Manfrin, M.: Ant algorithms for the university course timetabling problem with regard to the state-of-the-art. In: Raidl, G.R., Cagnoni, S., Cardalda, J.J.R., Corne, D.W., Gottlieb, J., Guillot, A., Hart, E., Johnson, C.G., Marchiori, E., Meyer, J.-A., Middendorf, M. (eds.) EvoIASP 2003, EvoWorkshops 2003, EvoSTIM 2003, EvoROB/EvoRobot 2003, EvoCOP 2003, EvoBIO 2003, and EvoMUSART 2003. LNCS, vol. 2611, pp. 334–345. Springer, Heidelberg (2003)
Costa, D., Hertz, A.: Ants can color graphs. Journal of the Operational Research Society 48, 295–305 (1997)
Dowsland, K., Thompson, J.: Ant colony optimisation for the examination scheduling problem. Journal of the Operational Research Society 56, 426–439 (2005)
White, G., Xie, B., Zonjic, S.: Using tabu search with long-term memeory and relaxation to create examination timetables. European Journal of Operational Research 153, 80–91 (2004)
Di Gaspero, L., Schaerf, A.: Tabu search techniques for examination timetabling. In: Burke, E., Erben, W. (eds.) PATAT 2000. LNCS, vol. 2079, pp. 104–117. Springer, Heidelberg (2001)
Caramia, M., Dell’Olmo, P., Italiano, G.: New algorithms for examination timetabling. LNCS, vol. 982, pp. 230–241 (2001)
Burke, E., Newall, J.: Enhancing timetable solutions with local search methods. In: Burke, E.K., De Causmaecker, P. (eds.) PATAT 2002. LNCS, vol. 2740, pp. 195–206. Springer, Heidelberg (2003)
Merlot, L., Boland, N., Hughes, B., Stuckey, P.: New benchmarks for examination timetabling. Test problem database, http://www.or.ms.unimelb.edu.au/timetabling.html
Di Gaspero, L.: Recolour, shake and kick: A recipe for the examination timetabling problem. In: Proceedings of the fourth international conference on the practice and theory of automated timetabling, Gent, Belgium, pp. 404–407 (2002)
Paquete, L., Stützle, T.: Empirical analysis of tabu search for the lexicographic optimization of the examination timetabling problem. In: Proceedings of the fourth international conference on the practice and theory of automated timetabling, Gent, Belgium, pp. 413–420 (2002)
Casey, S., Thompson, J.: GRASPing the examination scheduling problem. In: Burke, E.K., De Causmaecker, P. (eds.) PATAT 2002. LNCS, vol. 2740, pp. 232–244. Springer, Heidelberg (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Eley, M. (2006). Some Experiments with Ant Colony Algorithms for the Exam Timetabling Problem. In: Dorigo, M., Gambardella, L.M., Birattari, M., Martinoli, A., Poli, R., Stützle, T. (eds) Ant Colony Optimization and Swarm Intelligence. ANTS 2006. Lecture Notes in Computer Science, vol 4150. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11839088_50
Download citation
DOI: https://doi.org/10.1007/11839088_50
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-38482-3
Online ISBN: 978-3-540-38483-0
eBook Packages: Computer ScienceComputer Science (R0)