Capacitated Lot-Sizing Problem

Annahmen

Das CLSP geht dabei von folgenden Annahmen aus:

• einstufige, Mehrprodukt-Produktion
• endliche Produktionsgeschwindigkeit
• zeitlich veränderliche Nachfrage (dynamische Nachfrage)
• die Produktionsmittel (Maschinen) stehen nur für begrenzte Zeit innerhalb der einzelnen Perioden zur Verfügung. Die verfügbare Kapazität ist im Allgemeinen in jeder Periode unterschiedlich
• für das Auflegen eines Loses fallen fixe Rüstkosten an
• die Lagerkosten sind proportional zur gelagerten Menge
• endlicher Planungszeitraum

Mathematische Beschreibung

Eine mathematische Beschreibung sieht wie folgt aus: Mengen:

• ${\displaystyle {\mathcal {J}}=j_{1},j_{2},\dots }$ Menge aller Produkte
• ${\displaystyle {\mathcal {T}}=t_{1},t_{2},\dots }$ Menge aller Perioden

Parameter:

• ${\displaystyle b_{jt}}$ Bedarf von Produkt ${\displaystyle j\in {\mathcal {J}}}$ in Periode ${\displaystyle t\in {\mathcal {T}}}$. Die Produktionsmenge einer bestimmten Periode kann zur Befriedigung in dieser Periode verwendet werden.
• ${\displaystyle p_{j}}$ Fertigungsgeschwindigkeit von Produkt ${\displaystyle j\in {\mathcal {J}}}$
• ${\displaystyle f_{j}}$ fixe Rüstkosten je Rüstvorgang von Produkt ${\displaystyle j\in {\mathcal {J}}}$
• ${\displaystyle c_{j}}$ Lagerhaltungskostensatz für die am Ende einer Periode noch lagerne Menge des Produkts ${\displaystyle j\in {\mathcal {J}}}$
• ${\displaystyle \kappa _{t}}$ Kapazität in Periode ${\displaystyle t\in {\mathcal {T}}}$
• ${\displaystyle \kappa _{j}^{p}=1/p_{j}}$ Bedarf an Kapazität zur Herstellung einer Mengeneinheit von Produkt ${\displaystyle j\in {\mathcal {J}}}$

Variablen:

• ${\displaystyle Z_{jt}}$ ist gleich 1 falls das Produkt ${\displaystyle j\in {\mathcal {J}}}$ in Periode ${\displaystyle t\in {\mathcal {T}}}$ gefertigt wird und 0 wenn nicht
• ${\displaystyle L_{jt}}$ Lagerbestand von Produkt ${\displaystyle j\in {\mathcal {J}}}$ am Ende der Periode ${\displaystyle t\in {\mathcal {T}}}$
• ${\displaystyle Q_{jt}}$ Losgröße von Produkt ${\displaystyle j\in {\mathcal {J}}}$ in Periode ${\displaystyle t\in {\mathcal {T}}}$
• ${\displaystyle K}$ Der Zielfunktionswert der alle Rüst- und Lagerkosten vereint

Zielfunktion: ${\displaystyle {\text{minimize}}\quad K=\sum _{j\in {\mathcal {J}}}\sum _{t\in {\mathcal {T}}}(f_{j}Z_{jt}+c_{j}L_{jt})}$

unter den Nebenbedingungen

${\displaystyle L_{j,t-1}+Q_{jt}-L_{jt}=b_{jt}\qquad \forall j\in J,t\in {\mathcal {T}}|t>1}$ „Lagerbilanzgleichung“

${\displaystyle Q_{jt}\leqq Z_{jt}\sum _{\tau \in {\mathcal {T}}}b_{j\tau }\qquad \forall j\in {\mathcal {J}},t\in {\mathcal {T}}}$ stellt sicher, dass die Losgröße nur dann in die Berechnung eingeht wenn ein Los aufgelegt wird.

${\displaystyle \sum _{j\in {\mathcal {J}}}\kappa _{j}^{p}Q_{jt}\leqq \kappa _{t}\qquad \forall t\in {\mathcal {T}}}$

${\displaystyle L_{jt},Q_{jt}\geqq 0\qquad \forall j\in {\mathcal {J}},t\in {\mathcal {T}}}$

${\displaystyle Z_{jt}\in \{0,1\}\qquad \forall j\in {\mathcal {J}},t\in {\mathcal {T}}}$

${\displaystyle L_{j0}=L_{j|{\mathcal {T}}|}=0}$

Es unterscheidet sich dabei vom bekannten Wagner-Whitin-Modell durch die Einbeziehung mehrerer Produkte, beschränkte Produktionskapazität und endliche Fertigungsgeschwindigkeit. Das CLSP gehört zu den NP-schweren Problemen und lässt sich exakt durch Branch-and-Bound-Algorithmen lösen. Daneben existieren auch Heuristiken.