A multi-objective evolutionary algorithm for examination timetabling

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalNot applicablepeer-review

20 Scopus Citations
View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Pages (from-to)121-146
Journal / PublicationJournal of Scheduling
Volume12
Issue number2
Publication statusPublished - Apr 2009
Externally publishedYes

Abstract

This paper considers the scheduling of exams for a set of university courses. The solution to this exam timetabling problem involves the optimization of complete timetables such that there are as few occurrences of students having to take exams in consecutive periods as possible but at the same time minimizing the timetable length and satisfying hard constraints such as seating capacity and no overlapping exams. To solve such a multi-objective combinatorial optimization problem, this paper presents a multi-objective evolutionary algorithm that uses a variable-length chromosome representation and incorporates a micro-genetic algorithm and a hill-climber for local exploitation and a goal-based Pareto ranking scheme for assigning the relative strength of solutions. It also imports several features from the research on the graph coloring problem. The proposed algorithm is shown to be a more general exam timetabling problem solver in that it does not require any prior information of the timetable length to be effective. It is also tested against a few influential and recent optimization techniques and is found to be superior on four out of seven publicly available datasets. © 2008 Springer Science+Business Media, LLC.

Research Area(s)

  • Combinatorial problems, Evolutionary algorithms, Exam timetabling problem, Multi-objective optimization

Citation Format(s)

A multi-objective evolutionary algorithm for examination timetabling. / Cheong, C. Y.; Tan, K. C.; Veeravalli, B.

In: Journal of Scheduling, Vol. 12, No. 2, 04.2009, p. 121-146.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalNot applicablepeer-review