Skip to main content
SpringerLink
Log in

Multiple-retrieval case-based reasoning for course timetabling problems

  • Theoretical Paper
  • Published:
Journal of the Operational Research Society

Abstract

The structured representation of cases by attribute graphs in a case-based reasoning (CBR) system for course timetabling has been the subject of previous research by the authors. In that system, the case base is organized as a decision tree and the retrieval process chooses those cases that are sub-attribute graph isomorphic to the new case. The drawback of that approach is that it is not suitable for solving large problems. This paper presents a multiple-retrieval approach that partitions a large problem into small solvable sub-problems by recursively inputting the unsolved part of the graph into the decision tree for retrieval. The adaptation combines the retrieved partial solutions of all the partitioned sub-problems and employs a graph heuristic method to construct the whole solution for the new case. We present a methodology which is not dependent upon problem-specific information and which, as such, represents an approach which underpins the goal of building more general timetabling systems. We also explore the question of whether this multiple-retrieval CBR could be an effective initialization method for local search methods such as hill climbing, tabu search and simulated annealing. Significant results are obtained from a wide range of experiments. An evaluation of the CBR system is presented and the impact of the approach on timetabling research is discussed. We see that the approach does indeed represent an effective initialization method for these approaches.

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

Figure 1
Figure 2
Figure 3
Figure 4
Figure 5
Figure 6
Figure 7
Figure 8
Figure 9
Figure 10

Similar content being viewed by others

References

  • Wren A and Rousseau J-M (1995). Bus driver scheduling—an overview. In: Daduna JR, Branco I and Paix’ao JMP (eds). Computer-Aided Transit Scheduling. Springer-Verlag, Berlin, pp 173–187.

    Chapter  Google Scholar 

  • Easton K, Nemhauser G and Trick M (2004). Sports scheduling. In: Leung J (ed). Handbook of Scheduling: Algorithms, Models, and Performance Analysis, Chapter 52. CRC Press, Boca Raton, FL.

    Google Scholar 

  • Cheang B, Li H, Lim A and Rodrigues B (2003). Nurse rostering problems—a bibliographic survey. Eur J Opl Res 151: 447–460.

    Article  Google Scholar 

  • Burke E, De Causmaecker P, Vanden Berghe G and Van Landeghem H. (2004). The state of the art of nurse rostering. J Scheduling 7: 441–499.

    Article  Google Scholar 

  • Carter M and Laporte G (1995). Recent developments in practical examination timetabling. In: Burke E and Ross P (eds). The Practice and Theory of Automated Timetabling: Selected Papers from the 1st International Conference. Lecture Notes in Computer Science, Vol. 1153. Springer-Verlag, Berlin, pp 3–21.

    Google Scholar 

  • Bardadym V (1995). Computer-aided school and university timetabling: the new wave. In: Burke E and Ross P (eds). The Practice and Theory of Automated Timetabling: Selected Papers from the 1st International Conference. Lecture Notes in Computer Science, Vol. 1153. Springer-Verlag, Berlin, pp 22–45.

    Google Scholar 

  • Carter M and Laporte G (1997). Recent developments in practical course timetabling. In: Burke E and Carter M (eds). The Practice and Theory of Automated Timetabling: Selected Papers from the 2nd International Conference. Lecture Notes in Computer Science, Vol. 1408. Springer-Verlag, Berlin, pp 3–19.

    Google Scholar 

  • Burke E and Ross P (1995). The Practice and Theory of Automated Timetabling: Selected Papers from the 1st International Conference. Lecture Notes in Computer Science, Vol. 1153. Springer-Verlag: Berlin.

    Google Scholar 

  • Burke E and Carter MW (1997). The Practice and Theory of Automated Timetabling: Selected Papers from the 2nd International Conference. Lecture Notes in Computer Science, Vol. 1408. Springer-Verlag: Berlin.

    Google Scholar 

  • Burke E and Erben W (eds) (2000). The Practice and Theory of Automated Timetabling: Selected Papers from the 3rd International Conference. Lecture Notes in Computer Science, Vol. 2079. Springer-Verlag: Berlin.

    Google Scholar 

  • Burke E and de Causmaecker P (2002). The Practice and Theory of Automated Timetabling: Selected Papers from the 4th International Conference. Lecture Notes in Computer Science, Vol. 2740. Springer-Verlag: Berlin.

    Google Scholar 

  • Burke E and Trick M (eds) (2004). The Proceedings of the 5th International Conference on the Practice and Theory of Automated Timetabling. Carnegie Mellon University: Pittsburgh, USA.

    Google Scholar 

  • Wren A (1995). Scheduling, timetabling and rostering—a special relationship? In: Burke E and Ross P (eds). The Practice and Theory of Automated Timetabling: Selected papers from the 1st International Conference. Lecture Notes in Computer Science, Vol. 1153. Springer-Verlag, Berlin, pp 46–75.

    Google Scholar 

  • Burke E and Petrovic S (2002). Recent research directions in automated timetabling. Eur J Opl Res 140: 266–280.

    Article  Google Scholar 

  • Petrovic S and Burke E (2004). University timetabling. In: Leung J (ed). Handbook of Scheduling: Algorithms, Models, and Performance Analysis, Chapter 45. CRC Press, Boca Raton, RL.

    Google Scholar 

  • Schaerf A (1999). A survey of automated timetabling. Artif Intelli Rev 13: 87–127.

    Article  Google Scholar 

  • Carter M (1986). A lagrangian relaxation approach to the classroom assignment problem. INFOR 27: 230–246.

    Google Scholar 

  • de Werra D (1985). Graphs, hypergraphs and timetabling. Methods Opns Res (Germany F.R.) 49: 201–213.

    Google Scholar 

  • Burke E, Kingston J and de Werra D (2004). Applications to timetabling. In: Gross J and Yellen J (eds). Handbook of Graph Theory. Chapman & Hall/CRC Press, London, Boca Raton, FL, pp 445–474.

    Google Scholar 

  • Schaerf A (1996). Tabu search techniques for large high-school timetabling problems. In: Franz A and Kitano H (eds). Proceedings of the Thirteenth National Conference on Artificial Intelligence. AAAI Press: Menlo Park, CA, pp 363–368.

    Google Scholar 

  • Costa D (1994). A tabu search algorithm for computing an operational timetable. Eur J Opl Res 76: 98–110.

    Article  Google Scholar 

  • Abramson D (1991). Constructing school timetables using simulated annealing: sequential and parallel algorithms. Mngt Sci 37: 98–113.

    Article  Google Scholar 

  • Elmohamed MAS, Coddington P and Fox G (1997). A comparison of annealing techniques for academic course scheduling. In: Burke E and Carter M (eds). The Practice and Theory of Automated Timetabling: Selected Papers from the 2nd International Conference. Lecture Notes in Computer Science, Vol. 1408. Springer-Verlag, Berlin, pp 92–112.

    Google Scholar 

  • Burke E, Bykov Y, Newall J and Petrovic S (2003). A time-predefined approach to course timetabling. Yugoslav J Opns Res 13: 139–151.

    Article  Google Scholar 

  • Erben W and Keppler J (1995). A genetic algorithm solving a weekly course-timetabling problem. In: Burke E and Ross P (eds). The Practice and Theory of Automated Timetabling: Selected papers from the 1st International Conference. Lecture Notes in Computer Science, Vol. 1153. Springer-Verlag, Berlin, pp 198–211.

    Google Scholar 

  • Paechter B, Cumming A and Luchian H (1995). The use of local search suggestions lists for improving the solutions of timetable problems with evolutionary algorithms. In: Fogarty T (ed). AISB Workshop on Evolutionary Computing. Lecture Notes in Computer Science, Vol. 993. Springer-Verlag, Berlin, pp 86–93.

    Google Scholar 

  • Carrasco M and Pato M (2000). A multiobjective genetic algorithm for the class/teacher timetabling problem. In: Burke E and Erben W (eds). The Practice and Theory of Automated Timetabling: Selected papers from the 3rd International Conference. Lecture Notes in Computer Science, Vol. 2079. Springer-Verlag, Berlin, pp 3–17.

    Google Scholar 

  • Burke E, Newall J and Weare R (1996). A memetic algorithm for university timetabling. In: Burke E and Ross P (eds). The Practice and Theory of Automated Timetabling: Selected Papers from the 1st International Conference. Lecture Notes in Computer Science, Vol. 1153. Springer-Verlag, Berlin, pp 241–250.

    Chapter  Google Scholar 

  • Burke E, Newall J and Weare R (1998). Initialisation strategies and diversity in evolutionary timetabling. Evol Comput J (special issue on scheduling) 6: 81–103.

    Article  Google Scholar 

  • Lajos G (1996). Complete university modular timetabling using constraint logic programming. In: Burke E and Ross P (eds). The Practice and Theory of Automated Timetabling: Selected Papers from the 1st International Conference. Lecture Notes in Computer Science, Vol. 1153. Springer-Verlag, Berlin, pp 146–161.

    Chapter  Google Scholar 

  • Deris SB, Omatu S, Ohta H and Samat PABD (1997). University timetabling by constraint-based reasoning: A case study. J Opl Res Soc 48: 1178–1190.

    Article  Google Scholar 

  • Nonobe K and Ibaraki T (1998). A tabu search approach to the constraint satisfaction problem as a general problem solver. Eur J Opl Res 106: 599–623.

    Article  Google Scholar 

  • ten Eikelder HMM and Willemen RJ (2000). Some complexity aspects of secondary school timetabling problems. In: Burke E and Erben W (eds). The Practice and Theory of Automated Timetabling: Selected Papers from the 3rd International Conference. Lecture Notes in Computer Science, Vol. 2079. Springer-Verlag, Berlin, pp 18–27.

    Google Scholar 

  • de Werra D, Asratian AS and Durand S (2002). Complexity of some special types of timetabling problems. J Scheduling 5: 171–184.

    Article  Google Scholar 

  • Burke E, MacCarthy B, Petrovic S and Qu R (2000). Structured cases in case-based reasoning re-using and adapting cases for timetabling problems. Knowledge-based System 13: 159–165.

    Article  Google Scholar 

  • Burke E, MacCarthy B, Petrovic S and Qu R (2001). Case-based reasoning in course timetabling: an attribute graph approach. In: Aha DW and Watson I (eds). Case-Based Reasoning Research and Development. Proceedings of 4th International Conference on Case-Based Reasoning (ICCBR-2001). Lecture Notes in Artificial Intelligence, Vol. 2080. Springer-Verlag, Berlin, pp 90–104.

    Google Scholar 

  • Kolodner J (1993). Case Based Reasoning. Morgan Kaufmann: Los Altos, CA.

    Book  Google Scholar 

  • Leake D (ed). (1996). Case-Based Reasoning: Experiences, Lessons, & Future Directions. The AAAI Press, MIT Press: Cambridge, MA, USA.

    Google Scholar 

  • Aamodt A and Plaza E (1994). Case-based reasoning: foundational issues, methodological variations and system approaches. AI Commun 7: 39–59.

    Google Scholar 

  • Mantaras RL and Plaza E (1997). Case-based reasoning: an overview. AI Commun 10: 21–29.

    Google Scholar 

  • Burke E, Elliman D, Ford P and Weare R (1996). Examination timetabling in British universities - a survey. In: Burke E and Ross P (eds). The Practice and Theory of Automated Timetabling: Selected Papers from the 1st International Conference. Lecture Notes in Computer Science, Vol. 1153. Springer-Verlag, Berlin, pp 76–92.

    Chapter  Google Scholar 

  • Burke E, De Causmaecker P and Vanden Berghe G. (1998). A hybrid tabu search algorithm for the nurse rostering problem. In: McKay B, Yao X, Newton CS, Kim JH and Furuhashi T (eds). Proceedings of the Second Asia-Pacific Conference on Simulated Evolution and Learning. Springer-Verlag, Berlin, pp 187–194.

    Google Scholar 

  • Watson JP, Rana S, Whitley LD and Howe AE (1999). The impact of approximate evaluation on the performance of search algorithms for warehouse scheduling. J Scheduling 2: 79–98.

    Article  Google Scholar 

  • Aickelin U and Dowsland K (2000). Exploiting problem structure in a genetic algorithm approach to a nurse rostering problem. J Scheduling 3: 139–154.

    Article  Google Scholar 

  • Di Gaspero and Schaerf A (2000). Tabu search techniques for examination timetabling. In: Burke E and Erben W (eds). The Practice and Theory of Automated Timetabling: Selected Papers from the 3rd International Conference. Lecture Notes in Computer Science, Vol. 2079. Springer-Verlag, Berlin, pp 104–117.

    Google Scholar 

  • Marir F and Watson I (1994). Case-based reasoning: a categorised bibliography. Knowledge Eng Rev 9: 355–381.

    Article  Google Scholar 

  • Burke E, Hart E, Kendall G, Newall J, Ross P and Schulenburg S (2003). Hyper-heuristics: an emerging direction in modern search technology. In: Glover F and Kochenberger G (eds). Handbook of Meta-Heuristics. Kluwer, Boston, pp 457–474.

    Google Scholar 

  • Koton P (1989). SMARTplan: a case-based resource allocation and scheduling system. In: Hammond K (ed). Proceedings of the Workshop on Case-based Reasoning (DARPA). Morgan Kaufmann, San Francisco, CA, pp 285–289.

    Google Scholar 

  • Hennessy D and Hinkle D (1992). Applying case-based reasoning to autoclave loading. IEEE Expert 7: 21–26.

    Article  Google Scholar 

  • Bezirgan A (1993). A case-based approach to scheduling constraints. In: Dorn J and Froeschl KA (eds). Scheduling of Production Processes. Ellis Horwood Limited, Chichester, UK, pp 48–60.

    Google Scholar 

  • Miyashita K and Sycara K (1995). CABINS: a framework of knowledge acquisition and iterative revision for schedule improvement and reactive repair. Artif Intelli 76: 377–426.

    Article  Google Scholar 

  • Dorn J (1995). Case-based reactive scheduling. In: R Kerr, E Szelke (eds.) Artificial Intelligence in Reactive Scheduling. London, Chapman & Hall, pp 32–50.

    Chapter  Google Scholar 

  • Cunningham P and Smyth B (1997). Case-based reasoning in scheduling: reusing solution components. Int J Prod Res 35: 2947–2961.

    Article  Google Scholar 

  • Beddoe G and Petrovic S (2005). Determining feature weight using a genetic algorithm in a case-based reasoning approach to personnel rostering. Eur J Opl Res (forthcoming).

  • Scott S and Simpson R (1998). Case-bases incorporating scheduling constraint dimensions: experiences in nurse rostering. In: Smyth B and Cunningham P (eds). Advances in Case-Based Reasoning EWCBR98, Lecture Notes in Artificial Intelligence 1488. Springer-Verlag, Berlin, pp 392–401.

    Google Scholar 

  • Szelke E and Markus G (1997). A learning reactive scheduler using CBR/L. Comput Ind 33: 31–46.

    Article  Google Scholar 

  • Schmidt G (1998). Case-based reasoning for production scheduling. Int J Prod Econom 56-57: 537–546.

    Article  Google Scholar 

  • MacCarthy B and Jou P (1995). A case-based expert system for scheduling problems with sequence dependent set up times. In: Adey RA and Rzevski G (eds). Applications of Artificial Intelligence. Engineering X. Computational Machines Publications, Southampton, pp 89–96.

    Google Scholar 

  • MacCarthy B and Jou P (1996). Case-based reasoning in scheduling. In: Khan MK and Wright CS (eds), Proceedings of the Symposium on Advanced Manufacturing Processes, Systems and Techniques (AMPST96). MEP Publications Ltd, Bradford, UK, pp 211–218.

    Google Scholar 

  • Carter M (1983). A decomposition algorithm for practical timetabling problems. Working paper 83-06, Industrial Engineering, University of Toronto.

    Google Scholar 

  • Robert V and Hertz A (1995). How to decompose constrained course scheduling problems into easier assignment type subproblems. In: Burke E and Ross P (eds). The Practice and Theory of Automated Timetabling: Selected Papers from the 1st International Conference. Lecture Notes in Computer Science, Vol. 1153. Springer-Verlag, Berlin, pp 364–373.

    Google Scholar 

  • Weare RF (1995). Automated examination timetabling. PhD dissertation, Department of Computer Science, University of Nottingham.

    Google Scholar 

  • Burke E and Newall J (1999). A multistage evolutionary algorithm for the timetable problem. IEEE Trans Evol Comput 3: 63–74.

    Article  Google Scholar 

  • Marir F and Watson I (1995). Representation and indexing building refurbishment cases for multiple retrieval of adaptable pieces of cases. In: Veloso M and Aamodt A (eds). Case-Based Reasoning Research & Development: Proceedings of the 1st International Conference on Case-Based Reasoning (ICCBR-95). Springer-Verlag, Heidelberg, pp 55–66.

    Chapter  Google Scholar 

  • Smyth B, Keane M and Cunningham P (2001). Hierarchical case-based reasoning. IEEE Trans Knowledge Data Eng 13: 793–812.

    Article  Google Scholar 

  • Börner K, Coulon CH, Pippig E and Tammer EC (1996). Structural similarity and adaptation. In: Smith I and Faltings B (eds). Advances in Case-based Reasoning: Proceedings of the 4th European Workshop (EWCBR’98). Springer-Verlag, Heidelberg, pp 58–75.

    Chapter  Google Scholar 

  • Andersen WA, Evett MP, Kettler B and Hendler J (1994). Massively parallel support for case-based planning. IEEE Expert 7: 8–14.

    Google Scholar 

  • Macedo L and Cardoso A (1998). Nested graph-structured representations for cases. In: Smyth B and Cunningham P (eds). Advances in Case-Based Reasoning: Proceedings of the 4th European Workshop on Case-Based Reasoning. Lecture Notes on Artificial Intelligence, Vol. 1488. Springer-Verlag, Heidelberg, pp 1–11.

    Chapter  Google Scholar 

  • Sanders KE, Kettler BP and Hendler JA (1997). The case for graph-structured representations. In: Leake D and Plaza E (eds). Case-Based Reasoning Research and Development: Proceedings of the 2nd International Conference on Case-Based Reasoning (ICCBR-97). Springer-Verlag, Berlin, pp 245–254.

    Chapter  Google Scholar 

  • Ricci F and Senter L (1998). Structured cases, trees and efficient retrieval. Advances in case-based reasoning. In: Smyth B and Cunningham P (eds). Proceedings of the 4th European Workshop on Case-Based Reasoning. Lecture Notes on Artificial Intelligence, Vol. 1488. Springer-Verlag, Heidelberg, pp 88–99.

    Chapter  Google Scholar 

  • Gebhardt F (1995). Methods and systems for case retrieval exploiting the case structure. FABEL-Report 39, GMD, Sankt Augustin.

    Google Scholar 

  • Gebhardt F (1997). Survey on structure-based case retrieval. Knowledge Engi Rev 12: 41–58.

    Article  Google Scholar 

  • Burke E, Newall J and Weare R (1998). A simple heuristically guided search for the timetable problem. In: Alpaydin E (ed). Proceedings of the International ICSC Symposium on Engineering of Intelligent Systems. ICSC Academic Press, Canada, pp 574–579.

    Google Scholar 

  • Corne DW and Ross PM (1996). Peckish initialisation strategies for evolutionary timetabling. In: Burke E and Ross P (eds). The Practice and Theory of Automated Timetabling: Selected Papers from the 1st International Conference. Lecture Notes in Computer Science, Vol. 1153. Springer-Verlag, Berlin, pp 227–240.

    Chapter  Google Scholar 

  • Rossi-Doria O, Blum C, Knowles J, Sampels M, Socha K and Paechter B (2002). A local search for the timetabling problem. In: Burke E and De Causmaecker P (eds). Proceedings of the 4th International Conference on the Practice and Theory of Automated Timetabling, PATAT 2002 Ka Ho St.-Lieven, Gent, Belgium, pp 124–127.

  • Socha K, Knowles J and Sampels M (2002). A max-min ant system for the university course timetabling problem. In: Proceedings of the 3rd International Workshop on Ant Algorithms, ANTS 2002. Lecture Notes in Computer Science, Vol. 2463. Springer, Berlin, pp 1–13.

    Google Scholar 

  • Burke E, Kendall G and Soubeiga E (2003). A tabu search hyperheuristic for timetabling and rostering. J Heuristics 9: 451–470.

    Article  Google Scholar 

  • Kostuch P (2004). The university course timetabling problem with a 3-phase approach. In: Burke E and Trick M (eds). The Proceedings of the 5th International Conference on the Practice and Theory of Automated Timetabling. Carnegie Mellon University, Pittsburgh, USA, pp 251–266.

    Google Scholar 

  • Williams ML, Wilson RC and Hancock ER (1999). Deterministic search for relational graph matching. Pattern Recognition 32: 1255–1271.

    Article  Google Scholar 

  • Cross ADJ, Myers R and Hancock ER (2000). Convergence of a hill-climbing genetic algorithm for graph matching. PatternRecognition 33: 1863–1880.

    Google Scholar 

Download references

Acknowledgements

We thank Dr Jim Newall for his comments on this work. We also acknowledge the invaluable comments from the anonymous referees. One referee, in particular, was extremely helpful in substantially improving this paper.

Author information

Authors and Affiliations

  1. School of Computer Science and Information Technology, The University of Nottingham, Nottingham, UK

    E K Burke, S Petrovic & R Qu

  2. Business School, The University of Nottingham, Nottingham, UK

    B L MacCarthy

Authors
  1. E K Burke
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. B L MacCarthy
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. S Petrovic
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. R Qu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to R Qu.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Burke, E., MacCarthy, B., Petrovic, S. et al. Multiple-retrieval case-based reasoning for course timetabling problems. J Oper Res Soc 57, 148–162 (2006). https://doi.org/10.1057/palgrave.jors.2601970

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/palgrave.jors.2601970

Keywords

Search

Navigation