Timetabling to Please Most of the Staff Most of the Time

Funding:
New Technologies Initiative
Joint Information Systems Committee of the UK HEFCs
Duration: 1994-1997
Objectives:
The main aim of the project is to develop a system for the timetabling of both university exams and courses which is capable of generating high quality solutions despite the increased difficulties of modularisation.

Introduction

Despite advances in technology, and the development of increasingly efficient timetabling algorithms, very few academic institutions have fully automated their timetabling process to date[1]. We are applying and developing the latest artificial intelligence techniques, including genetic algorithms, to produce a useful, interactive, state-of-the-art university timetabling system.

This system incorporates an evolutionary timetabling algorithm developed at Nottingham, and a highly flexible method of specifying resource and constraint information, making it applicable to a wide range of academic timetabling problems.

Resource Specification

Timetabling deals with meetings and resources (students, rooms and equipment), but the data required by the timetabling process for each of these entities varies widely. Hence, for each meeting or type of resource, the ASAP timetabling system allows the timetabler to specify an arbitrary number of attributes of various types. For simplicity, the following description talks about resources, but meetings may be defined and grouped in the same way.

Each type of resource, eg rooms, has a set of attributes which are used to define individual resources. For example, rooms may have the following four attributes:
Attribute name Attribute values
Wheelchair access true iff the room is accessible by wheelchair
Purposes the uses the room may be put to, eg lecture theatre, computer lab, etc
Building the building in which the room is situated
Capacity the number of students which the room can contain
Every room would possess values for each of these attributes.

There are four different types of attribute, which are represented by the four room attributes in the above example:
Attribute type Example Values
Simple Wheelchair access true or false
List Purposes any number of items from a list of possible values
Exclusive Building exactly one item from a list of possible values
Number Capacity a positive integer
The timetabler may add, modify or remove attributes of any type in order to alter the information held about resources of any particular type.

All of the resources of a particular type which have the value true for a particular Simple attribute make up a set; for example, the set of rooms which have wheelchair access. Furthermore, each of the possible values for a List or Exclusive attribute can also be viewed as a set - the set of resources which take that value for that attribute; for example, the set of rooms which belong to the Tower Building.

The timetabler has two ways of viewing and manipulating resource data:

Constraints

Constraints of various types may be specified, in order to direct the automated scheduler. The constraints may be weighted using individual priority values, and some constraints may be "hard", or inviolable.

The most common form of constraint is the assignment constraint, which links two lists of resources or meetings. For example, once the timetabler has created an attribute to specify whether a room has wheelchair access, and an attribute to specify whether a person uses a wheelchair, one hard assignment constraint can ensure that people who are wheelchair-bound will not be required to attend meetings in rooms which do not have wheelchair access.

Timetabling

The ASAP timetabling system incorporates an evolutionary scheduling algorithm developed at the University of Nottingham[2-4]. This algorithm develops a "population" of timetables simultaneously, thus offering the user a choice of solutions. The algorithm is guided by the timetabler's constraints.

In addition, the timetabler may manually alter timetables with ease - placing meetings, and assigning resources in order to fine-tune the automatically generated solutions.

Conclusion

The ASAP timetabling system offers a highly flexible problem specification, and should thus be applicable to a wide range of timetabling problems.

References

  1. EK Burke, DG Elliman, PH Ford and RF Weare, "Exam Timetabling in British Universities - A Survey", the Practice and Theory of Automated Timetabling, eds EK Burke and P Ross, Springer-Verlag (Lecture Notes in Computer Science), 1996.
  2. EK Burke, DG Elliman, and RF Weare, "The Automation of the Timetabling Process in Higher Education", Journal of Educational Technology Systems, vol 23, no 4, pp 257-266, Baywood Publishing Company, 1995.
  3. EK Burke, DG Elliman, and RF Weare, "A Hybrid Genetic Algorithm for Highly Constrained Timetabling Problems", proceedings of the 6th International Conference on Genetic Algorithms (ICGA'95, Pittsburgh, USA, 15th-19th July 1995), Morgan Kaufmann, San Francisco, CA, USA.
  4. EK Burke, DG Elliman, and RF Weare, "The Automated Timetabling of University Exams using a Hybrid Genetic Algorithm", proceedings of the AISB (Artificial Intelligence and Simulation of Behaviour) Workshop on Evolutionary Computing (University of Sheffield, UK, 3rd-7th April 1995), pp. 75-85, Springer-Verlag, 1995.

Information

The following UK universities are acting as pilot sites for the first version of the system:

For more information, please contact Dr E.K. Burke

ASAP Homepage