Job-Shop-Scheduling

1 Motivation.- 2 Scheduling.- 2.1 Terminologischer Rahmen.- 2.2 Scheduling-Probleme.- 3 Grundelemente des Scheduling-Prozesses.- 3.1 Problem- und Lösungsrepräsentation.- 3.2 Die Konstruktion von Ablaufplänen.- 4 Suche.- 4.1 Suche als Problemlösungsstrategie.- 4.2 Lokale Suche.- 4.3 Erweiterungen der lokalen Suche.- 4.4 Lokale Suchverfahren für das J | | Cmax-Problem.- 5 Initialisierungsplanung durch Prioritätsregelverfahren.- 5.1 Charakterisierung von Prioritätsregelverfahren.- 5.2 Prioritätsregelgesteuertes Dispatching.- 5.3 Einfache Head-Tail-basierte Prioritätsregeln.- 5.4 Ergebnisse.- 6 Eine J | | Cmax-Schablone für Schwellenwertverfahren.- 6.1 Design problemspezifischer Verfahrenskomponenten.- 6.2 Grobstruktur einer Schablone für Schwellenwertverfahren.- 6.3 Verfahrensspezifische Parametrisierung.- 7 Evaluierung.- 7.1 Evaluierung des Konvergenzverhaltens.- 7.2 FAP: Ergebnisse für die Testprobleminstanzen des OR-Library.- 8 Zum Konvergenzverhalten von FAP.- 8.1 FAP als dynamisches System diskreter Zustandsänderungen.- 8.2 Existenz der stationären Verteilung.- 8.3 Die vermutete Gestalt der stationären Verteilung.- 8.4 Konvergenz der stationären Verteilung.- 8.5 Zusammenfassung.- 9 Fazit.- A.1 Aktives Dispatching (Verfahren AD/UD).- A.2 Lokale Suche: Resultate für 10x10-Testprobleminstanzen.- A.3 5x20-Testprobleminstanzen.- A.4 Neue Cmax-Upper-Bounds.- A.5 Stationäre Verteilung bei vollständig verknüpftem Suchraum.