Abstract
University examination timetabling is a challenging set partitioning problem that comes in many variations, and real world applications usually carry multiple constraints and require the simultaneous optimization of several (often conflicting) objectives. This paper presents a multiobjective framework capable of solving heavily constrained timetabling problems. In this prototype study, we focus on the two objectives: minimizing timetable length while simultaneously optimizing the spread of examinations for individual students. Candidate solutions are presented to a multiobjective memetic algorithm as orderings of examinations, and a greedy algorithm is used to construct violation free timetables from permutation sequences of exams. The role of the multiobjective algorithm is to iteratively improve a population of orderings, with respect to the given objectives, using various mutation and reordering heuristics.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Abdullah, S., Ahmadi, S., Burke, E., & Dror, M. (2007). Investigating Ahuja-Orlin’s large neighbourhood search approach for examination timetabling. OR Spectrum, 29(2), 351–372.
Apt, K. (2003). Principles of constraint programming. New York: Cambridge University Press.
Asmuni, H., Burke, E. K., & Garibaldi, J. M. (2005). Fuzzy multiple ordering criteria for examination timetabling. In E. Burke (Ed.), LNCS: Vol. 3616. PATAT 2004 (pp. 334–354). Berlin: Springer.
Brélaz, D. (1979). New methods to color the vertices of graphs. Communications of the ACM, 24(4), 251–256.
Burke, E., & Newall, J. (1996). A memetic algorithm for university exam timetabling. In LNCS: Vol. 1153. Practice and theory of automated timetabling: first international conference, PATAT 1996 (pp. 241–250). Berlin: Springer.
Burke, E., & Newall, J. (1999). A multi-stage evolutionary algorithm for the timetabling problem. IEEE Transactions on Evolutionary Computation, 3(1), 63–74.
Burke, E. K., & Newall, J. P. (2004). Solving examination timetabling problems through adaption of heuristic orderings. Annals of Operations Research, 129, 107–134.
Burke, E. K., & Petrovic, S. (2002). Recent research directions in automated timetabling. European Journal of Operational Research, 140(2), 266–280.
Burke, E. K., Elliman, D., Ford, P. H., & Weare, R. F. (1996). Examination timetabling in British universities: A survey. In Selected papers from the first international conference on practice and theory of automated timetabling (pp. 76–90). London: Springer.
Burke, E., Bykov, Y., & Petrovic, S. (2001). A multicriteria approach to examination timetabling. In LNCS: Vol. 2079. Practice and theory of automated timetabling III: third international conference, PATAT 2000 (pp. 118–131). Berlin: Springer.
Burke, E. K., Eckersley, A. J., McCollum, B., Petrovic, S., & Qu, R. (2006). Hybrid variable neighbourhood approaches to university exam timetabling (Computer Science Technical Report No. NOTTCS-TR-2006-2). University of Nottingham.
Burke, E. K., Mccollum, B., Meisels, A., Petrovic, S., & Qu, R. (2007). A graph-based hyper-heuristic for educational timetabling problems. European Journal of Operational Research, 176(1), 177–192.
Caramia, M., Dell’Olmo, P., & Italiano, G. F. (2001). New algorithms for examination timetabling. In LNCS: Vol. 1982. WAE’00: Proceedings of the 4th international workshop on algorithm engineering, September 5–8, 2000 (pp. 230–242). London: Springer.
Carter, M. W. (1986). A survey of practical applications of examination timetabling algorithms. Operations Research, 34, 193–202.
Carter, M. W., & Laporte, G. (1996). Recent developments in practical examination timetabling. In E. K. Burke (Ed.), LNCS: Vol. 1152. Practice and theory of automated timetabling: selected papers from the 1st international conference (pp. 3–21). Berlin: Springer.
Carter, M. W., Laporte, G., & Lee, S. Y. (1996). Examination timetabling: algorithms, strategies and applications. European Journal of Operational Research, 47, 373–383.
Casey, S., & Thompson, J. (2003). Grasping the examination scheduling problem. In E. K. Burke (Ed.), LNCS: Vol. 2740. Practice and theory of automated timetabling IV (pp. 232–244). Berlin: Springer.
Cheong, C. Y., Tan, K. C., & Veeravalli, B. (2007). Solving the exam timetabling problem via a multi-objective evolutionary algorithm—a more general approach. In Proceedings of the 2007 IEEE symposium on computational intelligence in scheduling (CI-Sched 2007) (pp. 165–172).
Côté, P., Wong, A., & Sabourin, R. (2005). A hybrid multi-objective evolutionary algorithm for the uncapacitated exam proximity problem. In E. Burke & M. Trick (Eds.), LNCS : Vol. 3616. PATAT 2004 (pp. 294–312). Berlin: Springer.
Culberson, J., & Luo, F. (1996). Exploring the k-colorable landscape with iterated greedy. In D. S. Johnson & M. Trick (Eds.), DIMACS series in discrete mathematics and theoretical computer science: Vol. 26. Cliques, coloring and satisfiability: second DIMACS implementation challenge (pp. 499–520). Providence: Am. Math. Soc.
Davis, L. (1991). Order-based genetic algorithms and the graph coloring problem. In Handbook of genetic algorithms (pp. 72–90). New York: Reinhold. Chap. 6.
Deb, K. (2001). Multi-objective optimization using evolutionary algorithms. Chichester: Wiley.
Laporte, G., & Desroches, S. (1984). Examination timetabling by computer. Computers & Operations Research, 11(4), 351–360.
Matula, D. W., Marble, G., & Isaacson, J. D. (1972). Graph coloring algorithms. In R. C. Read (Ed.), Graph theory and computing (pp. 104–122). New York: Academic Press.
Merlot, L. T. G., Borland, N., Hughs, B. D., & Stuckey, P. J. (2003). A hybrid algorithm for the examination timetabling problem. In E. K. Burke & P. De Causmaecker (Eds.), LNCS: Vol. 2740. Practice and theory of automated timetabling IV (pp. 207–231). Berlin: Springer.
Mumford, C. L. (2004). Simple population replacement strategies for a steady-state multi-objective evolutionary algorithm. In Proceedings of the 2004 genetic an evolutionary computation conference (GECCO) (pp. 1389–1400). Seattle, Washington, USA.
Mumford, C. L. (2006). New order-based crossovers for the graph coloring problem. In T. P. Runarsson, H.-G. Beyer, E. K. Burke, J. J. Merelo Guervós, L. D. Whitley, & X. Jao (Eds.), LNCS: Vol. 4193. Parallel problem solving from nature—PPSN IX, Proceedings of 9th international conference, Reykjavik, Iceland, September 9–13, 2006, (pp. 880–889). Berlin: Springer.
Mumford, C. L. (2007). An order based evolutionary approach to dual objective examination timetabling. In Proceedings of the 2007 IEEE symposium on computational intelligence in scheduling (CI-Sched 2007) (pp. 179–186).
Qu, R., Burke, E.K., McCollum, B., Merlot, L. T. G., & Lee, S. Y. (2008). A survey of search methodologies and automated system development for examination timetabling. Journal of Scheduling. doi:10.1007/s10951-008-0077-5.
Schaerf, A. (1999). A survey of automated timetabling. Artificial Intelligence Review, 13, 87–127.
Thompson, J. M., & Dowsland, K. A. (1998). A robust simulated annealing based examination timetabling system. Computers & Operations Research, 25(7–8), 637–648.
Tsang, E. (1993). Foundations of constraint satisfaction. San Diego: Academic Press.
Valenzuela, C. L. (2002). A simple evolutionary algorithm for multi-objective optimization (SEAMO). In Proceedings of the 2002 IEEE congress on evolutionary computation (CEC2002), Honolulu, Hawaii, 2002 (pp. 717–722). (C. L. Valenzuela is now known as C. L. Mumford).
Welsh, D. J. A., & Powell, M. B. (1967). An upper bound for the chromatic number of a graph and its application to timetabling problems. The Computer Journal, 10, 85–86.
Wong, A., Côté, P. & Sabourin, R., (2004). A hybrid MOEA for the capacitated exam proximity problem. In Proceedings of the 2004 IEEE congress on evolutionary computation, Portland, Oregon, 20–23 June 2004 (pp. 1495–1501). New York: IEEE Press.
Yang, Y., & Petrovic, S. (2005). A novel similarity measure for heuristic selection in examination timetabling. In E. Burke & M. Trick (Eds.), LNCS: Vol. 3616. PATAT 2004 (pp. 377–396). Berlin: Springer.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Mumford, C.L. A multiobjective framework for heavily constrained examination timetabling problems. Ann Oper Res 180, 3–31 (2010). https://doi.org/10.1007/s10479-008-0490-3
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-008-0490-3