A hybrid algorithm for the examination timetabling problem

Liam T.G. Merlot, Natashia Boland, Barry D. Hughes, Peter J. Stuckey

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

146 Citations (Scopus)

Abstract

Examination timetabling is a well-studied combinatorial optimization problem. We present a new hybrid algorithm for examination timetabling, consisting of three phases: a constraint programming phase to develop an initial solution, a simulated annealing phase to improve the quality of solution, and a hill climbing phase for further improvement. The examination timetabling problem at the University of Melbourne is introduced, and the hybrid method is proved to be superior to the current method employed by the University. Finally, the hybrid method is compared to established methods on the publicly available data sets, and found to perform well in comparison.

Original languageEnglish
Title of host publicationPractice and Theory of Automated Timetabling IV
Subtitle of host publication4th International Conference, PATAT 2002 Gent, Belgium, August 21-23, 2002 Selected Revised Papers
EditorsEdmund Burke, Patrick De Causmaecker
Place of PublicationBerlin Germany
PublisherSpringer
Pages207-231
Number of pages25
ISBN (Print)3540406999
DOIs
Publication statusPublished - 1 Dec 2003
Externally publishedYes
EventPractice and Theory of Automated Timetabling 2002 - Gent, Belgium
Duration: 21 Aug 200223 Aug 2002
Conference number: 4th

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume2740
ISSN (Print)0302-9743

Conference

ConferencePractice and Theory of Automated Timetabling 2002
Abbreviated titlePATAT 2002
Country/TerritoryBelgium
CityGent
Period21/08/0223/08/02

Cite this