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.
International Journal of Metaheuristics, 2016 Vol.5 No.2, pp.156 - 170
Received: 07 Apr 2016
Accepted: 08 Sep 2016
Published online: 06 Nov 2016 *