Bachelor Thesis BCLR-0137

BibliographyKeck, Philipp: Optimierung von Schulstundenplänen.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Bachelor Thesis No. 137 (2014).
86 pages, german.
CR-SchemaI.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)
Abstract

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.

Full text and
other links
PDF (817145 Bytes)
Department(s)University of Stuttgart, Institute of Formal Methods in Computer Science, Algorithmic
Superviser(s)Funke, Stefan
Entry dateNovember 24, 2014
   Publ. Computer Science