A hybrid algorithm for the examination timetabling problem

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

doi:10.1007/978-3-540-45157-0_14

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 proceeding › Conference Paper › Research › peer-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 language	English
Title of host publication	Practice and Theory of Automated Timetabling IV
Subtitle of host publication	4th International Conference, PATAT 2002 Gent, Belgium, August 21-23, 2002 Selected Revised Papers
Editors	Edmund Burke, Patrick De Causmaecker
Place of Publication	Berlin Germany
Publisher	Springer
Pages	207-231
Number of pages	25
ISBN (Print)	3540406999
DOIs	https://doi.org/10.1007/978-3-540-45157-0_14
Publication status	Published - 1 Dec 2003
Externally published	Yes
Event	Practice and Theory of Automated Timetabling 2002 - Gent, Belgium Duration: 21 Aug 2002 → 23 Aug 2002 Conference number: 4th

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	2740
ISSN (Print)	0302-9743

Conference

Conference	Practice and Theory of Automated Timetabling 2002
Abbreviated title	PATAT 2002
Country/Territory	Belgium
City	Gent
Period	21/08/02 → 23/08/02

Access to Document

10.1007/978-3-540-45157-0_14

Cite this

Merlot, L. T. G., Boland, N., Hughes, B. D., & Stuckey, P. J. (2003). A hybrid algorithm for the examination timetabling problem. In E. Burke, & P. De Causmaecker (Eds.), Practice and Theory of Automated Timetabling IV: 4th International Conference, PATAT 2002 Gent, Belgium, August 21-23, 2002 Selected Revised Papers (pp. 207-231). (Lecture Notes in Computer Science; Vol. 2740). Springer. https://doi.org/10.1007/978-3-540-45157-0_14

Merlot, Liam T.G. ; Boland, Natashia ; Hughes, Barry D. et al. / A hybrid algorithm for the examination timetabling problem. Practice and Theory of Automated Timetabling IV: 4th International Conference, PATAT 2002 Gent, Belgium, August 21-23, 2002 Selected Revised Papers. editor / Edmund Burke ; Patrick De Causmaecker. Berlin Germany : Springer, 2003. pp. 207-231 (Lecture Notes in Computer Science).

@inproceedings{0c73d037b9c241688ca5e4a6cfce2e04,

title = "A hybrid algorithm for the examination timetabling problem",

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.",

author = "Merlot, {Liam T.G.} and Natashia Boland and Hughes, {Barry D.} and Stuckey, {Peter J.}",

year = "2003",

month = dec,

day = "1",

doi = "10.1007/978-3-540-45157-0_14",

language = "English",

isbn = "3540406999",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "207--231",

editor = "Edmund Burke and {De Causmaecker}, Patrick",

booktitle = "Practice and Theory of Automated Timetabling IV",

note = "Practice and Theory of Automated Timetabling 2002, PATAT 2002 ; Conference date: 21-08-2002 Through 23-08-2002",

}

Merlot, LTG, Boland, N, Hughes, BD & Stuckey, PJ 2003, A hybrid algorithm for the examination timetabling problem. in E Burke & P De Causmaecker (eds), Practice and Theory of Automated Timetabling IV: 4th International Conference, PATAT 2002 Gent, Belgium, August 21-23, 2002 Selected Revised Papers. Lecture Notes in Computer Science, vol. 2740, Springer, Berlin Germany, pp. 207-231, Practice and Theory of Automated Timetabling 2002, Gent, Belgium, 21/08/02. https://doi.org/10.1007/978-3-540-45157-0_14

A hybrid algorithm for the examination timetabling problem. / Merlot, Liam T.G.; Boland, Natashia; Hughes, Barry D. et al.
Practice and Theory of Automated Timetabling IV: 4th International Conference, PATAT 2002 Gent, Belgium, August 21-23, 2002 Selected Revised Papers. ed. / Edmund Burke; Patrick De Causmaecker. Berlin Germany: Springer, 2003. p. 207-231 (Lecture Notes in Computer Science; Vol. 2740).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - A hybrid algorithm for the examination timetabling problem

AU - Merlot, Liam T.G.

AU - Boland, Natashia

AU - Hughes, Barry D.

AU - Stuckey, Peter J.

N1 - Conference code: 4th

PY - 2003/12/1

Y1 - 2003/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=35248816571&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-45157-0_14

DO - 10.1007/978-3-540-45157-0_14

M3 - Conference Paper

AN - SCOPUS:35248816571

SN - 3540406999

T3 - Lecture Notes in Computer Science

SP - 207

EP - 231

BT - Practice and Theory of Automated Timetabling IV

A2 - Burke, Edmund

A2 - De Causmaecker, Patrick

PB - Springer

CY - Berlin Germany

T2 - Practice and Theory of Automated Timetabling 2002

Y2 - 21 August 2002 through 23 August 2002

ER -

Merlot LTG, Boland N, Hughes BD, Stuckey PJ. A hybrid algorithm for the examination timetabling problem. In Burke E, De Causmaecker P, editors, Practice and Theory of Automated Timetabling IV: 4th International Conference, PATAT 2002 Gent, Belgium, August 21-23, 2002 Selected Revised Papers. Berlin Germany: Springer. 2003. p. 207-231. (Lecture Notes in Computer Science). doi: 10.1007/978-3-540-45157-0_14

A hybrid algorithm for the examination timetabling problem

Abstract

Publication series

Conference

Access to Document

Other files and links

Cite this