A tabu-based large neighbourhood search methodology for the capacitated examination timetabling problem

S. Abdullah, S. Ahmadi, E. K. Burke, M. Dror, B. McCollum

Research output: Contribution to journalArticlepeer-review

46 Scopus citations

Abstract

Neighbourhood search algorithms are often the most effective known approaches for solving partitioning problems. In this paper, we consider the capacitated examination timetabling problem as a partitioning problem and present an examination timetabling methodology that is based upon the large neighbourhood search algorithm that was originally developed by Ahuja and Orlin. It is based on searching a very large neighbourhood of solutions using graph theoretical algorithms implemented on a so-called improvement graph. In this paper, we present a tabu-based large neighbourhood search, in which the improvement moves are kept in a tabu list for a certain number of iterations. We have drawn upon Ahuja-Orlin's methodology incorporated with tabu lists and have developed an effective examination timetabling solution scheme which we evaluated on capacitated problem benchmark data sets from the literature. The capacitated problem includes the consideration of room capacities and, as such, represents an issue that is of particular importance in real-world situations. We compare our approach against other methodologies that have appeared in the literature over recent years. Our computational experiments indicate that the approach we describe produces the best known results on a number of these benchmark problems.

Original languageEnglish (US)
Pages (from-to)1494-1502
Number of pages9
JournalJournal of the Operational Research Society
Volume58
Issue number11
DOIs
StatePublished - Nov 2007

Keywords

  • Examination timetabling
  • Improvement graph
  • Large neighbourhood
  • Tabu search

ASJC Scopus subject areas

  • Modeling and Simulation
  • Strategy and Management
  • Statistics, Probability and Uncertainty
  • Management Science and Operations Research

Fingerprint

Dive into the research topics of 'A tabu-based large neighbourhood search methodology for the capacitated examination timetabling problem'. Together they form a unique fingerprint.

Cite this