DARWIN Digitale Dissertationen English Version Strich

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

FU Logo


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


Mail-Icon Fragen und Kommentare an:
darwin@inf.fu-berlin.de

© Freie Universität Berlin 1999