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
  • Einführung
  • Ziele der Arbeit und Überblick
• Übersicht über das Spektrum der Problemstellungen
  • Terminologie
  • Schulische Stundenpläne
    (School-Timetabling/STP)
  • Daily School Timetabling
  • Universitäre Veranstaltungsplanung
    (University-Timetabling/UTP)
  • Das Kurswahlproblem
  • Prüfungsverteilung (Examination-Timetabling)
  • Raumverteilung (Room Allocation)
  • Nachbargebiete
  • Transformationen
  • Zusammenfassung
• Komplexität des Problems
  • Terminologie
  • Polynomiell lösbare Fälle
  • Realistische Problemstellungen sind -vollständig
  • Approximierbarkeit
  • Randomisierte Algorithmen/Heuristiken
  • Die Komplexität von Teilproblemen
  • Der Normalfall
  • Zusammenfassung
• 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
  • Problemstellung
  • Modell
  • Gesamtaufbau
  • Wahl der 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
  • Grundlagen
  • Das Prinzip des Simulated Trading
  • Erweiterung auf eine individuell ausgeglichene Methode
  • Spieltheorie
  • Ablauf der Auktion und Strategien
  • Erste Versuche einer Implementierung
  • Zusammenfassung
• Implementierung des Rahmenprogrammes
  • Datenstrukturen
  • Funktionalität und Implementierung des Editors
  • Die interaktive Unterstützung
  • Besonderheiten
  • Sonstiges
  • Qualitätsprüfung und -management
  • Zusammenfassung
• Evaluation
  • Testdaten
  • Ergebnisse
  • Weitere Anmerkungen
• Ausblick
  • Bemerkungen zur betrachteten Problemstellung
  • Erweiterungsmöglichkeiten
  • Perspektiven
• Literaturverzeichnis
• Beispielausdruck
• Über dieses Dokument ...