The combinatorics of timetabling

Various formulations of timetabling problems are given in terms of coloring problems in graphs. We consider a collection of simple class–teacher timetabling problems and review complexity issues for these formulations. This tutorial presentation (which is not claimed to be an exhaustive review nor a research contribution) includes a brief sketch of a tabu search procedure which handles many specific requirements and provides an efficient heuristic technique.