Using tabu search with longer-term memory and relaxation to create examination timetables

Several methods have been developed over the past four decades for producing examination timetables in educational institutions. This has turned out to be a difficult problem for which even elementary instances have a NP-hard complexity. This paper describes a tabu search based algorithm called OTTABU that creates examination timetables that have an heuristically minimized penalty function or discomfort level. This algorithm incorporates two tabu lists, a tabu relaxation policy and several other novel features. The algorithm has been executed with 12 publicly available sets of data and the results obtained are compared with similar results from five other published algorithms that use the same penalty function. It has been found that OTTABU compares favourably with these other algorithms when presented with the same data. (C) 2003 Elsevier B.V. All rights reserved.