An integer linear programming model in university examination timetable scheduling: a case study at the university of Ruhuna

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.