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:
REFERENCES:
A similar project
COURSE PREREQUISITES: Genetic Algorithms
EQUIPMENT: Sun or PC, using software available in the department