Exam scheduling algorithms. (c1999)

Abstract

Scheduling final exams for large numbers of courses and students in liberal arts universities, such as the Lebanese American University (LAU), is an intractable problem. When 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 at LAU would aim for minimizing conflicts and the two unfairness factors based on user assigned weights to these three factors and subject to some constraints. This report presents the implementation of a Final Exam Scheduling Package (FESP) at L.A.U. FESP distributes the final exams among the exam sessions and assigns exams to classrooms. It aims for minimizing student conflicts such as students with simultaneous exams, consecutive exams and more than two exams per day. It also allows sharing classrooms among exams. This work also includes an improved natural optimization algorithm for exam scheduling, the Genetic Algorithm (GA). The problem is first formulated as a modified weighted-graph-coloring problem. Then the genetic algorithm is adapted for solving the exam scheduling problem taking into account the specific objectives and constraints of LAU. Then, we compare the results of the two algorithms and with a manual procedure. The experimental results obtained on real-life data show that FESP yields a substantial decrease in the number of exam conflicts in comparison with those obtained by the GA and the manually prepared exam schedule.