Abstract:
In this study, a two-phase procedure that consists of integer linear
programming models is developed for a case study in the university
examination timetabling problem. Educational timetable scheduling problems
are difficult NP-Hard combinatorial optimization problems. Because of the
complexity and practical importance, the examination timetable scheduling
problem is prominent among other scheduling problems. Examination
timetabling is the process of assigning examinations to time slots, and halls
while satisfying a given number of constraints and achieving certain
objectives. The students, as well as the staff, surely benefit from the wellplanned
examination timetabling. Since the examination timetabling problem
is a computationally expensive optimization problem, we propose a two-phase
procedure for constructing examination timetabling. In the first phase, we
constructed an integer linear programming model to assign halls to each
examination considering the hall clashes, halls, and exam capacities to
minimize the unnecessary space assigned while maximizing hall preference.
In the second phase, another integer linear programming problem is obtained
to assign each examination to time slots considering several hard and soft
constraints and the objective of minimizing the length of examination for each
student group and assigning examinations with a large number of students at
the beginning. The proposed two-phase procedure is applied to the
examination timetabling scheduling of the level I, semester II examination of
the faculty of science, the University of Ruhuna as a case study. Better feasible
solutions are obtained for each integer linear programming problem by
applying the branch and bound algorithm implemented in MATLAB.
