Job Shop Scheduling

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

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, ${\displaystyle n}$ Aufträge (auch Jobs) optimal auf ${\displaystyle 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.

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.[1]

Notation

Es seien ${\displaystyle J=\{1,\ldots ,n\}}$ die Menge der zu verteilenden Jobs und ${\displaystyle M=\{1,\ldots ,m\}}$ die Menge der zur Verfügung stehenden Maschinen. Für jeden Job ${\displaystyle j}$ sei ${\displaystyle (\sigma _{1}^{j},\ldots ,\sigma _{m}^{j})}$ die Reihenfolge der Maschinen, welche durch die Abarbeitung der Arbeitsschritte benötigt werden. Beispielsweise würde ${\displaystyle (\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 ${\displaystyle k}$ auf Maschine ${\displaystyle i}$ wird mit ${\displaystyle p_{ik}}$ bezeichnet.

Entscheidungsvariablen

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

Zielfunktion

Die zu minimierende Zielfunktion ist die gesamte Produktionsdauer ${\displaystyle 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 ${\displaystyle j\in J}$ und Maschinen ${\displaystyle i\in M}$ sichergestellt, dass innerhalb eines Jobs die Reihenfolge der Arbeitsschritte eingehalten wird.
• Die Restriktionen ${\displaystyle x_{ij}\geq x_{ik}+p_{ik}-V\cdot z_{ijk}}$ und ${\displaystyle x_{ik}\geq x_{ij}+p_{ij}-V\cdot (1-z_{ijk})}$ für alle ${\displaystyle i,j\in J}$ mit ${\displaystyle i<j}$ sowie alle ${\displaystyle i\in M}$ garantieren, dass nicht zwei Jobs gleichzeitig auf derselben Maschine durchgeführt werden können. Dabei ist das ${\displaystyle 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 ${\displaystyle z_{ijk}}$ aktiviert und deaktiviert also mit Hilfe der großen Zahl ${\displaystyle V}$ jeweils eine der beiden Ungleichungen, was als Big-M-Formulierung bezeichnet wird.[2]
• Letztlich gilt für die Produktionsdauer ${\displaystyle C_{max}\geq x_{\sigma _{m}^{j},j}+p_{\sigma _{m}^{j},j}}$ für alle Jobs ${\displaystyle 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.[1] Außerdem eignen sich Constraint Programming Methoden und auf Scheduling spezialisierte Verfahren wie das iSTS-SGS[3] 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.

Einzelnachweise

1. Wen-Yang Ku, J. Christopher Beck: Mixed Integer Programming models for job shop scheduling: A computational analysis. In: Computers & Operations Research. Band 73, September 2016, ISSN 0305-0548, S. 165–173, doi:10.1016/j.cor.2016.04.006 (utoronto.ca [PDF; abgerufen am 18. Januar 2024]). 
2. Nathan Sudermann-Merx: Einführung in Optimierungsmodelle. 2023, doi:10.1007/978-3-662-67381-2 (springer.com [abgerufen am 19. Januar 2024]). 
3. J. Christopher Beck, T. K. Feng, Jean-Paul Watson: Combining Constraint Programming and Local Search for Job-Shop Scheduling. In: INFORMS Journal on Computing. Band 23, Nr. 1, Februar 2011, ISSN 1091-9856, S. 1–14, doi:10.1287/ijoc.1100.0388. Fehler in Vorlage:Literatur – *** Parameterproblem: Dateiformat/Größe/Abruf nur bei externem Link