CLSP: Dynamisches Losgrößenmodell mit Kapazitätsbeschränkungen

Die als "Capacitated Lotsizing Problem" (CLSP) bezeichnete Modellformulierung beschreibt das erste Losgrößenmodell, in dem sowohl dynamische Periodenbedarfe als auch die beschränkte Kapazität einer Ressource berücksichtigt werden. Damit gelingt es erstmals, realistische, d.h. machbare Produktionspläne zu erzeugen. Bedarfsmengen einer Periode, die mangels verfügbarer Kapazität nicht "just-in-time" produziert werden können, werden auf Lager produziert. Wegen der knappen Kapzität wird also Lagerbestand aufgebaut.

Das Modell CLSP erhält man, wenn man das dynamische Einprodukt-Losgrößenmodell (SLULSP) auf die Betrachtung mehrerer Produkte ausweitet und dabei Kapazitätsbeschränkungen berücksichtigt. Es handelt sich um ein sog. Makroperiodenmodell ("big-bucket model"). Das heißt, das Modell ist so formuliert, daß in einer Periode prinzipiell beliebig viele Produkte produziert werden können, sofern die Kapazität dazu ausreicht.

Annahmen:

  • mehrere Produkte können pro Periode produziert werden ("big bucket"-Modell)

  • dynamische, periodenbezogene Nachfragemengen

  • eine oder mehrere Maschinen bzw. Ressourcen (in den meisten Modellierungsvarianten und Lösungsverfahren wird nur eine Maschine betrachtet); Achtung: Wenn mehrere Ressourcen betrachtet werden, dann wird angenommen, daß diese gleichzeitig an einem Auftrag arbeiten, z.B. eine Maschine, ein Werker, und ein spezielles Werkzeug. Mehrere Ressourcen, die nacheinander einen Auftrag bearbeiten, werden so nicht erfaßt. Für diesen Fall muß man ein mehrstufiges kapazitiertes Losgrößenmodell verwenden.

  • endliche Produktionsgeschwindigkeit, d.h. für jedes Produkt wird eine Stückbearbeitungszeit vorgegeben

  • keine Übernahme eines Rüstzustandes aus der Vorperiode: falls ein Produkt in einer Periode produziert wird, fallen auch Rüstzeiten bzw. Rüstkosten an; das gilt auch dann, wenn in mehreren aufeinanderfolgenden Perioden nur ein einziges Produkt produziert wurde

Es gibt verschiedene Modellvarianten des CLSP, die sich vor allem durch die verwendeten Variablen unterscheiden. Die einfachste Form lautet wie folgt:

$\mathrm{Minimiere } Z= \displaystyle{\sum_{k=1}^K \sum_{t=1}^T } \big( {s_k\cdot \gamma_{kt}}+{h_k\cdot y_{kt} \big)$

unter den Nebenbedingungen

$ y_{k,t-1}+q_{kt}-y_{kt}=d_{kt} \qquad {k=1,2,\ldots,K;\;t=1,2,\ldots,T} $

$ \displaystyle{\sum_{k\in {K}_j}} \big(tb_k\cdot q_{kt}+ tr_k\cdot \gamma _{kt}\big) \leq b_{jt} \qquad {j=1,2,\ldots,J;\;t=1,2,\ldots,T} $

$ q_{kt}-M\cdot \gamma _{kt} \leq 0 \qquad {k=1,2,\ldots,K;\;t=1,2,\ldots,T} $

$ q_{kt}, y_{kt} \geq 0 \qquad {k=1,2,\ldots,K;\;t=1,2,\ldots,T} $

$ \gamma_{kt} \in \{0,1\} \qquad {k=1,2,\ldots,K;\;t=1,2,\ldots,T} $

Symbole:
$t$ Periodenindex
$k$ Produktindex
$j$ Ressourcenindex
${K}_j$ Menge der Produkte, die an Ressource $j$ bearbeitet werden
$d_{kt}$ Primärbedarf des Produkts $k$ in Periode $t$
$tb_{k}$ Produktionszeit pro ME des Produkts $k$
$tr_{k}$ Rüstzeit für Produkt $k$
$b_{jt}$ Kapazität der Ressource $j$ in Periode $t$
$q_{kt}$ Produktionsmenge des Produkts $k$ in Periode $t$
$y_{kt}$ Lagerbestand des Produkts $k$ am Ende der Periode $t$
$\gamma_{kt}$ binäre Rüstvariable für Produkt $k$ in Periode $t$

Diese Formulierung ist zwar leicht verständlich. Sie hat aber den Nachteil, daß eine LP-Rleaxation (d.h. wenn man das Modell unter Vernachlässigung der Binäreigenschaft der Rüstvariablen löst) nur eine sehr schlechte untere Schranke des optimalen Zielfunktionswertes des Modells liefert. Diese untere Schranke ist z.B. in einem Branch&Bound-Verfahren zu schwach, so daß man mit ihrer Hilfe den Lösungsraum nicht ausreichend einschränken kann. Es sind daher verschiedene alternative Modellformulierungen für die betrachtete Problemstellung entwickelt worden, die höhere untere Schranken liefern und mit wesentlich kürzerer Rechenzeit auskommen. Eine wesentlich bessere Formulierung basiert auf den Standortmodell (siehe hierzu Tempelmeier (2012)).

Mittelgroße CLSP-Probleme lassen sich heute in vertretbarer Rechenzeit mit Standard-Software zur mathematischen Optimierung exakt lösen. Denn vielen Solver erkennen die Struktur eines dynamischen Losgrößenproblems und können diese durch für den Nutzer nicht erkennbare Reformulierungen ausnutzen.

Das CLSP kann um parallele Maschinen erweitert werden. Auch reihenfolgeabhängige Rüstzeiten und/oder eine Rüstressource mit beschränkter sowie Beschreänkungen der Lagerdauern lassen sich berücksichtigen.

Da eine CLSP-Lösung nur die Produktionsmengen pro Periode festlegt, bestehen hinsichtlich der Reihenfolge, in der die Produkte in einer Periode produziert werden, noch beträchtliche Freiheitsgrade. Das kann bei Störungen und anderen stochastischen Einflüssen von Vorteil sein.

Siehe auch ...

Literatur

Günther, H.-O. und Tempelmeier, H. (2016). Produktion und Logistik - Supply Chain and Operations Management. 12. Aufl., Norderstedt: Books on Demand.
Tempelmeier, H. (2017), Produktionsplanung in Supply Chains. 5. Aufl., Norderstedt: Books on Demand.