Multiple-retrieval case-based reasoning for course timetabling problems.
Saved in:
| Title: | Multiple-retrieval case-based reasoning for course timetabling problems. |
|---|---|
| Authors: | Burke, E. K.1, MacCarthy, B. L.2, Petrovic, S.1, Qu', R.1 |
| Source: | Journal of the Operational Research Society. Feb2006, Vol. 57 Issue 2, p148-162. 15p. 5 Diagrams, 5 Charts, 9 Graphs. |
| Subjects: | Case-based reasoning, Problem solving, Time perspective, Decision making, Mathematical models, Decision trees, Tree graphs, Flow charts |
| 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. [ABSTRACT FROM AUTHOR] |
| Copyright of Journal of the Operational Research Society is the property of Taylor & Francis Ltd and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
| FullText | Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 20096966 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Multiple-retrieval case-based reasoning for course timetabling problems. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Burke%2C+E%2E+K%2E%22">Burke, E. K.</searchLink><relatesTo>1</relatesTo><br /><searchLink fieldCode="AR" term="%22MacCarthy%2C+B%2E+L%2E%22">MacCarthy, B. L.</searchLink><relatesTo>2</relatesTo><br /><searchLink fieldCode="AR" term="%22Petrovic%2C+S%2E%22">Petrovic, S.</searchLink><relatesTo>1</relatesTo><br /><searchLink fieldCode="AR" term="%22Qu'%2C+R%2E%22">Qu', R.</searchLink><relatesTo>1</relatesTo> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Journal+of+the+Operational+Research+Society%22">Journal of the Operational Research Society</searchLink>. Feb2006, Vol. 57 Issue 2, p148-162. 15p. 5 Diagrams, 5 Charts, 9 Graphs. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Case-based+reasoning%22">Case-based reasoning</searchLink><br /><searchLink fieldCode="DE" term="%22Problem+solving%22">Problem solving</searchLink><br /><searchLink fieldCode="DE" term="%22Time+perspective%22">Time perspective</searchLink><br /><searchLink fieldCode="DE" term="%22Decision+making%22">Decision making</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+models%22">Mathematical models</searchLink><br /><searchLink fieldCode="DE" term="%22Decision+trees%22">Decision trees</searchLink><br /><searchLink fieldCode="DE" term="%22Tree+graphs%22">Tree graphs</searchLink><br /><searchLink fieldCode="DE" term="%22Flow+charts%22">Flow charts</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: 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. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of Journal of the Operational Research Society is the property of Taylor & Francis Ltd and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=20096966 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1057/palgrave.jors.2601970 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 15 StartPage: 148 Subjects: – SubjectFull: Case-based reasoning Type: general – SubjectFull: Problem solving Type: general – SubjectFull: Time perspective Type: general – SubjectFull: Decision making Type: general – SubjectFull: Mathematical models Type: general – SubjectFull: Decision trees Type: general – SubjectFull: Tree graphs Type: general – SubjectFull: Flow charts Type: general Titles: – TitleFull: Multiple-retrieval case-based reasoning for course timetabling problems. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Burke, E. K. – PersonEntity: Name: NameFull: MacCarthy, B. L. – PersonEntity: Name: NameFull: Petrovic, S. – PersonEntity: Name: NameFull: Qu', R. IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 02 Text: Feb2006 Type: published Y: 2006 Identifiers: – Type: issn-print Value: 01605682 Numbering: – Type: volume Value: 57 – Type: issue Value: 2 Titles: – TitleFull: Journal of the Operational Research Society Type: main |
| ResultId | 1 |
