A University Timetabling System Based on Graph Colouring and Constraint Manipulation

Abstract

The problem of constructing an automated system for use with timetabling is particularly well known. Many programs exist for this task, but they perform well only in particular, isolated environments. Currently being developed is a general system that will be able to cope with the ever-changing requirements of large educational institutions. This article presents a description of the methods and techniques behind such a system. Graph colouring and room allocation algorithms are presented, and ways of combining the two to provide a basis for a flexible and widely applicable timetabling system are shown. This article also describes how several common timetabling features can be handled within the system. The problems of intractability are overcome by producing a spreadsheet-type system that the user can guide in an informed and useful way. This gives the user control of the search and offers the possibility of backtracking where no reasonable solution is found, while still letting the heuristic algorithms do the hard work. Such an approach cannot guarantee an optimal solution, but it can guarantee a solution with which the user is happy. It is assumed that any user addressing a timetabling problem in a university environment has some idea of the timetable required and is qualified to judge whether a solution is suitable.