Inhaltsverzeichnis

• Einleitung
  • Einführung
  • Ziele der Arbeit und Überblick
• Übersicht über das Spektrum der Problemstellungen
  • Terminologie
    • Scheduling, Roostering
    • Das open shop scheduling model (OSS)
    • Eigene Bezeichnungen
  • 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
    • Fälle mit unbeschränktem Grad
    • Beschränkter Grad
    • Gewichtete Fälle
  • Randomisierte Algorithmen/Heuristiken
  • Die Komplexität von Teilproblemen
    • Festhalten des Zeitpunkts
    • Festhalten eines Objekts
    • Festhalten der Blockungen
  • Der Normalfall
  • Zusammenfassung
• Lösungsansätze
  • Direkte Heuristiken
  • Wissensbasierte Verfahren / Expertensysteme
  • Graphentheoriebasierte Verfahren
    • Modellierungsansätze
    • Integer Multicommodity Flüsse
    • Der Algorithmus nach König
      • Einige Grundlagen aus der Matchingtheorie
      • Anwendung im Timetabling
    • Der Satz von Galvin
      • Beweis:
      • Beweis:
      • Beweis:
    • equitable colorings
  • Lineare Programmierung / Ganzzahlige Lineare Programmierung / Semidefinite Programme
    • Lineare Programmierung und Ganzzahlige Lineare Programmierung
    • Semidefinite Programme
  • Constraintbasierte Verfahren
    • Prinzip
    • Das Verfahren von Gotlieb
    • Anwendbarkeit
  • Genetische Algorithmen / Evolutionsstrategien
  • Lokale Suchverfahren: Simulated Annealing und
    Threshold Accepting
  • Negotiation
  • Weitere Ansätze
  • Unergiebige Ansätze
    • Das Optimum Cost Chromatic Partition Problem
    • Bekannt gutartige Formen von Hypergraphen
    • Andere Ergebnisse zu Kantenfärbungen und Matchings in Hypergraphen
    • PathMatching
    • Approximationsalgorithmen für
      Multicommodity-Flow Probleme
    • Approximationsschemata für dichte Graphen
    • Sonstiges
  • Zusammenfassung
• Grundlegende Architektur, Modell und Algorithmen
  • Problemstellung
  • Modell
    • Das betrachtete Problem als ILP
    • Zielfunktion
  • Gesamtaufbau
    • Stammdatenverwaltung und Mengensystem
    • Gruppen
  • 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
    • Bewertungs und Aspiration - Funktion
  • Hybridisierung mit einer Variante des Algorithmus nach K¨ONIG
    • Anwendungsvoraussetzungen
    • Gewichtetes Matching
    • Für die Hybridisierung günstige Eigenschaften
    • Auswirkungen der Hybridisierung
    • Nachbearbeitung
      • Gestaffelte Ressourcenoptimierung
      • Alternierende Kreise
  • Implementierung dieses Verfahrens
    • Die Tabuliste
    • Der Filterschritt
    • Startpunkt
    • Laufzeitanalyse
  • Variationen des Graphenalgorithmus ohne
    Tabusuche
  • Zusammenfassung
• Verfahren 2: Handels - Heuristik
  • Grundlagen
  • Das Prinzip des Simulated Trading
  • Erweiterung auf eine individuell ausgeglichene Methode
  • Spieltheorie
    • Terminologie
    • Resultate
    • Reinterpretation im Rahmen der kombinatorischen Optimierung
    • Fazit
  • Ablauf der Auktion und Strategien
    • Auktionsschemata
    • Aufgabenbereich der Händler und Strategiebestimmung
      • Durch die Komplexität gesetzte Grenzen
      • Mögliche Modelle
    • Strategiebestimmung
    • Erzwingen des Anhaltens
    • Kooperation und Wahl des Homotopie - Parameters
  • Erste Versuche einer Implementierung
  • Zusammenfassung
• Implementierung des Rahmenprogrammes
  • Datenstrukturen
  • Funktionalität und Implementierung des Editors
    • Objekttypen- und Objekteditor
    • Mengeneditor
    • Bewertungs- und Zeiteditor
    • Ansichten
    • Gruppen- und Stundeneditor
    • Löschen, Kopierfunktionen und Zurücknahmefunktion
  • Die interaktive Unterstützung
  • Besonderheiten
    • Integrität und kaskadierende Löschvorgänge
    • Objektbeziehungen
    • Prüfung der Ressourcenzuteilung
    • Import und Export
    • Das Einbinden von Lösungsverfahren
  • Sonstiges
    • Darstellung und Symbolik
    • Codeoptimierung
    • Ergonomie
  • Qualitätsprüfung und -management
    • DIN ISO 9001-3, DIN ISO/IEC 12119
    • Sperrvariablen
    • Datumsabhängigkeiten
    • Unterstützung durch die Entwicklungsumgebung
  • Zusammenfassung
• Evaluation
  • Testdaten
  • Ergebnisse
    • Parameterwahl
    • Diagramme
  • Weitere Anmerkungen
• Ausblick
  • Bemerkungen zur betrachteten Problemstellung
  • Erweiterungsmöglichkeiten
    • Datenbankfunktionalität
    • Berichtsgenerator
    • Weitere relative Nebenbedingungen
    • Lehrerverteilung
  • Perspektiven
    • Problemstellungen
    • Lernfähige Systeme
    • Lösungsalgorithmen
• Literaturverzeichnis
• Beispielausdruck
• Über dieses Dokument ...