Multiple-Retrieval Case-Based Reasoning for Course Timetabling Problems

TitleMultiple-Retrieval Case-Based Reasoning for Course Timetabling Problems
Publication TypeJournal Article
Year of Publication2006
AuthorsBurke EK, MacCarthy BL, Petrovic S, Qu R
JournalJournal of the Operational Research Society
Start Page148
Date Published02/2006
ISSN0160-5682(Print) 1476-9360(Online)
Keywordstimetabling case-based reasoning (CBR) attribute graph tabu search simulated annealing

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.