Implementation of a Tabu Search Heuristic for the Examinations Timetabling Problem
AbstractThis 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
Copyright for articles published in this journal is retained by the journal.
This journal provides immediate open access to its content on the principle that making research freely available to the public supports a greater global exchange of knowledge