The Complexity of Timetable Construction Problems

Tim B. Cooper and Jeffrey H. Kingston

Basser Department of Computer Science
The University of Sydney 2006
Australia

3 February, 1995

Abstract

This paper shows that timetable construction is NP-complete in a number of quite different ways that arise in practice, and discusses the prospects of overcoming these problems. A formal speci?cation of the problem based on TTL, a timetable speci?cation language, is given.

1. Introduction

The timetable construction problem is to assign times, teachers, students and rooms to a collection of meetings so that none of the participants has to attend two meetings simultaneously. This basic requirement is often augmented with others concerning limits on the workload of teachers, constraints on the way a meeting's times are spread through the week, and so on.

Many different techniques have been applied to the timetable construction problem. Previous work by the authors and others has attempted to break it into subproblems, in the hope that each will be ef?ciently solvable. In such work a detailed understanding of the inherent complexity of timetable construction is needed; a broad statement that the overall problem is NP-complete gives no guidance on the prospects of solving any particular subproblem. This paper ?lls in some of these details by identifying ?ve independent NP-complete subproblems, and discussing the prospects of solving each in practice.

2. Speci?cation of the timetable construction problem

In this section we present a speci?cation of the timetable construction problem based on a timetable speci?cation language called TTL. This language is formal yet ?exible enough to specify instances encountered in practice. An earlier version of TTL appeared in [1].

A TTL instance consists of a time group, some resource groups, and some meetings. A formal grammar appears in Figure 1. Here is a typical time group: