Optimized scheduling of academic timetables : a mathematical approach

Abstract

Timetabling problem is a well-known problem commonly addressed by the researches over the decades using different techniques. With the advancement of the technology, the research direction has been narrowed to automate timetabling. Graph theoretic approach, linear programming, neural networks and artificial intelligence techniques have been used in literature. This study focuses on university course timetabling problem, which intends to model the semester timetable of the Faculty of Applied Sciences at University of Sri Jayewardenepura, which currently does not possess an automated timetabling system. It has been used an Integer Linear Programming model which attempts to assign group of course units to a time period where each group is a result of a graph coloring approach. A greedy algorithm has been used to color the vertices of the graph by the use of mathematical software. The variables in the model have defined to be binary integer variables. Branch and bound method has been used as the solution technique for the integer linear program. With the large number of variables and constraints the solution technique required large number of iterations. Hence a mathematical software has been used to implement the branch and bound method. Limited number of lecture halls, large number of subject combinations and growing number of student registration have made the problem very tight which results thousands of variables and constraints to the model. The quality of the solution depends on the location of the time period assigned to the set of course units. Hence the objective function is defined to optimize the allocation of time periods to course units. The model results a feasible solution which has reduced the maximum idle time of students to three hours and it can be implemented with the lecture halls currently available in the faculty of Applied Sciences, University of Sri Jayewardenepura. The model is flexible and allows to change the constraints depending on the faculty requirements and other factors, and if necessary, construct alternative schedules.