Optimierung von Schulstundenplänen

Abstract

Die automatische Erstellung von Stundenplänen für Schulen ist seit vielen Jahren Forschungsgegenstand in den Bereichen der Künstlichen Intelligenz und der Unternehmensforschung. Diese Arbeit kombiniert Techniken aus beiden Bereichen: Eine Modellierung als Constraint Satisfaction Problem und eine Modellierung als pseudo-boolesches Optimierungsproblem werden jeweils mit der Relaxierung des zugehörigen linearen Programms kombiniert, um schneller bessere Ergebnisse zu erzielen. Für jede Variante und Kombination dieser Modellierungen wurden Tests mit vier verschiedenen Probleminstanzen durchgeführt. Die Ergebnisse zeigen, dass die vorgestellten Verfahren zumindest für kleinere Schulen, wie beispielsweise deutsche Grundschulen, ähnlich schnell sind wie etablierte Verfahren. Im Unterschied zu diesen liefern die vorgestellten Verfahren jedoch stets vollständig zulässige und beweisbar optimale Lösungen und sind zudem einfacher erweiterbar und anpassbar. In Kombination mit kommerziellen Lösern erzielen die vorgestellten Modellierungen auch für größere Probleminstanzen, wie z. B. die von deutschen Gymnasien, bessere Ergebnisse. Die Modellierungen und Ergebnisse in dieser Arbeit sind spezifisch für das deutsche Schulsystem.

For many years, the automated construction of school timetables has been subject of research in Artificial Intelligence and Operations Research. This thesis combines techniques from both areas: Formulations as a constraint satisfaction problem and as a pseudo-boolean optimization problem are each combined with the relaxation of the corresponding linear program, in order to obtain better results more quickly. For each variant and combination of these formulations, tests were carried out using four different instances. The results show that - at least for smaller schools like German primary schools - the proposed methods are as fast as established methods. In contrast to these, the proposed methods always yield entirely feasible and provably optimal solutions. Moreover, they are easier to extend and adjust. When combined with commercial solvers, the proposed problem formulations achieve better results for larger instances like those of German high schools, as well. The formulations and results in this thesis are specific to the German education system.