A time-predefined local search approach to exam timetabling problems
- 1 June 2004
- journal article
- research article
- Published by Informa UK Limited in IIE Transactions
- Vol. 36 (6), 509-528
- https://doi.org/10.1080/07408170490438410
Abstract
In recent years the processing speed of computers has increased dramatically. This in turn has allowed search algorithms to execute more iterations in a given amount of real-time. Does this necessarily always lead to an improvement in the quality of final solutions? This paper is devoted to the investigation of that question. We present two variants of local search where the search time can be set as an input parameter. These two approaches are: a time-predefined variant of simulated annealing and an adaptation of the “great deluge” method. We present a comprehensive series of experiments which show that these approaches significantly outperform the previous best results (in terms of solution quality) on a range of benchmark exam timetabling problems. Of course, there is a price to pay for such better results: increased execution time. We discuss the impact of this trade-off between quality and execution time. In particular we discuss issues involving the proper estimation of the algorithm's execution time and the assessment of its importance.Keywords
This publication has 20 references indexed in Scilit:
- Recent research directions in automated timetablingEuropean Journal of Operational Research, 2002
- A multistage evolutionary algorithm for the timetable problemIEEE Transactions on Evolutionary Computation, 1999
- Examination Timetabling: Algorithmic Strategies and ApplicationsJournal of the Operational Research Society, 1996
- Constraint logic programming for examination timetablingThe Journal of Logic Programming, 1996
- A General Examination Scheduling SystemInforms Journal on Applied Analytics, 1994
- New Optimization HeuristicsJournal of Computational Physics, 1993
- OR Practice—A Survey of Practical Applications of Examination Timetabling AlgorithmsOperations Research, 1986
- Future paths for integer programming and links to artificial intelligenceComputers & Operations Research, 1986
- New methods to color the vertices of a graphCommunications of the ACM, 1979
- The preparation of examination time-tables using a small-store computerThe Computer Journal, 1964