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

Abstract

Attached

This paper presents the design and construction o f a faculty course timetable. The system uses an Integer Linear Programming model which attempts to assign groups o f course units to time periods where each group is a result o f a graph coloring approach. Limited number o f lecture halls, large number o f subject combinations and growing number o f student registration have made the problem very tight which results thousands o f variables and constraints to the m odel The quality o f the solution depends on the local ion o f the time period assigned to the set o f course units. Hence the objective function is defined to optimize the allocation o f time periods to course units. The model results a feasible solution which has reduced the maximum idle time oj students to three hours and it can be implemented with the lecture halls currently available in the faculty o f Applied Sciences, University o f 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.