Three-phase simulated annealing algorithms for exam scheduling

Abstract

Scheduling of final exam usually results in conflicts and inconvenience. Conflicts occur when simultaneous exams are scheduled for the same student, and inconvenience to a student refers to consecutive exams or more than two exams on the same day. A good exam schedule should aim to minimize conflicts and the two inconvenience factors based on weight that are user-assigned to these three factors and subject to some constraints such as the number and capacities of classrooms. Scheduling final exams for large numbers of courses and students in universities is an intractable problem. In this work, we decompose the problem into three phases and propose simulated annealing algo$hms for these phases. Hence, we refer to our solution methods as 3-phase simulated annealing (3PSA). We empirically compare 3PSA with a 4-phase clustering-based heuristic algorithm using realistic data. Our experimental results show that 3PSA produces good exam schedules, which are better than those of the clustering heuristic procedure.