Theorie und Praxis der automatischen Stundenplanerstellung
Next: Inhaltsverzeichnis Up: Postscript
Universität Bonn
Institut für Informatik III
Prof. Dr. A.B. Cremers
Diplomarbeit
zum Thema
Theorie und Praxis der automatischen Stundenplanerstellung
Vorgelegt von
Martin Löhnertz WS 1998/99
Danksagung
Die vorliegende Arbeit wurde betreut durch Prof. Dr. A.B. Cremers sowie Dipl. Math. C. Hundack und Dipl. Inf. J. Lüssem, denen ich für ihre Unterstützung danke. Mein besonderer Dank gilt Prof. Dr. M. Karpinski, der sich die Zeit für eine längere Diskussion zum Thema Approximationsalgorithmen nahm. Ebenso danke ich den Lehrern, die bereit waren, mir Testdaten zu überlassen bzw. an der Befragung teilzunehmen.
Martin Löhnertz Bonn, 1.2. 1999
- Inhaltsverzeichnis
- Einleitung
- Übersicht über das Spektrum der Problemstellungen
- Komplexität des Problems
- Lösungsansätze
- Direkte Heuristiken
- Wissensbasierte Verfahren / Expertensysteme
- Graphentheoriebasierte Verfahren
- Lineare Programmierung / Ganzzahlige Lineare Programmierung / Semidefinite Programme
- Constraintbasierte Verfahren
- Genetische Algorithmen / Evolutionsstrategien
- Lokale Suchverfahren: Simulated Annealing und
Threshold Accepting - Negotiation
- Weitere Ansätze
- Unergiebige Ansätze
- Zusammenfassung
- Grundlegende Architektur, Modell und Algorithmen
- Verfahren 1: Tabusuche
- Allgemeine Betrachtungen zum Lösungsraum
- Wahl der Heuristik: Die Tabuliste als notwendiges Element
- Tabusuche als allgemeines Optimierungsverfahren
- Kodierung
- Wahl der Nachbarschaft
- Hybridisierung mit einer Variante des Algorithmus nach K¨ONIG
- Implementierung dieses Verfahrens
- Variationen des Graphenalgorithmus ohne
Tabusuche - Zusammenfassung
- Verfahren 2: Handels - Heuristik
- Implementierung des Rahmenprogrammes
- Evaluation
- Ausblick
- Literaturverzeichnis
- Beispielausdruck
- Über dieses Dokument ...
-vollständig
(c) Martin Loehnertz 1999