Capacitated Lot-Sizing Problem

Das Capacitated Lot-Sizing Problem (CLSP) ist ein Modell der dynamischen Losgrößenplanung.

Es geht von mehreren Produkten aus, für die eine begrenzte Produktionskapazität vorhanden ist. Zu ermitteln ist, in welcher Periode welche Lose aufgelegt werden sollen und wie groß diese sein sollen. Die Bedarfe der einzelnen Perioden werden dabei als bekannt angenommen. Eine Reihenfolge, in der die einzelnen Lose innerhalb der Perioden zu fertigen sind, wird nicht ermittelt.

Im Gegensatz zum Discrete Lot-Sizing and Scheduling Problem (DLSP) ist es möglich, in einer Periode mehrere Lose aufzulegen. Es eignet sich daher eher für die mittelfristige Planung, während das DLSP zur kurzfristigen Feinplanung geeignet ist, da es auch eine Reihenfolge der Lose ermittelt.^[1]

Das CLSP geht dabei von folgenden Annahmen aus:^[2]

• 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

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.^[3]

1. ↑ Domschke, Scholl, Voß: Produktionsplanung: Ablauforganisatorische Aspekte. 2. Auflage, Springer, Berlin, 1997, S. 133.
2. ↑ Domschke, Scholl, Voß: Produktionsplanung: Ablauforganisatorische Aspekte. 2. Auflage, Springer, Berlin, 1997, S. 134.
3. ↑ Domschke, Scholl, Voß: Produktionsplanung: Ablauforganisatorische Aspekte. 2. Auflage, Springer, Berlin, 1997, S. 133–146.