Bachelorarbeit BCLR-0137

Keck, Philipp: Optimierung von Schulstundenplänen.
Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, Bachelorarbeit Nr. 137 (2014).
86 Seiten, deutsch.
CR-Klassif.I.2.8 (Problem Solving, Control Methods, and Search)
G.2.3 (Discrete Mathematics Applications)
F.2.2 (Nonnumerical Algorithms and Problems)
J.1 (Administration Data Processing)

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.

Volltext und
andere Links
PDF (817145 Bytes)
Abteilung(en)Universität Stuttgart, Institut für Formale Methoden der Informatik, Algorithmik
BetreuerFunke, Stefan
Eingabedatum24. November 2014
   Publ. Informatik