A Scatter search algorithm for exam scheduling. (c2006)

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.