Abstract:
Scheduling final exams for large numbers of courses and students in
universities, such as the Lebanese American University (LAU), is an intractable
problem. In order to solve this problem, the approach must be efficient, flexible and
adaptable. Conflicts occur when multiple exams are scheduled for the same student at
the same period (simultaneously), and unfairness to a student refers to consecutive
exams (two exams directly after each other) or more than two exams on the same day
(referred to as mUltiples). A good exam schedule would aim for minimizing conflicts
and the two unfairness factors based on user-assigned weights associated to these
three factors and subject them to some constraints. Likewise, since a limited number
of rooms are available in each exam period, an additional constraint concerned with
room violations is added to achieve the goal of minimizing room violations. All
constraints may be violated if necessary, since it is almost impossible in real world situations to find a solution without violating any constraint. In this work, we first formulate the problem as a modified weighted-graph
coloring problem and adapt two natural optimization algorithms: Simulated
Annealing and Genetic Algorithm; in addition to a clustering based algorithm (FESP),
and a hybrid of natural optimization and clustering based algorithms (FESPSA) for
solving the exam scheduling problem taking into account the specific objectives and
constraints of LAD. Then, we compare these algorithms with each other as well as
with the manual procedure done by the registrar's office. The comparison is done
using realistic data taken from LAU for six semesters. Our experimental results show that simulated annealing gives better exam
schedules than genetic algorithms, FESPSA, FESP and manual scheduling. All
algorithms were run on different exam days ranging from five to ten. Simulated
Annealing stayed to show the best results in all semesters in all days variations.
Moreover, Simulated Annealing shares with the Genetic Algorithm more flexibility to
accommodate various user constraints. On the other hand, FESPSA showed better
results in terms of conflicts and unfairness factors among all exam days when
compared with FESP. Moreover, FESPSA also proved to be better than FESP when dealing with room violations. That is, FESPSA minimized the number room
violations much better than FESP.
