Scheduling Time Tables by Using Graph Colouring

Abstract

Creating time table is the scheduling of a set of related events in a minimal block of time such that no resource is required simultaneously by more than one event. In university time tabling, the resources involved, which we assume may be required by no more than one course at any particular time, are instructors, classrooms, and students. University timetabling is a practical application of graph colouring. We develop and describe a mathematical method for creating university timetables using techniques of graph coloring that incorporates the satisfaction of both essential and preferential timetabling conditions. The model involves creating a conflict graph from assembled university course data, properly coloring the conflict graph, and transforming this colouring into a conflict-free timetable of courses. From this timetable, one can then assign the courses to classrooms based on room capacity and availability. Once a course timetable is constructed, a conflict-free schedule of final examinations for the courses can quite easily be obtained.