[Dept. of Computer Science]

Experimentation Project ACS

Title A column generation approach for examination timetabling
Student Roel Wijgers
Supervisor Han Hoogeveen
Related Course(s) Scheduling and Timetabling
Description The goal of this project was to devise an algorithm to solve the examination timetabling problem as experienced at our own faculty.
Each exam has to be assigned to one of the 10 time slots, taking into account:
  • Student availability: no student should have two exams at the same time.
  • Room availability: there are a limited number of rooms with given capacity available, and these limits should not be exceeded.
    Here we assign each exam to one room, but several exams can take place in the same room. We want to use the `big' rooms (Educ alpha etc.) as little as possible.
  • Teacher availability: an exams can be assigned to a time slot only if the teacher is available.
  • At most one exam per day. Here we want to minimize the number of students that have two exams per day.
We have developed a new algorithmic approach for the above problem, which is based on ILP and column generation.
This works very well: in a couple of seconds, we can find a solution for the problem of scheduling the exams of the Computer Science department,
such that only 6 students have two exams on one day, whereas the number of big rooms needed is minimum.
Special Note This program will be used to generate examination timetables at our department. We will publish a paper on this.