FU Berlin Digitale Dissertation
Heinrich Hilbert-Siekmann : Zur Stundenplansetzung an allgemeinbildenden Schulen Neue Möglichkeiten der Gemischt-ganzzahligen Programmierung On the Setting of School Timetables
|Zusammenfassung| |Inhaltsverzeichnis| |Ergänzende Angaben|

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

Inhaltsverzeichnis Die gesamte Dissertation können Sie als gezippten tar-File oder als zip-File laden. Durch Anklicken der Kapitelüberschriften können Sie das Kapitel in PDF-Format laden: 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

Ergänzende Angaben:
Online-Adresse:	http://www.diss.fu-berlin.de/2001/158/index.html
Sprache:	Deutsch
Keywords:	School Timetabling, Mixed Integer Programming, Mathematical Programming, Exact Methods, Heuristics
DNB-Sachgruppe:	17 Wirtschaft
Datum der Disputation:	28-May-2001
Entstanden am:	Fachbereich Wirtschaftswissenschaft, Freie Universität Berlin
Erster Gutachter:	Univ.-Prof. Dr. Christoph Haehling von Lanzenauer
Zweiter Gutachter:	Univ.-Prof. Dr. Uwe H. Suhl
Kontakt (Verfasser):	HeinHil@aol.com
Abgabedatum:	21-Aug-2001
Freigabedatum:	22-Aug-2001

 

---

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

---

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