Abstract:
At universities where students enjoy flexibility in selecting courses, the Registrar's
office aims to generate an appropriate exam schedule for numerous courses and large
number of students. An appropriate exam schedule should show fairness towards all
students, respecting criteria and constraints: (a) eliminating or minimize the number
of simultaneous exams; (b) minimize the number of consecutive exams; (c) minimize
the number of multiple exams a student has per day; (d) exams should fit in rooms
with predefined capacity; and (e) the number of exam periods is limited. These
constraints are conflicting in nature. Hence, finding an optimal solution is challenging
and the problem of exam scheduling is an NP-complete problem. Solving this
problem in a reasonable amount of time requires the use of heuristic approaches. A
good heuristic algorithm should aim to minimize the above mentioned constraints. In this work, we develop an evolutionary algorithm based on the scatter search
approach for finding good suboptimal solutions for exam scheduling. This approach is
based on maintaining a population of solutions for the purpose of generating new trial
solutions. We perform experimental evaluation of our suggested algorithm on real
data and compare our results with the registrar's manual schedule in addition to other
optimization heuristic algorithms: Simulated Annealing, Genetic Algorithm, Three
Phase Simulated Annealing (3PSA); a clustering based algorithm (FESP), and a
hybrid algorithm (FESPSA).Our experimental results show that our adapted scatter
search algorithm generated results that are better than FESP, 3PSA, FESPSA
algorithms and the registrar's manual schedule, and it is comparable with the results
generated by GA and SA.
