RWTH Aachen University course timetabling: carpe diem!
Abstract: Increasing student numbers alongside with a growing interdependence between different curricula have led us to a point where generating university timetables by hand is now at its limit. Due to this need for technical support RWTH Aachen University decided to replace its current manual timetabling processes by a fully automated, software based scheduling system. This led to the carpe diem! Project, a cooperation between the Chair of Operations Research at RWTH Aachen University and the innoCampus Team at TU Berlin. The projects goal is to develop techniques for optimized timetabling and bring these into production at RWTH Aachen University in order to increase student satisfaction.
The old days of timetabling
- Efficient usage of available rooms and facilities
- Give students more freedom of choice among the available lectures of their curricula
- Decrease amount of inter campus travels
- Set up database and UIs to gather the relevant information about available courses, rooms, staff, curricula and additional constraints and conflicts. These were originally developed for use at TU Berlin by the innoCampus Team and are now beeing adapted for use at RWTH Aachen.
- Establishing processes at the university for using the new timetabling procedures. This includes redefining the existing administrative roles and scheduling the new necessary tasks involved.
- Educating and supporting the university staff in the new system
- Developing new algorithms and software for solving the associated university course timetabling problem.
- Expand the mathematical theory with respect to timetabling optimization.
- The university timetabling problems we encounter exhibit a lot of structure that can be exploited for efficient optimization. Gerald Lach and Marco Lübbecke have already shown that one can decompose timetabling problems into two stages using Halls Marriage theorem. We try to generalize these results to make them applicable for wider ranges of problems.
- In order to deal with changing conditions we develop a robustness concept for timetabling. Here we want to find timetables that can resist modifications of the original constraints or can be easily recovered from such.
People involved in the project (in alphabetical order):
- Martina Dahm
- Florian Dahms
- Sebastian Knoth
- Gerald Lach
- Mirjana Lach
- Marco Lübbecke
- Julia Meul
- Erhard Zorn
Byproducts from the project
In addition to optimized timetables we achieved some additional benefits:
- Before carpe diem! there did not exist a proper timeslot grid along which the courses where aligned during the course of the day. This made changes in the timetable particularly difficult and created unnecessary collisions between, e.g., just 5 minutes of two courses. With the optimization procedures we also introduced timeslots which circumvent these problems.
- Access to better curricula data was gained through the data that was collected to calculate the conflicts between courses. This curricula data now allows us to calculate estimates of how many students will be moving between which parts of the city to reach their lecture rooms. This information can be used to
- calculate how many students will be at which Mensa at which point in time. Distributing these numbers evenly over the lunch time period is one of the new goals in the optimization algorithm
- calculate which bus lines will be utilized by how many students at which time. The algorithm tries to keep the amount of inter campus travels small. Nevertheless this data helps us to find bottlenecks in the bus system. A potential cooperation with ASEAG in order to optimize these is currently being discussed.