Capacitated Lot-Sizing Problem

Modelle mit dynamischer Losgrößenermittlung

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.

Beschreibung des Modells

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:

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

Parameter:

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

Variablen:

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

Zielfunktion: ${\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

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

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

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

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

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

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