Skip to main content
SpringerLink
Log in

Memetic techniques for examination timetabling

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

In this paper, we investigate the effectiveness of combining the main components of the memetic algorithms (MAs) on the quality of solutions produced for Uncapacitated Examination Timetabling Problem (UETP). These components are recombination, randomness, and neighbourhood structures. The Harmony Search Algorithm (HSA), which is a variation of MA, is used to perform different combinations of these components. It has three main components: Memory Consideration using the recombination, Random Consideration using the randomness and Pitch Adjustment using the neighbourhood structures (or local search). The combinations among MA components are evaluated using 17 different scenarios each of which reflects a combination of one, two or three components. The results show that the system that combines the three components (recombination, randomness, and neighbourhood structures) provides the best results. Furthermore, the best results obtained from the convergence scenarios were compared with 22 other methods that used a de facto dataset defined by Carter et al. (in Journal of the Operational Research Society 74:373–383, 1996) for UETP. The results exceed those produced by the previous methods in 2 out of 12 datasets.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Algorithm 1
Algorithm 2
Algorithm 3

Similar content being viewed by others

Notes

  1. Second International Timetabling Competition (http://www.cs.qub.ac.uk/itc2007/).

  2. http://www.asap.cs.nott.ac.uk/resources/data.shtml.

References

  • Abdullah, S., Ahmadi, S., Burke, E. K., & Dror, M. (2007). Investigating Ahuja-Orlin’s large neighbourhood search approach for examination timetabling. OR Spektrum, 29(2), 351–372.

    Article  Google Scholar 

  • Al-Betar, M. A., & Khader, A. T. (2009). A hybrid Harmony Search for university course timetabling. In J. Blazewicz, M. Drozdowski, G. Kendall, & B. McCollum (Eds.), Proceedings of the 4nd multidisciplinary conference on scheduling: theory and applications (MISTA 2009), Dublin, Ireland (pp. 157–179).

    Google Scholar 

  • Al-Betar, M. A., & Khader, A. T. (2012). A Harmony Search Algorithm for university course timetabling. Annals of Operations Research, 194(1), 3–31.

    Article  Google Scholar 

  • Al-Betar, M. A., Khader, A. T., & Liao, I. Y. (2010). A Harmony Search Algorithm with the multi-pitch adjusting rate for university course timetabling. In Z. W. Geem (Ed.), Recent advances in Harmony Search Algorithm, studies in computational intelligence (SCI) (Vol. 270, pp. 147–162). Berlin, Heidelberg: Springer.

    Chapter  Google Scholar 

  • Al-Betar, M. A., Doush, I. A., Khader, A. T., & Awadallah, M. A. (2012a). Novel selection schemes for Harmony Search. Applied Mathematics and Computation, 218(10), 6095–6117.

    Article  Google Scholar 

  • Al-Betar, M. A., Khader, A. T., & Zaman, M. (2012b). University course timetabling using a hybrid Harmony Search metaheuristic algorithm. IEEE Transactions on Systems, Man and Cybernetics. Part C, Applications and Reviews, 42(5), 664–681.

    Article  Google Scholar 

  • Al-Betar, M. A., Doush, I. A., Geem, Z. W., Khader, A. T., & Awadallah, M. A. (2013). An analysis of selection methods in memory consideration for Harmony Search. Applied Mathematics and Computation, 219(22), 10,753–10,767.

    Article  Google Scholar 

  • Asmuni, H., Burke, E. K., Garibaldi, J. M., & McCollum, B. (2005). Fuzzy multiple heuristic orderings for examination timetabling. In LNCS: Vol. 3616. Proceedings of the 5th international conference on practice and theory of automated timetabling (PATAT2004), Pittsburgh, PA, USA. Berlin: Springer.

    Google Scholar 

  • Asmuni, H., Burke, E. K., Garibaldi, J. M., McCollum, B., & Parkes, A. J. (2009). An investigation of fuzzy multiple heuristic orderings in the construction of university examination timetables. Computers & Operations Research, 36(4), 981–1001.

    Article  Google Scholar 

  • Blum, C., & Roli, A. (2003). Metaheuristics in combinatorial optimization: overview and conceptual comparison. ACM Computing Surveys, 35(3), 268–308.

    Article  Google Scholar 

  • Brélaz, D. (1979). New methods to color the vertices of a graph. Communications of the ACM, 22(4), 251–256.

    Article  Google Scholar 

  • Burke, E. K., & Newall, J. P. (2003). Enhancing timetable solutions with local search methods. In LNCS: Vol. 2740. Proceedings of the 4th international conference on practice and theory of automated timetabling (PATAT2002), KaHo St.-Lieven, Gent, Belgium (pp. 195–206). Berlin: Springer.

    Google Scholar 

  • Burke, E. K., & Newall, J. P. (2004). Solving examination timetabling problems through adaption of heuristic orderings. Annals of Operations Research, 129(1), 107–134.

    Article  Google Scholar 

  • Burke, E. K., Bykov, Y., Newall, J., & Petrovic, S. (2004). A time-predefined local search approach to exam timetabling problems. IIE Transactions, 36(6), 509–528.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • Burke, E. K., Eckersley, A. J., McCollum, B., Petrovic, S., & Qu, R. (2010). Hybrid variable neighbourhood approaches to university exam timetabling. European Journal of Operational Research, 206(1), 46–53.

    Article  Google Scholar 

  • Burke, E. K., Kendall, G., Misir, M., & Özcan, E. (2012). Monte Carlo hyper-heuristics for examination timetabling. Annals of Operations Research, 196(1), 73–90.

    Article  Google Scholar 

  • Caramia, M., Dell’Olmo, P., & Italiano, G. (2008). Novel local-search-based approaches to university examination timetabling. INFORMS Journal on Computing, 20(1), 86–99.

    Article  Google Scholar 

  • Carter, M. W., Laporte, G., & Lee, S. Y. (1996). Examination timetabling: algorithmic strategies and applications. Journal of the Operational Research Society, 74, 373–383.

    Article  Google Scholar 

  • Casey, S., & Thompson, J. (2003). Grasping the examination scheduling problem. In LNCS: Vol. 2740. Proceedings of the 4th international conference on practice and theory of automated timetabling (PATAT2002), KaHo St.-Lieven, Gent, Belgium (pp. 232–244). Berlin: Springer.

    Google Scholar 

  • Cote, P., Wong, T., & Sabouri, R. (2005). Application of a hybrid multi-objective evolutionary algorithm to the uncapacitated exam proximity problem. In LNCS: Vol. 3616. Proceedings of the 5th international conference on practice and theory of automated timetabling (PATAT2001) (pp. 151–168). Berlin: Springer.

    Google Scholar 

  • Di Gaspero, L. (2002). Recolour, shake and kick: a recipe for the examination timetabling problem. In Proceedings of the 4th international conference on practice and theory of automated timetabling (PATAT2002), KaHo St.-Lieven, Gent, Belgium.

    Google Scholar 

  • Di Gaspero, L., & Schaerf, A. (2002). Tabu search techniques for examination timetabling. In LNCS: Vol. 3616. Proceedings of the 3rd international conference on practice and theory of automated timetabling (PATAT2001). Berlin: Springer.

    Google Scholar 

  • Eley, M. (2007). Ant algorithms for the exam timetabling problem. In LNCS: Vol. 3616. Proceedings of the 5th international conference on practice and theory of automated timetabling (PATAT2001) (pp. 364–382). Berlin: Springer.

    Google Scholar 

  • Fesanghary, M., Mahdavi, M., Minary-Jolandan, M., & Alizadeh, Y. (2008). Hybridizing Harmony Search Algorithm with sequential quadratic programming for engineering optimization problems. Computer Methods in Applied Mechanics and Engineering, 197(33–40), 3080–3091.

    Article  Google Scholar 

  • Geem, Z. W., Kim, J. H., & Loganathan, G. V. (2001). A new heuristic optimization algorithm: Harmony Search. Simulation, 76(2), 60–68.

    Article  Google Scholar 

  • Gogos, C., Alefragis, P., & Housos, E. (2012). An improved multi-staged algorithmic process for the solution of the examination timetabling problem. Annals of Operations Research, 194(1), 203–221.

    Article  Google Scholar 

  • Handoko, S., Kwoh, C. K., & Ong, Y. S. (2010). Feasibility structure modeling: an effective chaperone for constrained memetic algorithms. IEEE Transactions on Evolutionary Computation, 14(5), 740–758.

    Article  Google Scholar 

  • Huy, N. Q., Soon, O. Y., Hiot, L. M., & Krasnogor, N. (2009). Adaptive cellular memetic algorithms. Evolutionary Computation, 17(2), 231–256.

    Article  Google Scholar 

  • Ingram, G., & Zhang, T. (2009). Overview of applications and developments in the Harmony Search Algorithm. In Z. W. Geem (Ed.), Music-inspired Harmony Search Algorithm (pp. 15–37). Berlin, Heidelberg: Springer.

    Chapter  Google Scholar 

  • Kendall, G., & Hussin, N. (2005). A tabu search hyper-heuristic approach to the examination timetabling problem at the Mara University of Technology. In LNCS: Vol. 3616. Proceedings of the 5th international conference on practice and theory of automated timetabling (PATAT2001) (pp. 270–293). Berlin: Springer.

    Chapter  Google Scholar 

  • McCollum, B., Schaerf, A., Paechter, B., McMullan, P., Lewis, R., Parkes, A. J., Gaspero, L. D., Qu, R., & Burke, E. K. (2010). Setting the research agenda in automated timetabling: the second international timetabling competition. INFORMS Journal on Computing, 22(1), 120–130.

    Article  Google Scholar 

  • Merlot, L. T. G., Boland, N., Hughes, B. D., & Stuckey, P. J. (2003). A hybrid algorithm for the examination timetabling problem. In LNCS: Vol. 2740. Proceedings of the 4th international conference on practice and theory of automated timetabling (PATAT2002), KaHo St.-Lieven, Gent, Belgium (pp. 207–231). Berlin: Springer.

    Google Scholar 

  • Meuth, R., Lim, M. H., Ong, Y. S., & Wunsch, D. (2009). A proposition on memes and meta-memes in computing for higher-order learning. Memetic Computing, 1, 85–100.

    Article  Google Scholar 

  • Nguyen, Q. H., Ong, Y. S., & Lim, M. H. (2009). A probabilistic memetic framework. IEEE Transactions on Evolutionary Computation, 13(3), 604–623.

    Article  Google Scholar 

  • Ong, Y. S., & Keane, A. (2004). Meta-Lamarckian learning in memetic algorithms. IEEE Transactions on Evolutionary Computation, 8(2), 99–110.

    Article  Google Scholar 

  • Ong, Y. S., Lim, M. H., Zhu, N., & Wong, K. W. (2006). Classification of adaptive memetic algorithms: a comparative study. IEEE Transactions on Systems, Man and Cybernetics. Part B. Cybernetics, 36(1), 141–152.

    Article  Google Scholar 

  • Ong, Y. S., Lim, M., & Chen, X. (2010). Memetic computation—past, present & future [research frontier]. IEEE Computational Intelligence Magazine, 5(2), 24–31.

    Article  Google Scholar 

  • Paquete, L., & Stutzle, T. (2003). Empirical analysis of tabu search for the lexicographic optimization of the examination timetabling problem. In LNCS: Vol. 2740. Proceedings of the 4th international conference on practice and theory of automated timetabling (PATAT2002), KaHo St.-Lieven, Gent, Belgium (pp. 413–420).

    Google Scholar 

  • Pillay, N., & Banzhaf, W. (2009). A study of heuristic combinations for hyper-heuristic systems for the uncapacitated examination timetabling problem. European Journal of Operational Research, 197(2), 482–491.

    Article  Google Scholar 

  • Qu, R., & Burke, E. K. (2009). Hybridizations within a graph-based hyper-heuristic framework for university timetabling problems. Journal of the Operational Research Society, 60, 1273–1285.

    Article  Google Scholar 

  • Qu, R., Burke, E. K., & McCollum, B. (2009a). Adaptive automated construction of hybrid heuristics for exam timetabling and graph colouring problems. European Journal of Operational Research, 198(2), 392–404.

    Article  Google Scholar 

  • Qu, R., Burke, E. K., McCollum, B., Merlot, L. T. G., & Lee, S. Y. (2009b). A survey of search methodologies and automated system development for examination timetabling. Journal of Scheduling, 12(1), 55–89.

    Article  Google Scholar 

  • Tang, J., Lim, M., & Ong, Y. S. (2007). Diversity-adaptive parallel memetic algorithm for solving large scale combinatorial optimization problems. Soft Computing, 11, 873–888.

    Article  Google Scholar 

  • Yang, X. S. (2009). Harmony search as a metaheuristic algorithm. In Z. W. Geem (Ed.), Music-inspired Harmony Search Algorithm (pp. 1–14). Berlin, Heidelberg: Springer.

    Chapter  Google Scholar 

  • Yang, Y., & Petrovic, S. (2005). A novel similarity measure for heuristic selection in examination timetabling. In LNCS: Vol. 3616. Proceedings of the 5th international conference on practice and theory of automated timetabling (PATAT2001) (pp. 247–269). Berlin: Springer.

    Chapter  Google Scholar 

Download references

Acknowledgements

The authors sincerely appreciate the helpful and insightful comments from the anonymous referees, which have greatly improved the clarity of the paper. The first author is grateful to be awarded a Postdoctoral Fellowship from the School of Computer Sciences (USM).

Author information

Authors and Affiliations

  1. School of Computer Sciences, Universiti Sains Malaysia, 11800 USM, Penang, Malaysia

    Mohammed Azmi Al-Betar & Ahamad Tajudin Khader

  2. Department of Information Technology, Al-Huson University College, Al-Balqa Applied University, P.O. Box 50, Al-Huson, Irbid, Jordan

    Mohammed Azmi Al-Betar

  3. Computer Science Department, Computer Science and Information Technology Faculty, Yarmouk University, Irbid, 21163, Jordan

    Iyad Abu Doush

Authors
  1. Mohammed Azmi Al-Betar
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ahamad Tajudin Khader
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Iyad Abu Doush
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Mohammed Azmi Al-Betar.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Al-Betar, M.A., Khader, A.T. & Doush, I.A. Memetic techniques for examination timetabling. Ann Oper Res 218, 23–50 (2014). https://doi.org/10.1007/s10479-013-1500-7

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10479-013-1500-7

Keywords

Search

Navigation