Implementation of a Tabu Search Heuristic for the Examinations Timetabling Problem

Abstract

This paper reports on the design and implementation of an algorithm for the construction of an examinations timetable. The Examinations Timetabling Problem is the problem of assigning examinations and candidates to time periods and examination rooms while satisfying a set of specific constraints. Every University has a different set of constraints and structure of examinations. Generally, timetabling problems are NP-Hard and therefore very difficult to solve. However, they are of great interest due to their important practical application in educational institutions. This paper discusses a heuristic algorithm basing on the examinations timetabling at the University of Dar es salaam. The algorithm uses a Tabu Search technique, which has been successfully applied to other variations of the problem. Real life instance of the problem has been solved within reasonable time and compares with results of the previous work which used a Simulated Annealing Algorithm. It is concluded that the algorithm gives a better performance than manual system and compares well with Simulated Annealing results; Tabu Search is therefore applicable and a good approach to the problem of Examinations timetabling at UDSM.

Keywords: Timetabling, Tabu Search, Combinatorial Optimization, Scheduling

Tanz. J. Sci. Vol. 37 2011, 84-93