Mathematics underlying the university timetable
by
Kevin Broughan
University of Waikato
Coauthors: Nan Zhu

The existing university timetable gives rise to a range of complaints from staff and students. The programme used at Waikato takes just a few minutes to run, so does little to resolve constraints or move towards an optimal result. There are standard approaches to this problem described in the literature [1], some old and some new. The problem in highly simplified forms is NP complete, so is intrinsically difficult, and should be avoided of course. For the department chairperson however, it becomes one of the principal tools to improve participation and success with mathematics, being a subject a the heart of the university, and therefore deeply impacted by a clash rich timetable structure.

In this presentation the mathematics underlying the problem will be surveyed and the approach being adopted described. It will include a breakdown into clashible sets of courses, slot assignments and then room assignments. Recent work on the colouring of large random graphs [2], and approaches using simulated annealing have been found to be of little use, but older simpler methods, and long periods of CPU time, beneficial, according to preliminary experiments.

[1] de Werra, D. "An introduction to timetabling", European Journal of Operations Research, 19 (1985), p151-162.

[2] McDiarmid, C. "On the chromatic number of random graphs", Random Structures and Algorithms, 1 (1990), p435-442.

Date received: June 12, 1998