Multiple-retrieval case-based reasoning for course timetabling problems
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 organised as a decision tree and the retrieval process chooses those cases which are sub...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Published: |
Palgrave Macmillan
2006
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/372/ |
| _version_ | 1848790402302214144 |
|---|---|
| author | Burke, Edmund MacCarthy, Bart L. Petrovic, Sanja Qu, Rong |
| author_facet | Burke, Edmund MacCarthy, Bart L. Petrovic, Sanja Qu, Rong |
| author_sort | Burke, Edmund |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | 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 organised as a decision tree and the retrieval process chooses those cases which 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 dependant 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 initialisation 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 initialisation method for these approaches. |
| first_indexed | 2025-11-14T18:12:03Z |
| format | Article |
| id | nottingham-372 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| last_indexed | 2025-11-14T18:12:03Z |
| publishDate | 2006 |
| publisher | Palgrave Macmillan |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-3722020-05-04T20:29:34Z https://eprints.nottingham.ac.uk/372/ Multiple-retrieval case-based reasoning for course timetabling problems Burke, Edmund MacCarthy, Bart L. Petrovic, Sanja Qu, Rong 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 organised as a decision tree and the retrieval process chooses those cases which 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 dependant 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 initialisation 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 initialisation method for these approaches. Palgrave Macmillan 2006-02 Article PeerReviewed Burke, Edmund, MacCarthy, Bart L., Petrovic, Sanja and Qu, Rong (2006) Multiple-retrieval case-based reasoning for course timetabling problems. Journal of the Operational Research Society, 57 (2). pp. 148-162. ISSN 0160-5682 Timetabling problems Case-Based Reasoning Attribute graph Scheduling problems Hill climbing Tabu search Simulate annealing Graph heuristic method http://www.palgrave-journals.com/jors/journal/v57/n2/pdf/2601970a.pdf |
| spellingShingle | Timetabling problems Case-Based Reasoning Attribute graph Scheduling problems Hill climbing Tabu search Simulate annealing Graph heuristic method Burke, Edmund MacCarthy, Bart L. Petrovic, Sanja Qu, Rong Multiple-retrieval case-based reasoning for course timetabling problems |
| title | Multiple-retrieval case-based reasoning for course timetabling problems |
| title_full | Multiple-retrieval case-based reasoning for course timetabling problems |
| title_fullStr | Multiple-retrieval case-based reasoning for course timetabling problems |
| title_full_unstemmed | Multiple-retrieval case-based reasoning for course timetabling problems |
| title_short | Multiple-retrieval case-based reasoning for course timetabling problems |
| title_sort | multiple-retrieval case-based reasoning for course timetabling problems |
| topic | Timetabling problems Case-Based Reasoning Attribute graph Scheduling problems Hill climbing Tabu search Simulate annealing Graph heuristic method |
| url | https://eprints.nottingham.ac.uk/372/ https://eprints.nottingham.ac.uk/372/ |