Die Job-Shop-Planung ist ein herausforderndes Problem für die mathematische Programmierung. Gegebenenfalls können die betrieblichen Auswirkungen jedoch groß sein. Im heutigen Blogbeitrag werde ich mit einem technischen Beispiel zur genetischen Jobplanung zu diesem Thema beitragen .

Aufgabenplanungsproblem für Job-Shop-Maschinen

Das von mir vorgeschlagene Beispiel umfasst 3 Maschinen (M1, M2 und M3) und 5 Tasks (T1, T2, T3, T4 und T5). Die Aufträge müssen in einem Jobshop bearbeitet werden. Jede Aufgabe kann auf jeder Maschine verarbeitet werden, aber es gibt bestimmte Beschränkungen, die die mögliche Abfolge von Aufgaben auf jeder Maschine einschränken.

Die Einschränkungen könnten beispielsweise wie folgt aussehen:

• T1 muss vor T2 auf M1 verarbeitet werden
• T4 muss vor T5 auf M2 verarbeitet werden
• T2 und T3 können nicht auf derselben Maschine verarbeitet werden

Ich möchte nun auf jeder Maschine einen Aufgabenplan finden, der die Gesamtverarbeitungszeit für alle Aufgaben minimiert.

Job-Shop-Aufgabenplanung mit genetischen Algorithmen

Um dieses Problem mit einem genetischen Algorithmus zu lösen, stelle ich einen Zeitplan als eine Folge von ganzen Zahlen dar. Jede Ganzzahl repräsentiert die als nächstes zu bearbeitende Aufgabe. Zum Beispiel bedeutet ein Zeitplan [1, 2, 3, 4, 5], dass wir Aufgabe 1 auf Maschine 1 verarbeiten, gefolgt von Aufgabe 2 auf Maschine 2, gefolgt von Aufgabe 3 auf Maschine 3 und so weiter.

Wir können eine einfache Fitnessfunktion verwenden, die die Gesamtverarbeitungszeit für einen bestimmten Zeitplan unter Berücksichtigung der Einschränkungen berechnet. Beispielsweise können wir die Bearbeitungszeit wie folgt berechnen:

• Berechnen Sie für jede Maschine die Bearbeitungszeit als Summe der Bearbeitungszeiten aller Aufgaben, die dieser Maschine zugewiesen sind.
• Wenn es irgendwelche Beschränkungsverletzungen gibt (z. B. wenn T2 und T3 derselben Maschine zugewiesen sind), fügen Sie eine Strafe zur Verarbeitungszeit hinzu.
• Die Fitness eines Zeitplans ist das Negativ der Bearbeitungszeit.

Wir können dann einen genetischen Algorithmus verwenden, um Zeitpläne zu erstellen und weiterzuentwickeln, bis wir einen guten gefunden haben.

Beispiel für einen genetischen Scheduling-Algorithmus

Hier ist ein Beispiel dafür, wie der Algorithmus funktionieren könnte:

1. Generieren Sie eine Anfangspopulation von Zeitplänen, die jeweils aus einer zufälligen Abfolge von Aufgaben bestehen, die Maschinen zugewiesen werden.
2. Berechnen Sie die Fitness jedes Zeitplans mit der Fitnessfunktion.
3. Wählen Sie eine Teilmenge der Population aus, um die nächste Generation von Zeitplänen zu züchten, indem Sie eine Auswahlmethode wie die Turnierauswahl verwenden.
4. Erstellen Sie neue Zeitpläne mit Crossover- und Mutationsoperatoren.
5. Ersetzen Sie die alte Population durch die neue Population und wiederholen Sie die Schritte 2-4 für eine bestimmte Anzahl von Generationen.
6. Der beste gefundene Zeitplan ist derjenige mit dem höchsten Fitnesswert.

Job-Shop-Scheduling-Probleme sind bekanntermaßen NP-schwer, was bedeutet, dass das Finden der optimalen Lösung für große Probleminstanzen rechenintensiv ist. Infolgedessen kann es sein, dass genetische Algorithmen lange brauchen, um zu konvergieren, oder dass sie überhaupt nicht in der Lage sind, die optimale Lösung zu finden.

Abschließende Bemerkungen und zugehöriger Inhalt

Die Auftragsplanung ist ein anspruchsvolles Thema. Mathematische Programmierung und in diesem Fall genetische Algorithmen können in einigen Fällen effektiv sein. In anderen Fällen können Probleme zu komplex sein, um sie mit vertretbarem Aufwand analytisch zu lösen. Sollte dies der Fall sein, kann die diskrete Ereignissimulation helfen, einige der Herausforderungen der mathematischen Programmieranwendung zu überwinden. Der folgende SCDA-Blogbeitrag beschreibt die Herausforderungen der Auftragsfertigungsplanung:

• Link : Herausforderungen bei der Auftragsplanung

In den folgenden SCDA-Veröffentlichungen können Sie mehr über Simulation, insbesondere ereignisdiskrete Simulation, lesen. Die Simulationsmodellierung kann Scheduling-Lösungen implementieren, die die Herausforderungen der mathematischen Programmierung überwinden können, die sie für die Anwendung in realen Problemen ungeeignet machen.

• Link : Werkstattsimulation mit salabim in Python
• Link : Werkstattsimulation in SimPy
• Link : Visualisierung von SimPy Job Shop Simulation

Constraint-Programmierung ist ein weiterer Ansatz für die Job-Shop-Planung, den Sie wählen können. Hier ist ein Beispiel, das Ihnen den Einstieg erleichtern kann:

• Link : Constraint-Programmierung mit Google ortools

Linnart Felkl

Wirtschaftsingenieur mit Interesse an Optimierung, Simulation und mathematischer Modellierung in R, SQL, VBA und Python