Ein Tabu Search-Verfahren zur Lösung des Timetabling-Problems an deutschen Grundschulen

The paper presents a tabu search algorithm (TSA) for the Timetabling problem at German primary schools (GPS-TTP). The GPS-TTP represents a special variant of School Time-tabling with a specific mix of constraints. At first the GPS-TTP is modelled as a binary optimization problem. The model is formulated in terms of so-called complex lesson units (CLU). A CLU aggregates all lessons that are forced by coupling constraints to happen at the same time or one after another (2-hour lessons). Two objective functions are formulated. Each of them aims at the avoidance of idle periods as well as compact time tables. But these criteria are prioritized in a different way within the objective functions. The TSA is based on the model. Consequently, CLUs are to be planned instead of simple lessons. Moreover, a multiobjective optimization is carried out using both objective functions. Thus, the search results in two best solutions (per instance) which form a so-called Paretofront of non-dominated solutions. The method was tested by means of 45 instances. Some instances stem directly from practice while the others are derived from them. The test showed that the TSA is able to cover practical requirements regarding the solution quality as well as the calculation time.