A Program for Constructing High School Timetables

Tim B. Cooper and Jeffrey H. Kingston

Basser Department of Computer Science
The University of Sydney 2006
Australia

6 March, 1995

Abstract

This paper describes TT2, a computer program for high school timetable construction. The program is a combination of tree search and techniques from operations research (matchings and ?ows). Two instances taken without simpli?cation from real high schools have been solved.

Keywords: timetable construction, speci?cation, implementation, operations research.

Contact: Dr. Jeffrey H. Kingston, email [email protected].

1. Introduction

The high school timetable construction problem is to assign times, teachers, students, and rooms to a collection of meetings so that none of the participants is required to attend two meetings simultaneously. This basic requirement is often accompanied by others, such as that the times of a meeting should be spread evenly through the week, and so on. The problem is well known to be NP-hard [4].

This paper describes the speci?cation language that we use for describing real instances of the timetabling problem, our current high school timetable construction program (which we call TT2), and the results we have obtained with it. Our approach may be characterized roughly as tree search, with move generation and pruning rules based on techniques adapted from operations research.

Many approaches have been tried, and the reader is referred to the annotated bibliography of Schmidt and Str?hlein [7] and the more recent bibliographies available on the Internet, such as [1]. We can mention here only work directly related to our own.

The ?rst application of operations research techniques to timetable construction seems to have been by Csima [3], who was able to solve a special case in polynomial time. His methods were championed by Lions [5, 6]. The work of de Werra [8, 9] contains several network models, one of which has found its way into our work. Our search techniques, primarily beam search, are standard in the arti?cial intelligence literature [10].

2. Speci?cation

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