Energieorientierte Produktionsplanung: Ein Fallbeispiel mit Simheuristics 

Kurze Einführung in die Simulation und Optimierung  

In der mathematischen Optimierung ist die Maschinenbelegungsplanung (Scheduling) eine häufige Aufgabe. Scheduling-Probleme zielen darauf ab, optimale Zuweisungsstrategien zwischen begrenzten Ressourcen (z. B. Maschinen und Anlagen) und Aufträgen zu finden. Sie sind aufgrund ihrer Komplexität, vielfältiger Nebenbedingungen, diverser Zielgrößen und des großen Lösungsraums oft als NP-schwere Probleme definiert. Ein NP-schweres Problem ist eine Klassifikation für die komplexesten Probleme, die nicht in polynomialer Zeit lösbar sind. Normalerweise erfordert es erhebliche Rechenressourcen und Zeit, um die optimale Lösung zu finden, was zu einer großen Herausforderung in der Praxis führen kann. Aufgrund dieser Herausforderungen ist es oft unmöglich, solche Probleme in begrenzter Zeit mit exakten Optimierungsmethoden zu lösen. Einige heuristische und approximative Algorithmen können in praktischen Anwendungen ausreichend gute Lösungen in kurzer Zeit liefern. Die Verwendung rein heuristischer Optimierungsmethoden kann jedoch aufgrund der Komplexität des Problems zu einer starken Vereinfachung des Problems führen und potenziell wichtige Details oder Zusammenhänge unterschlagen. Dabei ergeben sich folgende Effekte: 

1. Im realen Produktionsprozess gibt es viele zufällige Ereignisse, wie Schwankungen in der Taktzeit an manuellen Arbeitsstationen und das Auftreten unerwarteter Ausfallzeiten der Maschine. 
2. Die in der Produktion verwendeten Richtlinien sind dynamisch und beeinflussen sich gegenseitig, wie zum Beispiel die Reaktionspläne, die in verschiedenen Szenarien verwendet werden. 
3. Es ist schwierig die räumlichen Anforderungen von Personen und Maschinen zu berücksichtigen. 
4. Das zu optimierende Zielsystem ist oft ein Subsystem eines übergeordneten Systems. Die Interaktionen zwischen mehreren Subsystemen sind schwierig anhand von reiner Optimierung darzustellen.

Simulationsmodelle hingegen können solche komplexe Systeme, insbesondere Systeme mit Zufallsvariablen, besser abbilden. Durch Einstellen der Attribute jedes Elements sowie der interaktiven Regelung zwischen den Elementen werden charakteristische Eigenschaften und das Verhalten des Systems simuliert. Anhand von verschiedenen Eingaben kann man durch das Simulationsmodell das Verhalten des Systems experimentell beobachten und so die zukünftige Leistung des realen Systems evaluieren. Konkret: Durch Kopplung von einem Simulationsmodell mit einem Optimierungsverfahren können komplexe Probleme effizient bewältigt werden. 

Die Art und Weise, wie Simulation und Optimierung kombiniert werden, kann nach Lothar März [1] in vier Kategorien unterteilt werden. 

Abbildung 1 – Kopplung von Simulation und Optimierung: (a) Optimierungsintegrierte Simulation, (b) Simulation bewertet die Optimierung, (c) Die Simulationsergebnisse als Anfangswert der Optimierung, (d) Simulationsbasierte Optimierung 

Die simulationsbasierte Optimierung, d. h. die Integration des Simulationsmodells in das heuristische Framework, ist bekannt als Simheuristics [2]. Hierbei wird die Simulation verwendet, um jede gefundene Lösung durch die Heuristik-Komponente zu bewerten. Zur Verdeutlichung dieser Methode wird im Folgenden ein Fallbeispiel vorgestellt. 

Fallstudie: Scheduling einer zweistufigen Werkstatt mit Blick auf den Energieverbrauch und die Gesamtproduktionszeit 

Anhand dieses Anwendungsbeispiels, zeigen wir Ihnen ein typisches Simheuristic-Framework und um weisen auf potentielle Erweiterungen und Verbesserungen hin.  

Problem: 

Eine kleine Werkstatt stellt mit ihren zweistufigen Produktionsgeräten Produkte her und montiert sie. In der ersten Stufe gibt es drei parallele automatische Stationen mit den gleichen Funktionen, aber der Energieverbrauch und die Zykluszeit für die Herstellung der Teile ist jeweils unterschiedlich. Die zweite Stufe ist eine manuelle Montagestation, die von einem Mitarbeiter bedient wird. Der Mitarbeiter muss die Teile aus der Station der ersten Stufe entnehmen und an der Station der zweiten Stufe bearbeiten. Zwischen der ersten und der zweiten Stufe gibt es keinen zeitlichen Puffer. 

Abbildung 2: Simulationsmodell des beispielhaften Anwendungsfalls 

Die Werkstatt hat jetzt eine Reihe von Aufträgen erhalten, die innerhalb des Tages abgeschlossen werden müssen. Alle Teile in diesen Aufträgen müssen zunächst in der ersten Stufe und dann in der zweiten Stufe bearbeitet werden. Es gibt keine besonderen Einschränkungen für die verwendete Maschine. Die Werkstatt muss die Aufträge planen, um den Gesamtenergieverbrauch und die Produktionszeit zu minimieren. 

Abbildung 3: unterschiedliche Bearbeitungszeit in Bezug auf Produkt und Maschine 

Lösung: 

Um mit dieser Aufgabenstellung umzugehen verwenden wir ein Simheuristic-Framework, das ein DES-Modell (Discrete-Event-Simulation) in einem mehrkriteriellen genetischen Algorithmus integriert. Das DES-Modell wurde durch die Software Tecnomatix Plant Simulation erstellt. Es umfasst drei parallele automatische Stationen und eine manuelle Station. Jede automatische Station ist so konfiguriert, dass sie je nach Betriebszustand und Werkstücktyp unterschiedliche Energieverbräuche und Bearbeitungszeiten aufweist. Automatische Stationen verfügen über Puffer, in denen zu produzierende Werkstücke abgelegt und nach FIFO-Prinzip produziert werden. Die Werkstücke werden von Arbeitern zwischen den Stationen transportiert und weiterverarbeitet. Nach Abschluss der Simulation erfasst das Modell die Gesamtproduktionszeit und den Energieverbrauch. Diese Daten können über eine Socket-Schnittstelle zur Optimierung übertragen werden. Das gesamte Prozessframework ist wie folgt: 

Abbildung 4: Prozessframework der Optimierung 

Zuerst werden durch die Anwendung eines genetischen Algorithmus eine Reihe von möglichen Lösungen generiert. Dieses Set an Lösungen wird in der Simulation bewertet. Dann werden Gruppen ausgewählt, die sich kreuzen und mutieren, um eine neue Generation zu erzeugen. Die Schritte 2 und 3 werden wiederholt, bis die vorgegebene Laufzeit überschritten ist oder die erforderliche Anzahl von Generationen erreicht ist. 

Ergebnis: 

Das Optimierungsergebnis bildet eine Pareto-Front (d. h. Eine Gruppe von Lösungen in der multi-objektiven Optimierung, bei welchen eine Verbesserung in einem Ziel, eine Verschlechterung in mindestens einem anderen Ziel erfordert). Jedes „Individuum“ repräsentiert eine Lösung bestehend aus zehn „Genen“ (Werkstücken), wobei jedes Gen die Freigabezeit und -station eines Werkstücks darstellt. Die Fitnesswerte sind Gesamtproduktionszeit und Energieverbrauch. Die am besten geeignete Lösung kann je nach Anforderungen (z. B. frühere Fertigstellung) ausgewählt werden. 

Abbildung 5: Pareto-Front der besten Lösungen 

Potenzial für Erweiterungen und Verbesserungen 

Aufgrund der Größe und Komplexität des Simulationsmodells ist die Geschwindigkeit des Simulationsdurchlaufs jedoch langsam. Wenn die Simulation häufig verwendet wird, kann dies die Geschwindigkeit des gesamten Prozesses verlangsamen und das Risiko erhöhen, die vorgegebene Rechenzeit zu überschreiten, bevor eine akzeptierbare Lösung gefunden wird. Verbesserungen und Erweiterungen dieses Frameworks sollten daher die Geschwindigkeit der Optimierung erhöhen und die Qualität der Ergebnisse verbessern. Dies wird durch die Verringerung der Anzahl an Aufrufen des Simulationsmodells erreicht . Daraus folgt eine effizientere Durchführung der Simulation.

Konkret ergeben sich dafür folgende Maßnahmen [3]:  

1. Es wird eine Vorsortierung von Lösungskandidaten durchgeführt und nur „vielversprechende“ Lösungen werden an die Simulation übergeben. Dadurch verringert sich die Anzahl der zu bewertenden Lösungen.  
2. Die Bewertung der Lösungen können erfasst und bei gleichen Genen weiter genutzt werden, um redundante Simulationsdurchläufe zu vermeiden.
3. Parameter können unterschiedliche Prioritäten, Suchbereiche und Genauigkeiten haben. Für Parameter mit höherer Priorität wird ein umfangreicher und präziser Suchbereich definiert, während für weniger wichtige Parameter, die einen geringen Einfluss auf den Zielwert haben, ein reduzierter Suchbereich und eine niedrigere Genauigkeit zugewiesen werden. Aus der Perspektive der Simulation können Modelle verschiedener Komplexitätsgrade in unterschiedlichen Optimierungsphasen eingesetzt werden. Ein deterministisches Simulationsmodell führt eine grobe Bewertung der Lösungen während des iterativen Prozesses durch, um eine erste Auswahl zu treffen. Ein detaillierteres stochastisches Simulationsmodell führt dann eine Tiefenanalyse der ausgewählten Lösungen durch, um die Robustheit der Lösungen zu testen und die optimale Lösung zu finden. 

[1] März, Lothar, et al., eds. Simulation und Optimierung in Produktion und Logistik: Praxisorientierter Leitfaden mit Fallbeispielen. Springer-Verlag, 2010. 

[2] Juan, Angel A., et al. „A review of simheuristics: Extending metaheuristics to deal with stochastic combinatorial optimization problems.“ Operations Research Perspectives 2 (2015): 62-72. 

[3] Rabe, Markus, Maik Deininger, and Angel A. Juan. „Speeding up computational times in simheuristics combining genetic algorithms with discrete-event simulation.“ Simulation Modelling Practice and Theory 103 (2020): 102089. 

Bildquelle: Headerbild via Dall-E 3 erstellt.