Implementation of a Tabu Search Heuristic for the Examinations Timetabling Problem
Loading...
Date
2011
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Tanzania Journal of Science
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.
Description
Keywords
Timetabling, Tabu Search, Combinatorial Optimization, Scheduling