A multi-phase approach to university course timetabling
Date
2007
Authors
Zibran, Minhaz Fahim
University of Lethbridge. Faculty of Arts and Science
Journal Title
Journal ISSN
Volume Title
Publisher
Lethbridge, Alta. : University of Lethbridge, Faculty of Arts and Science, 2007
Abstract
Course timetabling is a well known constraint satisfaction optimization (CSOP) problem,
which needs to be solved in educational institutions regularly. Unfortunately, this course
timetabling problem is known to be NP-complete [7, 39].
This M.Sc. thesis presents a multi-phase approach to solve the university level course
timetabling problem. We decompose the problem into several sub-problems with reduced
complexity, which are solved in separate phases. In phase-1a we assign lectures to professors,
phase-1b assigns labs and tutorials to academic assistances and graduate assistants.
Phase-2 assigns each lecture to one of the two day-sequences (Monday-Wednesday-Friday
or Tuesday-Thursday). In Phase-3, lectures of each single day-sequence are then assigned
to time-slots. Finally, in phase-4, labs and tutorials are assigned to days and time-slots.
This decomposition allows the use of different techniques as appropriate to solve different
phases. Currently different phases are solved using constraint programming and integer
linear programming. The multi-phase architecture with the graphical user interface allows
users to customize constraints as well as to generate new solutions that may incorporate
partial solutions from previously generated feasible solutions.
Description
ix, 117 leaves ; 29 cm
Keywords
Constraint programming (Computer Science) , Computer scheduling , Scheduling -- Computer programs , Dissertations, Academic