Show simple item record

dc.contributor.advisor Dean, Nathaniel
dc.contributor.advisor Tapia, Richard A.
dc.creatorRedl, Timothy Anton
dc.date.accessioned 2009-06-04T08:38:40Z
dc.date.available 2009-06-04T08:38:40Z
dc.date.issued 2004
dc.identifier.urihttps://hdl.handle.net/1911/18687
dc.description.abstract 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.
dc.format.extent 159 p.
dc.format.mimetype application/pdf
dc.language.iso eng
dc.subjectMathematics
dc.title A study of university timetabling that blends graph coloring with the satisfaction of various essential and preferential conditions
dc.type.genre Thesis
dc.type.material Text
thesis.degree.department Mathematics
thesis.degree.discipline Natural Sciences
thesis.degree.grantor Rice University
thesis.degree.level Doctoral
thesis.degree.name Doctor of Philosophy
dc.identifier.citation Redl, Timothy Anton. "A study of university timetabling that blends graph coloring with the satisfaction of various essential and preferential conditions." (2004) Diss., Rice University. https://hdl.handle.net/1911/18687.


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record