Scheduling-Probleme mit stochastischen Anordnungsbeziehungen
Stochastische Vorrangbeziehungen zwischen Jobs von Scheduling-Problemen können als sogenannte GERT-Netzpläne dargestellt werden. GERT-Netzpläne sind zur Modellierung, Planung und Steuerung von Projekten mit stochastischer Ablaufstruktur und Rückkopplungen entwickelt worden. Spezielle GERT-Netzpläne mit verallgemeinerter Baumstruktur (sogenannte Oder-Netzpläne) können mit Markowschen Erneuerungsprozessen assoziiert werden. Für die Zeitplanung von Projekten, die durch Oder-Netzpläne modelliert werden, können Resultate der Theorie Markowscher Erneuerungsprozesse verwendet werden. Für allgemeinere GERT-Netzpläne sind analytische und Simulations-Methoden entwickelt worden.
Maschinen-Scheduling-Probleme mit stochastischen Anordnungsbeziehungen treten in der Variantenfließfertigung (z.B. in der Automobilindustrie) und der Werkstattfertigung auf. Für einige Ein-Maschinen-Scheduling-Probleme mit Vorrangbeziehungen, die Oder-Netzplänen entsprechen, sind polynomiale Lösungsverfahren entwickelt worden. Das allgemeine Ein-Maschinen-Minisum-Scheduling-Problem mit GERT-Anordnungsbeziehungen kann mittels stochastischer dynamischer Optimierung gelöst werden.
Parallel-Maschinen-, Flow-Shop- und Job-Shop-Scheduling-Probleme mit GERT-Anordnungsbeziehungen sind NP-schwer. Für identische parallele Maschinen und Oder-Vorrangbeziehungen stehen zwei Arten von heuristischen Lösungsverfahren zur Verfügung: Verallgemeinerungen von Methoden für entsprechende deterministische Probleme und Prioritätsregelverfahren. Die meisten dieser Heuristiken können auf Probleme mit allgemeinen GERT-Anordnungsbeziehungen übertragen werden. Für Flow-Shop- und Job-Shop-Scheduling-Probleme mit Oder-Vorrangbeziehungen sind eine Shifting-Bottleneck-Heuristik und Prioritätsregelverfahren vom Giffler-Thompson-Typ entwickelt worden. Lösungsmethoden dieser Art sind für die Minimierung der erwarteten Makespan, der maximalen erwarteten Lateness oder der maximalen erwarteten Tardiness verfügbar. Für Flow-Shop-Probleme ist außerdem der Fall begrenzter Zwischenläger vor den einzelnen Maschinen betrachtet worden.
Veröffentlichungen des Lehrstuhls im Forschungsgebiet
Bücher:
-
Lechleiter, I. (1999):
Maschinenbelegungsplanung in der Variantenfertigung, Gabler, Wiesbaden -
Schneider, W. (1997):
Job Scheduling with Stochastic Precedence Constraints, Shaker, Aachen -
Neumann, K. (1990):
Stochastic Project Networks - Temporal Analysis, Scheduling and Cost Minimization Lecture Notes in Economics and Mathematical Systems, Vol. 344, Springer, Berlin -
Neumann, K.; Steinhardt, U. (1979):
GERT Networks and the Time-Oriented Evaluation of Projects. Lecture Notes in Economics and Mathematical Systems, Vol. 172, Springer, Berlin
Referierte Fachzeitschriften (ab 1996):
-
Neumann, K.; Schneider, W. (1999):
Heuristic Algorithms for Job-Shop Scheduling Problems with Stochastic Precedence Constraints, Annals of Operations Research 92, 45-63 -
Zimmermann, J. (1999):
Time Complexity of Single- and Identical Parallel-Machine Scheduling with GERT Network Precedence Constraints, Mathematical Methods of Operations Research 49, 221-238 -
Neumann, K.; Zimmermann, J. (1998):
Heuristic Procedures for Parallel-Machine Scheduling Problems with Stochastic Precedence Constraints, Annals of Operations Research 83, 115-136
Beiträge in Tagungs- und Sammelbänden (ab 1996):
-
Neumann, K. (1999):
Scheduling of Projects with Stochastic Evolution Structure. In: Weglarz, J., Ed., Project Scheduling: Recent Models, Algorithms, and Applications, Kluwer, 309-332 -
Lechleiter, I. (1998):
Verfahren zur Berechnung unterer Schranken für den erwarteten Abschlußzeitpunkt bei Job-Shop Scheduling Problemen mit stochastischen Anordnungsbeziehungen. In: Kischka, P.; Lorenz, H.-W.; Derigs, U.; Domschke, W.; Kleinschmidt, P.; Möhring, R., Eds., Operations Research Proceedings, Springer, Berlin 1998, 434-439
zurück
oben