FU Berlin Digitale Dissertation
Heinrich Hilbert-Siekmann : On the Setting of School Timetables New Opportunities for Mixed Integer Programming Zur Stundenplansetzung an allgemeinbildenden Schulen
|Abstract| |Table of Contents| |More Information|

Abstract 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.

Table of Contents Download the whole PhDthesis as a zip-tar file or as zip-File For download in PDF format click the chapter title Nr. Kapitel / Unterkapitel Seite   Inhalts-, Tabellen- und Abbildungsverzeichnis   1 Einleitung 11 2 Problem der Stundenplansetzung an allgemeinbildenden Schulen 14 2.1 Einordnung und Abgrenzung 14 2.2 Restriktionen und Zielsetzungen 25 2.3 Komplexität und Lösbarkeit 35 2.4 Kriterien für die Beurteilung von Lösungsansätzen 40 2.5 Verwandtschaft zu anderen Stundenplanerstellungsproblemen 43 2.6 Zusammenfassung 50 3 Bisherige Lösungsansätze 52 3.1 Lösung in der schulischen Praxis Berlins 52 3.2 Lösungsansätze der Wissenschaft 63 3.3 Zusammenfassung und kritische Würdigung 130 4 Neue Lösungsansätze auf Basis Gemischt-ganzzahliger Programmierung 134 4.1 Einführung 134 4.2 Ansatz 1: ToMIP - Einstufige Setzung im Totalmodell 140 4.3 Ansatz 2: HiMIP - Hierarchische Setzung in einem Wochen- und mehreren Tagesmodellen 165 4.4 Ansatz 3: SeMIP - Sequenzielle Setzung nach Klassen mit vorgeschalteter Prioritätsphase 195 5 Erprobung der neuen Lösungsansätze 202 5.1 Implementation eines prototypischen Softwaresystems 202 5.2 Testfallkatalog 211 5.3 Testergebnisse 215 5.4 Kritische Würdigung in Theorie und Praxis 239 6 Fazit 245 7 Verzeichnis der verwendeten Literatur 248 8 Anhang 260 8.1 Erläuterungen zur schriftlichen Befragung Berliner Stundenplaner vom Winter 1997/98 260 8.2 Modellstrukturen der neuen Lösungsansätze 271 8.3 Stundenplanbeispiele 297 8.4 Fragebogen für die Beurteilung der SeMIP-Stundenpläne 309 8.5 Lebenslauf 311

More Information:
Online available:	http://www.diss.fu-berlin.de/2001/158/indexe.html
Language of PhDThesis:	german
Keywords:	School Timetabling, Mixed Integer Programming, Mathematical Programming, Exact Methods, Heuristics
DNB-Sachgruppe:	17 Wirtschaft
Date of disputation:	28-May-2001
PhDThesis from:	Fachbereich Wirtschaftswissenschaft, Freie Universität Berlin
First Referee:	Univ.-Prof. Dr. Christoph Haehling von Lanzenauer
Second Referee:	Univ.-Prof. Dr. Uwe H. Suhl
Contact (Author):	HeinHil@aol.com
Date created:	21-Aug-2001
Date available:	22-Aug-2001

 

---

|| DARWIN|| Digitale Dissertationen || Dissertation|| German Version|| FU Berlin|| Seitenanfang ||

---

	Fragen und Kommentare an: darwin@inf.fu-berlin.de
© Freie Universität Berlin 1999