Final exams scheduling for univeristies. (c2001)

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.