Ulteriori informazioni
Metaheuristiken, insbesondere Verfahren der lokalen Suche, werden mit zunehmendem Erfolg zur approximativen Lösung kombinatorischer Optimierungsprobleme eingesetzt. Bei der Konzeption operativer Systeme erweist sich die Vielfalt existierender Verfahrensvarianten jedoch oftmals als Hindernis, denn es gibt keine verallgemeinerbaren Handlungsempfehlungen zur Auswahl geeigneter Basisverfahren und zur probleminstanzunabhängigen Parametrisierung dieser Verfahren.
Für die Ablaufplanung in der Werkstattfertigung, das sogenannte Job-Shop-Scheduling, untersucht Jukka Siedentopf auf der Basis einer modular aufgebauten Verfahrensschablone verschiedene schwellenwertbasierte lokale Suchverfahren. In umfangreichen Effektivitäts- und Effizienzvergleichen demonstriert er die Dominanz eines Verfahrens, das einfach und problemunabhängig parametrisierbar ist. Damit ist die Grundvoraussetzung für einen flexiblen Einsatz auch in praktischen Umgebungen erfüllt. Abschließend untersucht der Autor das Konvergenzverhalten des Verfahrens mit Hilfe der Markov-Theorie.
Sommario
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.
Info autore
Dr. Jukka Siedentopf promovierte bei Prof. Dr. Stephan Zelewski am Institut für Produktion und Informationsmanagement der Universität Essen. Heute ist er Projektleiter für Verkehrssteuerungssysteme bei der Deutschen Post AG.
Riassunto
Metaheuristiken, insbesondere Verfahren der lokalen Suche, werden mit zunehmendem Erfolg zur approximativen Lösung kombinatorischer Optimierungsprobleme eingesetzt. Bei der Konzeption operativer Systeme erweist sich die Vielfalt existierender Verfahrensvarianten jedoch oftmals als Hindernis, denn es gibt keine verallgemeinerbaren Handlungsempfehlungen zur Auswahl geeigneter Basisverfahren und zur probleminstanzunabhängigen Parametrisierung dieser Verfahren.
Für die Ablaufplanung in der Werkstattfertigung, das sogenannte Job-Shop-Scheduling, untersucht Jukka Siedentopf auf der Basis einer modular aufgebauten Verfahrensschablone verschiedene schwellenwertbasierte lokale Suchverfahren. In umfangreichen Effektivitäts- und Effizienzvergleichen demonstriert er die Dominanz eines Verfahrens, das einfach und problemunabhängig parametrisierbar ist. Damit ist die Grundvoraussetzung für einen flexiblen Einsatz auch in praktischen Umgebungen erfüllt. Abschließend untersucht der Autor das Konvergenzverhalten des Verfahrens mit Hilfe der Markov-Theorie.
Testo aggiuntivo
Metaheuristiken, insbesondere Verfahren der lokalen Suche, werden mit zunehmendem
Erfolg zur approximativen Lösung kombinatorischer Optimierungsprobleme
eingesetzt. Bei der Konzeption operativer Systeme erweist sich die Vielfalt
existierender Verfahrensvarianten jedoch oftmals als Hindernis, denn es
gibt keine verallgemeinerbaren Handlungsempfehlungen zur Auswahl geeigneter
Basisverfahren und zur probleminstanzunabhängigen Parametrisierung dieser
Verfahren. Für die Ablaufplanung in der Werkstattfertigung, das sogenannte
Job-Shop-Scheduling, untersucht Jukka Siedentopf auf der Basis einer modular
aufgebauten Verfahrensschablone verschiedene schwellenwertbasierte lokale
Suchverfahren. In umfangreichen Effektivitäts- und Effizienzvergleichen
demonstriert er die Dominanz eines Verfahrens, das einfach und problemunabhängig
parametrisierbar ist. Damit ist die Grundvoraussetzung für einen flexiblen
Einsatz auch in praktischen Umgebungen erfüllt. Abschließend untersucht
der Autor das Konvergenzverhalten des Verfahrens mit Hilfe der Markov-Theorie.
