Scheduling-Probleme mit stochastischen Anordnungsbeziehungen

In der Produktion werden heute zunehmend variantenreiche Produkte gefertigt. So werden z.B. beim Fahrzeugbau verschiedene Ausstattungen eines Fahrzeugs simultan auf einer Produktionsanlage gefertigt. Während der Produktion findet häufig eine Kontrolle der Produktqualität statt, d.h., die Ausführung eines Arbeitsgangs wird begutachtet und gegebenenfalls erneut durchgeführt. Betrachten wir die Arbeitsgänge, die bei der Produktion anfallen, als Bestandteile eines Projekts mit gewissen Ausführungsvorschriften, dann muss es möglich sein, mit Hilfe dieser Ausführungsvorschriften sowohl Rückkopplungen und wiederholtes Ausführen von Vorgängen als auch die alternative Ausführung mehrerer Vorgänge (Modellierung von Varianten) mit einer vorgegebenen Wahrscheinlichkeit zu modellieren. Um Projekte mit solchen stochastischen Ausführungsvorschriften (Unsicherheit bei der Abfolge von Vorgangsausführungen) beschreiben zu können, wurden sogenannte GERT-Netzpläne entwickelt. GERT-Netzpläne können dabei sowohl zur Modellierung als auch zur Planung und Steuerung von Projekten mit stochastischer Ablaufstruktur und Rückkopplungen eingesetzt werden. Spezielle GERT-Netzpläne mit verallgemeinerter Baumstruktur (Oder-Netzpläne) können mit Markowschen Erneuerungsprozessen assoziiert werden. Für die Zeitplanung solcher Projekten können dann Resultate der Theorie Markowscher Erneuerungsprozesse verwendet werden. Für allgemeinere GERT-Netzpläne sind analytische und Simulations-Methoden entwickelt worden.

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.

 

Kontakt  Sitemap  Impressum
© TU Clausthal 2017