Title: Simulated annealing for the uncapacitated exam scheduling problem

Authors: Meryem Cheraitia; Salim Haddadi

Addresses: LabSTIC, 8 Mai 1945 University, Guelma, Algeria ' LabSTIC, 8 Mai 1945 University, Guelma, Algeria

Abstract: The uncapacitated exam scheduling problem asks for a conflict-free assignment of a set of given exams into a limited number of time slots such that conflicting exams are spread as evenly as possible. In our proposed approach, using a simple graph colouring heuristic, we construct a feasible timetable to start with. Simulated Annealing is then used as an iterative heuristic for improving the spreading of the conflicting exams. Our results on the Toronto benchmark data set show that our approach provides good results and turns out competitive with 10 recent existing methods.

Keywords: metaheuristics; simulated annealing; uncapacitated exam scheduling; graph colouring; conflicting exams.

DOI: 10.1504/IJMHEUR.2016.080266

International Journal of Metaheuristics, 2016 Vol.5 No.2, pp.156 - 170

Received: 07 Apr 2016
Accepted: 08 Sep 2016
Published online: 09 Nov 2016 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article