Investigations of the longer term memory, relaxation and restructure in the tabu search heuristic optimization of examination timetables.

Abstract

The examination scheduling problem is a difficult problem with NP-hard complexity and several methods for heuristically solving it have been developed over the past decades. This thesis investigates the casting of examination timetables with tabu search techniques, the combination of the move or transition recency based short-term memory and move frequency based longer-term memory and several tabu search variations such as solution restructuring, tabu relaxation, and alternating neighborhoods. By integrating the tabu techniques mentioned above, a multi-phase system OTTASYS has been implemented and tested on several sets of real data. It is shown here that the quality of the solutions obtained compare favourably with other published algorithms when presented with the same data. As the engine of the system, the algorithm OTTABU is proven powerful and productive and also can be used as a platform for further research.