Tabu Search with Explicit Adaptive Guiding Heuristic for the Examination Timetabling Problem

Abstract

Tabu Search algorithm (TS) is one of the leading methods for solving
the Examination Timetabling Problem (ETP). The challenge with TS
which uses only one solution in searching is that it can easily miss
some areas of the search space and chose the best solution based on
the current search step and position without taking the future steps
into consideration. To address these problems, an explicit and
adaptive guiding heuristic was proposed for the standard TS
algorithm with the goal of enhancing its performance. The standard
TS and the TS with the explicit adaptive guiding mechanism, the TS_G
algorithm were implement using the Java programing language
(version 8.92) with the MySQL database and experimented with data
from Bells University of Technology, Ota. Performance of the two
algorithms were evaluated using first Order Conflict Counts (OCC),
Second OCC and third OCC for students and invigilators respectively,
in addition to memory consumption. The TS and TS_G yielded an
average first OCC 0.0 and 0.0 students and 0.0 and 0.0 for
invigilators. Similarly, TS and TS_G yielded average second OCC of
18.8 and 10.5 for students and, 0.0 and 0.0 for invigilators
respectively. Furthermore, TS and TS_G yielded average third OCC
of 33375.0 and 9922.1 for students and 0.0 and 0.0 for invigilators,
respectively. The TS_G algorithm outperformed the standard TS
algorithm with lower conflicts violations. Both algorithms however
recorded similar memory consumption