Simulated annealing for the uncapacitated exam scheduling problem. (2016)

• Record Type: Journal Article
• Authors: Cheraitia, Meryem; Haddadi, Salim
• Is Part Of: International journal of metaheuristics. Volume 5:Number 2(2016)
• Page Start: 156
• Page End: 170
• Publication Date: 2016
• Subjects: metaheuristics -- simulated annealing -- uncapacitated exam scheduling -- graph colouring -- conflicting exams; Heuristic algorithms -- Periodicals; 006.3105
• Languages: English
• ISSNs: 1755-2176

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.