Abstract:
Scheduling final exams for large numbers of
courses and students in universities is an intractable
problem. Where scheduling is done manually, conflicts
and unfairness are inevitable. Conflicts occur when
simultaneous exams are scheduled for the same student,
and unfairness 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
unfairness factors based on user-assigned weights to
these three factors and subject to some constraints such
as classrooms’ number and capacities. In this work, we
use a modified weighted-graph coloring problem
formulation and adapt two stochastic search algorithms
for solving the problem. The two algorithms are a
simulated annealing algorithm (SA) and a genetic
algorithm (GA). We also propose an improvement to a
‘good’ clustering-based heuristic procedure, known as
FESP, by using simulated annealing procedures. The
improved heuristic is referred to as FESP-SA. Then, we
empirically compare the three proposed algorithms and
FESP using realistic data. Our experimental results
show that SA and GA produce good exam schedules that
are better than those of FESP heuristic procedure. Also,
SA and GA allow a reduction in the number of exam
days without much aggravating conflicts and unfairness.
However, SA is more favorable since it is faster than GA.
Citation:
Mansour, N., & Timani, M. (2007). Stochastic search algorithms for exam scheduling. Int J Comput Intell Res, 3(4), 353-361.
