Development of a Hybrid Tabu Search and Genetic Algorithms for the Examination Timetabling Problem

Abstract

Genetic Algorithms (GA) and Tabu Search Algorithm (TSA) are
amongst the leading research approaches for solving the
Examination Timetabling Problem (ETP), however, both algorithms
are not optimal. GA returns poor solution, uses excessive memory,
experience damage to solution during crossover while solving the
ETP. TSA consumes much time, can easily miss some regions of the
search space since it uses one solution, and may fail to generate some
neighborhood candidate solution. TSA also selects best solution
based on the current steps without taking future steps into
consideration. This research developed a hybrid of GA and TSA, the
GATS algorithm, with the aim of mitigating against the GA’s and TS
weaknesses to produce higher quality results when solving the ETP.
The ETP was modeled as an optimization problem, implemented in
Java for the three algorithms and experimented with dataset from
Bells University of Technology, Ota. The algorithms’ performances
were evaluated using first Order Conflict Counts (OCC) and second
OCC for students and invigilators respectively, as well as with space
complexity. The GA, TSA and GATSA yielded average first Order
Conflict Counts (OCC) of 0.0, 0.0 and 0.0 for both students and
invigilators. They yielded average second OCC of 5228.5, 18.8 and
0.7 for students and, 0.0, 0.0 and 0.0 for invigilators respectively.
The Developed GATSA produced higher quality timetables than TSA
and GA, and consumes similar amount of memory as the TSA and
has an empirical space complexity of O(n).