Automatic Timetabling

Timetabling for this department is very tedious and currently performed with the minimum of computer assistance. In particular, the existing system makes no attempt to help with the creation of the timetable, but only checks for clashes in the timetable, which must be created entirely by hand.

This situation exists mainly because the general timetabling problem is NP, and we have hundreds of activities to schedule. Although faster algorithms exist, they rely on attaching priorities and/or preferred times to each activity, and on the timetable not being full, so that little searching is necessary to place each activity. However, the departmental timetable is over-full, and we are trying to minimise the number of clashes while making best use of the resources available.

As a search through all possible combinations is apparently necessary, but not possible in any reasonable amount of time, maybe we can use an approximation to an exhaustive search, such as a Genetic Algorithm (GA). Some success has been reported using a GA to timetable exams.

This project will consist of locating a public-domain GA package which can be customised to our particular problem. This customisation will be a significant job - I would expect that a simple GA, with a gene consisting of (randomised) times and places for each activity, will have great difficulty generating plausible timetables. Instead, we could try e.g. a gene that (randomly) orders the activities, and then place each in turn in the next available timetable slot. We could even incorporate some further heuristics, such as initially sorting the activities by the number of students attending them, or some other measure of the likely difficulty of placing the activity.

There are several complications, such as:

If this is successful, we might add further soft criteria, such as minimising the number of 9am lectures, or minimising the number of days each individual lecturer is lecturing, etc.


REFERENCES: A similar project
COURSE PREREQUISITES: Genetic Algorithms
EQUIPMENT: Sun or PC, using software available in the department