Abstract
In examination timetabling a given set of examinations must be assigned to as few time slots as possible so as to satisfy certain side constraints and so as to reduce penalties deriving from proximity constraints. In this paper, we present new algorithms for this problem and report the results of an extensive experimental study. All our algorithms are based on local search and are compared with other existing implementations in the literature.
Work partially supported by the Italian National Research Council (CNR).
Work partially supported by the Italian National Research Council (CNR) under contract n. 98.00770.CT26.
Work partially supported by the IST Programme of the EU under contract n. IST- 1999-14186 (ALCOM-FT), by the Italian Ministry of University and Scientific Research (Project “Algorithms for Large Data Sets: Science and Engineering”), and by the Italian National Research Council (CNR).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Burke, E., and Newall, J, “A Multi-Stage Evolutionary Algorithm for the Timetabling Problem”, IEEE Transactions on Evolutionary Computation, 3 (1) (1999) 63–74.
Burke, E., Newall, J, and Weare, R., “A Memetic Algorithm for University Exam Timetabling”, in Proc. of the 1st Int. Conf. on the Practice and Theory of Automated Timetabling, (1995) 241–250.
Corne, D., Fang, H.-L., and Mellish, C, “Solving the Modular Exam Scheduling Problem with Genetic Algorithms”, Tech. rep. 622, Department of Artificial Intelligence, University of Edinburgh, (1993).
Corne, D., Ross, P., and Fang, H.-L., “Evolutionary Timetabling: Practice Prospects and Work in Progress”, in UK Planning and Scheduling SIG Workshop, (1994).
Carter, M.W., ldA Survey of Practical Applications of Examination Timetabling Algorithms”, Operations Research, 34 (2) (1986) 193–202.
Carter, M.W., Laporte, G., and Chinnek, J.W., “A General Examination Scheduling”, Interfaces, 24 (3) (1994) 109–120.
Carter, M.W., Laporte, G., and Lee, S.Y., “Examination Timetabling: Algorithm Strategies and Applications”, Journal of the Operational Research Society, 47 (1996) 373–383.
De Werra, D., “An Introduction to Timetabling”, European Journal of Operational Research, 19 (1985) 151–162.
Di Gaspero, L., and Schaerf, A., “Tabu Search Techniques for Examination Timetabling Problems”, in Proc. of the 6th Int. Conf. on the Practice and Theory of Automated Timetabling, (2000).
Garey, M.R., and Johnson, D.S., Computers and Intractability: A Guide to the Theory of NP-completeness, W.H. Freeman & Company, San Francisco, (1979).
Johnson, D., “Timetabling University Examinations”, Journal of the Operational Research Society, 41 (1990) 39–47.
Laporte, G., and Desroches, S., “Examination Timetabling by Computer”, Computers and Operations Research, 11 (1984) 351–360.
Metha, N.K., “The Application of a Graph Colouring Method to an Examination Scheduling Problem”, Interfaces, 11 (5) (1981) 57–64.
Thompson, J.M., and Dowsland, K.A., “A Robust Simulated Annealing Based Examination Timetabling System”, Computers and Operations Research, 25 (1998) 637–648.
Schaerf, A., “A Survey of Automated Timetabling”, Artificial Intelligence Review, 13 (2) (1999) 87–127.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Caramia, M., Dell’Olmo, P., Italiano, G.F. (2001). New Algorithms for Examination Timetabling. In: Näher, S., Wagner, D. (eds) Algorithm Engineering. WAE 2000. Lecture Notes in Computer Science, vol 1982. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44691-5_20
Download citation
DOI: https://doi.org/10.1007/3-540-44691-5_20
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42512-0
Online ISBN: 978-3-540-44691-0
eBook Packages: Springer Book Archive