Metaheuristics Network



	The Course Timetable Problem The Course Timetable Problem edited by Ben Paechter, Napier Univerity Contents About Course Timetabling Readings Links 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 timetables · Producing good timetables A 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: · We want to be able to to see more clearly what is going on in algorithms designed to solve the problem. Real data is too complicated, and real problems have too many soft and hard constraints to allow researchers to properly study the processes. · The large number of soft and hard constraints in real data (and the differences between them at different institutions) make it a long process for researchers to write code to solve them, or to adapt existing programs to be suitable. Since we want to encourage research in this area, we wanted to create a set of benchmark problems which were like real problems, but which researchers could easily work on. 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: no student attends more than one event at the same time; the room is big enough for all the attending students and satisfies all the features required by the event; only one event is in each room at any timeslot. In addition, a candidate timetable is penalised equally for each occurrence of the following soft constraint violations: a student has a class in the last slot of the day; a student has more than two classes consecutively; a student has a single class on a day. 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. Readings 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: PATAT 1995 - Selected Papers Published by Springer PATAT 1997 - Selected Papers Published by Springer PATAT 2000 - Selected Papers Published by Springer PATAT 2002 - Full Paper List (not yet published) Links The PATATwebsite The WATT website

Network Coordinator: Marco Dorigo e-mail: mdorigo@ulb.ac.be Web site responsibles: Christian Blum and Max Manfrin