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.