Mathematical investigation of a model of the school timetabling problem

Abstract

The task of constructing school timetables - which is
a laborious one - seems an obvious problem for a computer. The
early attempts to solve this problem were simply of a ‘trial and
error' type and did not depend upon any mathematical theory.
However, it soon became evident that the problem could be formulated
in precise mathematical terms - but only at the expense of simplifying
the timetable requirements.

The development of analytical models suggests the
desirability of finding criteria which will determine, at every
stage of the construction of a timetable, whether or not it is
susceptible of being completed.

No such criteria have as yet been found, and the
problem may well prove to be insoluble in general.

In this thesis the known models have been surveyed and
have been compared with the requirements of a timetable in an actual
school. These requirements are described in detail. An attempt has
then been made to consider how the analysis of a realistic timetable
can be carried further and what kind of mathematical techniques are
applicable to the problem.

There appear to be two aspects of the problem:
i) to discover the above criteria and so enable the ‘ideal’ computer
timetabling system to be developed;
ii) to develop an efficient ‘compromise’ solution.
To facilitate the search for the required criteria we
define a mathematical structure which we have called a Latin Form.
This enables us to apply some of the language and results of
transversal theory to the problem.

A ‘compromise' procedure is described and illustrated
by reference to different parts of a school - sixth form, upper and
lower school - systematically linked.

It is further shown how the search for solutions to
some particular timetabling problems may be greatly facilitated
by the use of graph theory, transversal theory and Latin Forms.

Date of Award	1972
Original language	English