Job Shop Scheduling

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.
• 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}$.