Postscript / Anfang
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 ...
(c) Martin Loehnertz 1999