Zur Stundenplansetzung an allgemeinbildenden Schulen: Neue Möglichkeiten der Gemischt-ganzzahligen Programmierung

Abstract

Diese Arbeit untersucht das Problem der Stundenplansetzung an allgemeinbildenden Schulen, definiert als Zuordnungsproblem von Unterrichtseinheiten (Kombinationen von Lehrern, Klassen, Fächern und Raumgruppen) zu Perioden und Räumen. Dabei werden zunächst, gestützt auf eine empirische Untersuchung, Restriktionen und Zielsetzungen des Problems identifiziert und eine Abgrenzung von verwandten Stundenplanerstellungsproblemen vorgenommen. Anschließend werden bisherige Lösungsansätze, die sowohl der Praxis als auch der Wissenschaft im Bereich der Stundenplanung entstammen, hinsichtlich ihres Potenzials für die Lösung des o.g. speziellen Setzungsproblems untersucht. Darüber hinaus werden drei neue Ansätze auf Basis der Gemischt-ganzzahligen Programmierung vorgestellt, die den Kern der Arbeit bilden. Von diesen beinhaltet der erste, ToMIP, die Abbildung des Problems in Form eines gemischt-ganzzahligen Totalmodells. Der zweite Ansatz, HiMIP, bedient sich einer Aufteilung des Gesamtproblems in ein Wochen- und mehrere Tagesprobleme. Sie werden jeweils in einem eigenen gemischt-ganzzahligen Modell dargestellt, wobei die Lösung des Wochenmodells die Basis für die einzelnen Tagesmodelle bildet. Im dritten Ansatz, SeMIP, wird die Menge aller Unterrichtseinheiten nach Prioritätskriterien und nach Schulklassen in mehrere Teilmengen aufgeteilt und für jede dieser Teilmengen ein eigenes gemischt-ganzzahliges Teilmodell formuliert. Die Lösung der Teilmodelle erfolgt sequenziell, wobei die Ergebnisse der bereits gelösten Modelle als Randbedingungen in das jeweils nachfolgend zu lösende Modell eingehen. Die Ansätze HiMIP und SeMIP beinhalten zufallsgesteuerte Komponenten, welche bei wiederholtem Durchlauf unterschiedliche Lösungspfade garantieren. Im Anschluss an ihre Formulierung werden für die drei Ansätze Testergebnisse präsentiert, die mit Hilfe von Praxisdaten erzielt wurden. Sie zeigen, dass ToMIP und HiMIP kein, SeMIP hingegen ein signifikantes Potenzial für die adäquate Setzung von Stundenplänen allgemeinbildender Schulen beinhaltet.

This thesis examines the problem of setting timetables at primary and secondary schools, which is defined as the problem of assigning teaching units (combinations of teachers, classes, subjects and room groups) to time slots and rooms. The analysis starts with an identification, based on an empirical survey, of constraints and objectives relevant to this problem also pointing out differences from related timetabling problems. The thesis continues with an analysis of solution approaches which have formerly been developed by practitioners as well as scientists in the timetabling field in order to identify their potential to adequately solve the special problem regarded here. Moreover, three new approaches based on Mixed Integer Programming are presented forming the main focus of the thesis. The first one, ToMIP, transforms the problem into a single mixed integer model. The second approach, HiMIP, divides the overall problem into one weekly and several daily problems. Each of these problems is depicted in a separate mixed integer model with the solution of the weekly model rendering the basic data for each daily model. The third approach, SeMIP, divides the set of all teaching units into a number of subsets using calculated priorities as well as school classes as separation criteria. Each of these subsets is represented by its own mixed integer sub- model. The sub-models are solved sequentially with each model containing the results of its predecessors as side constraints. Approaches HiMIP and SeMIP also contain randomized components in order to guarantee varying solution paths when the solution process is iterated. Having formulated the three new solution approaches test results based on real life data are presented. They show that ToMIP and HiMIP have no potential, whereas SeMIP has a significant potential of properly setting primary and secondary school timetables.