|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.
|PDF (817145 Bytes)|
|Abteilung(en)||Universität Stuttgart, Institut für Formale Methoden der Informatik, Algorithmik|
|Eingabedatum||24. November 2014|