Abstract
Metaheuristic approaches to examination timetabling problems are usually split into two phases: an initialisation phase in which a sequential graph colouring heuristic is employed to construct an initial solution and an improvement phase in which the initial solution is gradually improved. Different hybridisations of metaheuristics with sequential heuristics are known to lead to solutions of different quality. A Case Based Reasoning (CBR) methodology has been developed for selecting an appropriate sequential construction heuristic for hybridisation with the Great Deluge metaheuristic. In this paper we propose a new similarity measure between two timetabling problems that is based on fuzzy sets. The experiments were performed on a number of real-world benchmark problems and the results were also compared with other state-of-the-art methods. The results obtained show the effectiveness of the developed CBR system.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Burke, E.K., Bykov, Y., Newall, J.P., Petrovic, S.: A Time-Predefined Local Search Approach to Exam Timetabling Problems. IIE Trans. Oper. Eng. 36, 509–528 (2004)
Burke, E.K., Eckersley, A.J., McCollum, B., Petrovic, S., Qu, R.: Similarity Measures For Exam Timetabling Problems. In: Proc. 1st Multidisciplinary International Conference on Scheduling: Theory and Applications, pp. 120–136 (2003)
Burke, E.K., Dror, M., Petrovic, S., Qu, R.: Hybrid Graph Heuristics in a Hyper-Heuristic Approach to Exam Timetabling. In: Golden, B.L., Raghavan, S., Wasil, E.A. (eds.) The Next Wave in Computing, Optimization and Decision Technologies, pp. 79–92. Springer, Heidelberg (2005)
Burke, E.K., Elliman, D.G., Ford, P.H., Weare, R.F.: Examination Timetabling in British Universities—A Survey. In: Burke, E.K., Ross, P. (eds.) PATAT 1995. LNCS, vol. 1153, pp. 76–92. Springer, Heidelberg (1996)
Burke, E.K., Hart, E., Kendall, G., Newall, J., Ross, P., Schulenburg, S.: Hyper-Heuristics: An Emerging Direction in Modern Search Technology. In: Glover, F., Kochenberger, G. (eds.) Handbook of Meta-heuristics, ch. 16, pp. 457–474. Kluwer, Dordrecht (2003)
Burke, E.K., Kendall, G., Soubeiga, E.: A Tabu Search Hyper-heuristic for Timetabling and Rostering. J. Heuristics 9, 451–470 (2003)
Burke, E., Kingston, J., De Werra, D.: Applications to Timetabling. Section 5.6. In: Gross, J., Yellen, J. (eds.) Handbook of Graph Theory, pp. 445–474. Chapman and Hall/CRC Press, London (2004)
Burke, E.K., Landa, J.D.: Design of Memetic Algorithms for Scheduling and Timetabling Problems. In: Krasnogor, N., Hart, W., Smith, J. (eds.) Recent Advances in Memetic Algorithms and Related Search Technologies, pp. 289–312. Springer, Heidelberg (2004)
Burke, E.K., MacCarthy, B., Petrovic, S., Qu, R.: Structured Cases in CBR—Re-using and Adapting Cases for Time-Tabling Problems. Knowledge-Based Syst. 13, 159–165 (2000)
Burke, E., MacCarthy, B., Petrovic, S., Qu, R.: Knowledge Discovery in a Hyper-heuristic Using Case-Based Reasoning for Course Timetabling. In: Burke, E.K., De Causmaecker, P. (eds.) PATAT 2002. LNCS, vol. 2740, pp. 276–287. Springer, Heidelberg (2003)
Burke, E.K., MacCarthy, B., Petrovic, S., Qu, R.: Multiple-Retrieval Case Based Reasoning for Course Timetabling Problems. J. Oper. Res. Soc. (2005) (accepted for publication)
Burke, E.K., Meisels, A., Petrovic, S., Qu, R.: A Graph-Based Hyper Heuristic for Timetabling Problems. Eur. J. Oper. Res. (2005) (accepted for publication)
Burke, E.K., Newall, J.P., Weare, R.F.: A Memetic Algorithm for University Exam Timetabling. In: Burke, E.K., Ross, P. (eds.) PATAT 1995. LNCS, vol. 1153, pp. 241–250. Springer, Heidelberg (1996)
Burke, E.K., Newall, J.P.: 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)
Burke, E.K., Newall, J.P., Weare, R.F.: Initialisation Strategies and Diversity in Evolutionary Timetabling. Evol. Comput. 6, 81–103 (1998)
Burke, E.K., Newell, J.P.: Solving Examination Timetabling Problems Through Adaptation of Heuristic Orderings. Ann. Oper. Res. 129, 107–134 (2004)
Burke, E.K., Newell, J.P., Weare, R.F.: A Simple Heuristically Guided Search for the Timetable Problem. In: Proceedings of the International ICSC Symposium on Engineering of Intelligent Systems (University of La Laguna), pp. 574–579. Academic, New York (1998)
Burke, E.K., Petrovic, S.: Recent Research Directions in Automated Timetabling. Eur. J. Oper. Res. 140, 266–280 (2002)
Burke, E.K., Petrovic, S., Qu, R.: Case Based Heuristic Selection for Timetabling Problems. J. Scheduling (2006) (accepted for publication)
Carter, M.W.: A Survey of Practical Applications on Examination Timetabling. Oper. Res. 34, 193–202 (1986)
Carter, M.W., Laporte, G.: Recent Developments in Practical Course Timetabling. In: Burke, E.K., Ross, P. (eds.) PATAT 1995. LNCS, vol. 1153, pp. 3–21. Springer, Heidelberg (1996)
Carter, M.W., Laporte, G., Chinneck, J.W.: A General Examination Scheduling System. Interfaces 24, 109–120 (1994)
Carter, M.W., Laporte, G., Lee, S.Y.: Examination Timetabling: Algorithmic Strategies and Applications. J. Oper. Res. Soc. 47, 373–383 (1996)
Carter, M.W., Johnson, D.G.: Extended Clique Initialisation in Examination Timetabling. J. Oper. Res. Soc. 52, 538–544 (2001)
Casey, S., Thompson, J.: GRASPing the Examination Scheduling Problem. In: Burke, E.K., De Causmaecker, P. (eds.) PATAT 2002. LNCS, vol. 2740, pp. 232–246. Springer, Heidelberg (2003)
Deng, P.S.: Using Case-Based Reasoning Approach to the Support of Ill-structured Decisions. Eur. J. Oper. Res. 93, 511–521 (1996)
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)
Dueck, G.: New Optimization Heuristics. J. Comput. Phys. 104, 86–92 (1993)
Garey, M.R., Johnson, D.S.: Computers and Intractability a Guide to the Theory of NP-completeness. Freeman, San Francisco (1977)
Gendreau, M., Soriano, P., Salvail, L.: Solving the Maximum Clique Problem Using a Tabu Search Approach. Ann. Oper. Res. 41, 385–403 (1993)
Johnson, D.: Timetabling University Examinations. J. Oper. Res. Soc. 41, 39–47 (1990)
Kolodner, J.: Case-Based Reasoning. Morgan Kaufmann, San Mateo (1993)
Laporte, G., Desroches, S.: Examination Timetabling by Computer. Comput. Oper. Res. 11, 351–360 (1984)
Leake, D.B.: CBR in Context: the Present and Future, Case-Based Reasoning: Experiences, Lessons, and Future Directions. AAAI Press/MIT Press, Menlo Park (1996)
Merlot, L.T.G., Boland, N., Hughes, B.D., Stuckey, P.J.: A Hybrid Algorithm for the Examination Timetabling Problem. In: Burke, E.K., De Causmaecker, P. (eds.) PATAT 2002. LNCS, vol. 2740, pp. 205–232. Springer, Heidelberg (2003)
Miyashita, K., Sycara, K.: CABINS: A Framework of Knowledge Acquisition and Iterative Revision for Schedule Improvement and Reactive Repair. Artif. Intell. 76, 377–426 (1995)
Petrovic, S., Beddoe, G.R., Berghe, G.V.: Storing and Adapting Repair Experiences in Employee Rostering. In: Burke, E.K., De Causmaecker, P. (eds.) PATAT 2002. LNCS, vol. 2740, pp. 149–166. Springer, Heidelberg (2003)
Petrovic, S., Burke, E.: Educational Timetabling. In: Leung, J. (ed.) Handbook of Scheduling: Algorithms, Models, and Performance Analysis, ch. 45, pp. 45.1–45.23. Chapman and Hall/CRC Press, London (2004)
Petrovic, S., Kendall, G., Yang, Y.: A Tabu Search Approach for Graph-Structured Case Retrieval. In: Proc. STarting Artificial Intelligence Researchers Symposium (France), pp. 55–64. IOS Press, Amsterdam (2002)
Petrovic, S., Yang, Y., Dror, M.: Case-based Initialisation of Metaheuristics for Examination Timetabling. In: Kendall, G., Burke, E., Petrovic, S., Gendreau, M. (eds.) Multidisciplinary Scheduling Theory and Applications, pp. 289–308. Springer, Berlin (2005)
Petrovic, S., Yang, Y., Dror, M.: Use of Case Based Reasonin. Solving Examination Timetabling Problems. Technical Report NOTTCS-TR-2004-6, University of Nottingham, UK (2004)
Schirmer, A.: Case-Based Reasoning and Improved Adaptive Search for Project Scheduling. Naval Res. Log. 47, 201–222 (2000)
Schmidt, G.: Case-Based Reasoning for Production Scheduling. Int. J. Product. Econ. 56/7, 537–546 (1998)
Terashima-Marín, H., Ross, P., Valenzuela-Rendón, M.: Evolution of Constraint Satisfaction Strategies in Examination Timetabling. In: Proceedings of the Genetic and Evolutionary Conference, pp. 635–642 (1999)
Thompson, J.M., Dowsland, K.A.: Variants of Simulated Annealing for the Examination Timetabling Problem. Ann. Oper. Res. 63, 105–128 (1996)
Welsh, D.J.A., Powell, M.B.: An Upper Bound on the Chromatic Number of a Graph and its Application to Timetabling Problems. Comput. J. 10, 85–86 (1967)
White, G.M., Xie, B.S., Zonjic, X.: Using Tabu Search With Longer-Term Memory and Relaxation to Create Examination Timetables. Eur. J. Oper. Res. 153, 80–91 (2004)
Zadeh, L.A.: Fuzzy Sets. Inform. Control 8, 338–353 (1965)
Zadeh, L.A.: The Concept of a Linguistic Variable and its Application to Approximate Reasoning. Inform. Sci. 8(9), 199–249, 43–80, respectively (1975)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Yang, Y., Petrovic, S. (2005). A Novel Similarity Measure for Heuristic Selection in Examination Timetabling. In: Burke, E., Trick, M. (eds) Practice and Theory of Automated Timetabling V. PATAT 2004. Lecture Notes in Computer Science, vol 3616. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11593577_15
Download citation
DOI: https://doi.org/10.1007/11593577_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-30705-1
Online ISBN: 978-3-540-32421-8
eBook Packages: Computer ScienceComputer Science (R0)