Time-tables, polyhedra and the greedy algorithm Original Research Article

We study the facial structure of polyhedra associated with the classical class-teacher time-table problem. After the presentation of some first results we introduce the class of partition inequalities and show that they are facet-defining for the general, monotone time-table polyhedron. Then we show that for two classes, two teachers and an arbitrary number of time periods, the time-table problem can be solved by the greedy algorithm. A polyhedral description for the associated monotone polytope is given based on nonnegativity, assignment and partition inequalities. The completeness of the linear system is established via the concept of total dual integrality. Finally, we conclude with some open questions and related problems.