A study of university timetabling that blends graph coloring with the satisfaction of various essential and preferential conditions

[摘要] Constructing a satisfactory conflict-free semester-long timetable of courses and creating a similarly satisfactory conflict-free timetable for end-of-semester final examinations are two closely related and often difficult problems that colleges and universities face each semester. We discuss the relevance of such timetabling problems as a natural and practical application of graph coloring, and develop a mathematical and computational model for solving university timetabling problems using techniques of graph coloring that incorporates the satisfaction of both ;;essential;; timetabling conditions (i.e., conditions or constraints that must be satisfied in order to produce a legal or feasible timetable) as well as suggested ;;preferential;; timetabling conditions (i.e., additional conditions or constraints that need not necessarily be satisfied to produce a legal or legitimate timetable, but if satisfied may very well produce a more ;;acceptable;; timetable for students and/or faculty members). We discuss in detail the step-by-step process that is taken to implement our timetabling-by-graph-coloring procedure, from the assembling of university course data, to creating a course conflict graph based on the assembled data, to coloring the conflict graph, to transforming this coloring to a conflict-free timetable, to finally assigning courses to classrooms. Once a conflict-free timetable of courses has been constructed, we present ways in which such a course timetable for a particular semester can be used to construct a conflict-free timetable of final examinations. Our model also considers a number of sociological scheduling concerns and preferences addressed by university registrars, faculty, staff, and students. Computational results, obtained by the author using actual data provided by Rice University and the University of St. Thomas, are documented.

[发布机构] Rice University