A Model to Optimize University Course Timetable Using Graph Coloring and Integer Linear Programming

Abstract

This paper presents the design and construction of a faculty course timetable. The system uses an Integer Linear Programming model which attempts to assign groups of course units to time periods where each group is a result of a graph coloring approach. 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