Job Shop Scheduling

Job Shop Scheduling oder das Job Shop Scheduling Problem (JSP) ist ein Optimierungsproblem mit Anwendungen in der Maschinenbelegungsplanung mit dem Produktionssysteme mit Werkstattfertigung modelliert werden können. Die Aufgabe besteht darin, $n$ Aufträge (auch Jobs) optimal auf $m$ Maschinen zu verteilen, wobei jeder Auftrag aus verschiedenen Arbeitsschritten besteht, die auf bestimmten Maschinen bearbeitet werden müssen. Dabei kann jeder Auftrag grundsätzlich auch mehrmals auf derselben Maschine bearbeitet werden oder auch manche Maschinen auslassen.

Aufträge durchlaufen in der Produktion Maschinen in unterschiedlichen Reihenfolgen. Der rote Auftrag muss etwa auf den Maschinen 3, 2 und 6 verarbeitet werden.

Formulierung als Optimierungsmodell

Es gibt verschiedene Möglichkeiten, das Job Shop Scheduling Problem als gemischt-ganzzahliges lineares Optimierungsproblem (MILP) zu formulieren. Vorgestellt wird das folgendeOptimierungsmodell, welches als disjunctive JSP formulation bezeichnet wird und sich laut Literatur im Vergleich zu anderen Modellen als vorteilhaft erwiesen hat.

Notation

Es seien $J=\{1,\ldots ,n\}$ die Menge der zu verteilenden Jobs und $M=\{1,\ldots ,m\}$ die Menge der zur Verfügung stehenden Maschinen. Für jeden Job $j$ sei $(\sigma _{1}^{j},\ldots ,\sigma _{m}^{j})$ die Reihenfolge der Maschinen, welche durch die Abarbeitung der Arbeitsschritte benötigt werden. Beispielsweise würde $(\sigma _{1}^{7},\sigma _{2}^{7},\sigma _{3}^{7})=(2,1,3)$ bedeuten, dass Job Nr. 7 aus drei Arbeitsschritten besteht, die zunächst auf Maschine 2 und anschließend auf den Maschinen 1 und 3 erfolgen. Die benötigte Arbeitszeit für Arbeitsschritt $k$ auf Maschine $i$ wird mit $p_{ik}$ bezeichnet.

Entscheidungsvariablen

Die kontinuierliche Entscheidungssvariable $x_{ij}\geq 0$ gibt den Startzeitpunkt des Jobs $j$ auf Maschine $i$ an und die binäre Variable $z_{ijk}$ modelliert, ob Job $j$ vor Job $k$ auf Maschine $i$ durchgeführt wird ($z_{ijk}=1$) oder nicht ($z_{ijk}=0$).

Zielfunktion

Die zu minimierende Zielfunktion ist die gesamte Produktionsdauer $C_{max}$ (auch makespan), d. h. die Dauer zwischen Produktionsbeginn und dem Ende des letzten Bearbeitungsvorgangs.

Nebenbedingungen

• Zunächst wird durch die Nebenbedingung ${\textstyle x_{\sigma _{h}^{j},j}\geq x_{\sigma _{h-1}^{j},j}+x_{p_{h-1}^{j},j}}$ für alle Jobs $j\in J$ und Maschinen $i\in M$ sichergestellt, dass innerhalb eines Jobs die Reihenfolge der Arbeitsschritte eingehalten wird.
• Die Restriktionen $x_{ij}\geq x_{ik}+p_{ik}-V\cdot z_{ijk}$ und $x_{ik}\geq x_{ij}+p_{ij}-V\cdot (1-z_{ijk})$ für alle $i,j\in J$ mit $i<j$ sowie alle $i\in M$ garantieren, dass nicht zwei Jobs gleichzeitig auf derselben Maschine durchgeführt werden können. Dabei ist das $V$ eine Zahl, die ausreichend groß gewählt werden sollte. Eine mögliche Wahl ist ${\textstyle V=\sum _{j\in J,i\in M}p_{ij}}$. Die Variable $z_{ijk}$ aktiviert und deaktiviert also mit Hilfe der großen Zahl $V$ jeweils eine der beiden Ungleichungen, was als Big-M-Formulierung bezeichnet wird.
• Letztlich gilt für die Produktionsdauer $C_{max}\geq x_{\sigma _{m}^{j},j}+p_{\sigma _{m}^{j},j}$ für alle Jobs $j\in J$.

Lösungsmethoden

Das oben vorgestellte Optimierungsmodell kann für kleine bis mittlere Problemgrößen (bis etwa 30 Jobs und 30 Maschinen) exakt mit Hilfe von Branch-and-Bound-Methoden gelöst werden, die in Solvern wie CPLEX, Gurobi oder SCIP implementiert sind. Außerdem eignen sich Constraint Programming Methoden und auf Scheduling spezialisierte Verfahren wie das iSTS-SGS für die Lösung moderater Instanzen. Für größere Probleminstanzen werden Metaheuristiken und problemspezifische Heuristiken, die gute Konfigurationen berechnen, ohne eine Aussage bezüglich deren globaler Optimalität zu treffen.

Varianten

Wenn die Folge der Arbeitsgänge für jeden Auftrag identisch ist, handelt es sich um einen Flow-Shop, der ein Modell der Fließproduktion darstellt. Wird auf jeder Maschine die gleiche Folge von Aufträgen bearbeitet, handelt es sich um einen Permutations-Job Shop. Für den Fall, dass nur eine Maschine vorhanden ist, ergibt sich ein Ein-Maschinen Problem; falls die Aufträge aus nur einem Arbeitsgang bestehen, der auf einer beliebigen Maschine zu bearbeiten ist, handelt es sich um ein Maschinenbelegungsproblem mit parallelen Maschinen.

Siehe auch

• Operations Research
• Gemischt-ganzzahlige Optimierung
• Losgröße
• Fließbandabstimmung
• Betriebsmittel
• Werkzeugmaschine
• Produktionsplanung und -steuerung
• Arbeitsvorbereitung
• Produktionstechnik
• Prioritätsregel (Produktion)

Literatur

• Jacek Blazewicz et al.: Handbook on Scheduling. 2. Auflage, Springer, Berlin, Heidelberg, 2019, ISBN 978-3-319-99848-0.
• Wolfgang Domschke, Armin Scholl, Stefan Voß: Produktionsplanung: Ablauforganisatorische Aspekte. 2. Auflage, Springer, Berlin, Heidelberg 1997, ISBN 3-5406-3560-2.
• Michael L. Pinedo: Scheduling. 4. Auflage, Springer, Berlin, Heidelberg, 2012, ISBN 978-1-4899-9043-3.