The Course Timetable Problem
About Course Timetabling
Timetabling the classes of a University involves assigning timeslots to a number of classes or similar events. In doing this there are two goals:
· Producing feasible timetablesA feasible timetable is one in which all the events can have all of the resources they require at the timeslot that has been allocated to them. These resources might be rooms (possibly with particular equipment), student groups (a group of students is defined as one or more students who share the same timetable), and lecturers.
A good timetable is one that conforms well to a number of criteria set by the user. These criteria might be things like “students should not have more than three lectures in a row”, or “lecturers should have one day a week free of teaching”.
We can also think of the problem in terms of constraints. A hard constraint is one that if broken would make the timetable infeasible. A soft constraint is one that if broken would make the timetable less good.
The course timetable problem might include the assignment of rooms, student groups and lecturers to events.
Course Timetabling for the Metaheuristics Network
The problem we are studying in the Metaheuristics project is one that is closely based on real world problems, but simplified. We are not entirely happy about using a simplified problem, but the reasons are two-fold:
The problem we consider has events, students, and rooms. Students attend events, and events take place in rooms. Rooms can have a number of features (e.g. computers, wheelchair access), and events can require these features. Room also have a capacity.
The weekly timetable to be created has 45 timeslots split into 5 days of 9 timeslots each. The events have to be placed into timeslots and rooms so that:
A public competition with this problem has been organised, ending in March 2003. The competition web-site has more details about the problem, example problem instances, and solutions checking software.
A good place to start reading about the course timetabling problem and variuos solution methods is in the Proceeding of the PATAT series of conferences:
|Network Coordinator: Marco Dorigo e-mail: email@example.com Web site responsibles: Christian Blum and Max Manfrin|