Multiple-retrieval case-based reasoning for course timetabling problems

E K Burke, B L MacCarthy, S Petrovic () and R Qu ()
Additional contact information
E K Burke: School of Computer Science and Information Technology, The University of Nottingham
B L MacCarthy: Business School, The University of Nottingham
S Petrovic: School of Computer Science and Information Technology, The University of Nottingham
R Qu: School of Computer Science and Information Technology, The University of Nottingham

Journal of the Operational Research Society, 2006, vol. 57, issue 2, 148-162

Abstract: 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.

Keywords: timetabling; case-based reasoning (CBR); attribute graph; tabu search; simulated annealing (search for similar items in EconPapers)
Date: 2006
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://link.springer.com/10.1057/palgrave.jors.2601970 Abstract (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:pal:jorsoc:v:57:y:2006:i:2:d:10.1057_palgrave.jors.2601970

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/41274

DOI: 10.1057/palgrave.jors.2601970

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald and Jonathan Crook

More articles in Journal of the Operational Research Society from Palgrave Macmillan, The OR Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().