Decomposing the High School Timetable Problem

The process of timetable construction is a common and repetitive task for High Schools worldwide. In this paper a generic approach is presented for Greek High Schools organized around the idea of solving a significant number of tractable Integer Programming problems. Variables of the underlying mathematical model correspond to daily teacher schedules while a number of hard and soft constraints are included so as for the model to handle practical aspects that manifest themselves in Greek High Schools. By selecting better teacher schedules that exist in subproblems the quality of the overall solution gradually improves. The collected results which are obtained within reasonable time are most promising. The strength of the approach is supported by the fact that it managed to find the best known results for two public instance problems included in the Benchmarking Project for High School Timetabling (XHSTT-2012 1 )