A comparison of the performance of different metaheuristics on the timetabling problem.

Rossi-Doria, Olivia, Sampels, Michael, Birattari, Mauro, Chiarandini, Marco, Dorigo, Marco, Gambardella, Luca Maria, Knowles, Joshua, Manfrin, Max, Mastrolilli, Monaldo, Paechter, Ben, Paquete, Luis and Stutzle, Thomas (2003) A comparison of the performance of different metaheuristics on the timetabling problem. In: Practice and Theory of AutomatedTimetabling IV. Lecture Notes in Computer Science, 2740 . Springer-Verlag, Gent, pp. 329-351. ISBN 978-3-540-40699-0

Full text not available from this repository. (Request a copy)


The main goal of this paper is to attempt an unbiased comparison of the performance of straightforward implementations of five different metaheuristics on a university course timetabling problem. In particular, the metaheuristics under consideration are Evolutionary Algorithms, Ant Colony Optimization, Iterated Local Search, Simulated Annealing, and Tabu Search. To attempt fairness, the implementations of all the algorithms use a common solution representation, and a common neighbourhood structure or local search. The results show that no metaheuristic is best on all the timetabling instances considered. Moreover, even when instances are very similar, from the point of view of the instance generator, it is not possible to predict the best metaheuristic, even if some trends appear when focusing on particular instance classes. These results underline the difficulty of finding the best metaheuristics even for very restricted classes of timetabling problem.

Item Type: Book Section
ISBN: 978-3-540-40699-0
Electronic ISBN: 978-3-540-45157-0
Additional Information: 4th International Conference, PATAT 2002
Uncontrolled Keywords: university timetabling; evolutionary algorithms; ant colony optimization; iterated local search; simulated annealing; tabu search;
University Divisions/Research Centres: Faculty of Engineering, Computing and Creative Industries > School of Computing
Dewey Decimal Subjects: 000 Computer science, information & general works > 000 Computer science, knowledge & systems > 005 Computer programming, programs & data
Library of Congress Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Item ID: 3348
Depositing User: Computing Research
Date Deposited: 11 May 2010 11:35
Last Modified: 22 Jan 2014 14:52

Actions (login required)

View Item View Item

Edinburgh Napier University is a registered Scottish charity. Registration number SC018373