Models and methods for school timetabling using a column generation approach

Sammanfattning: Creating timetables for educational institutions is a complex task, and the quality of the timetables affects a large number of students and teachers. This process involves assigning teachers to courses, students to classes, classrooms to lessons and setting the starting time of the lessons.In this thesis, models and solution methods are presented for the assignment of starting times and classrooms as appearing in Swedish schools. This school system has two aspects that make timetabling particularly hard. The first is the mix of both individual and class based timetables, and the second that lessons can have any length unlike many other school systems which only has lessons of the same length. For the timetables to be of practical interest, modelling of quality aspects of a timetable is also a major issue.A first generalised set-packing model is presented for the problem, with a column representing a feasible schedule for one class. Solution techniques involving column generation and constraint branching are developed and presented. This model is deemed too complex to solve, and a sequential solution approach that solves the problem in several stages is presented. The models and solution techniques in the sequential solution approach also involve column generation and constraint branching. The models allow for a capturing many quality aspects of a timetable. The sequential solution approach is tested on a test database, and the results are presented and discussed. A study of improving the performance of the branch-andbound method is finally presented.