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

Die Aufgabe der Losgrößenplanung ist es, festzulegen, wie viele Mengeneinheiten eines Produkts auf einmal, d.h. mit einem Rüstvorgang, produziert werden sollen und wann dies geschehen soll. Dieses Problem wird seit mehr als 100 Jahren in der Literatur diskutiert. In der ursprünglichen Modellierung des sog. klassischen Losgrößenproblems wird von einer konstanten und kontinuierlich auftretenden Nachfrage(-rate) ausgegangen. Dies führt zu dem bekannten Sägezahn-ähnlichen Verlauf des Lagerbestands, der die Grundlage für die Berechnung der Lagerkosten bildet. Da sich das wirkliche Geschäftsleben aber nicht auf einer kontinuierlichen Zeitachse abspielt, sondern in Monate, Wochen, Arbeitstage, Schichten, Stunden oder Minuten eingeteilt ist, und da Zinskosten in der Finanzwelt nicht kontinuierlich, sondern i.d.R. täglich berechnet werden, wurde von Wagner und Whitin im Jahre 1958 eine Modellformulierung mit einer diskreten Zeitachse und periodenbezogenen Nachfragemengen vorgestellt. Ein Losgrößenmodell mit diskreter Zeitachse bezeichnet man als dynamisches Losgrößenmodell. Dadurch wird es auch möglich, im Zeitablauf sich verändernde Nachfragemengen (auch die Periodennachfragemenge Null) zu berücksichtigen. Diese Abbildung des Nachfrageverlaufs korrespondiert mit den in der Praxis eingesetzten Prognoseverfahren.

Das Modell von Wagner und Whitin unterstellt unbeschränkte Kapazitäten. Bei dieser Annahme entsteht ein Losgrößenproblem allerdings erst dann, wenn mit der Produktion eines Loses (oder der Bestellung einer Produktmenge bei einem Lieferanten) fixe Kosten verbunden sind. Ist das nicht der Fall, dann kann man einfach nachfragesynchron (just-in-time oder in amerikanisch L4L wie lot-for-lot) unter Vermeidung von Lagerkosten produzieren und hat folglich auch kein Optimierungsproblem. 

In der industriellen Praxis spielen Fixkosten aber oft keine oder nur eine untergeordnete Rolle - sie sind oft nicht einmal bekannt.  Beispielsweise läßt sich kaum beziffern, wie hoch die mit einem Rüstvorgang an einer Maschine verbundenen Fixkosten sind, wenn der Rüstvorgang durch einen Mitarbeiter durchgeführt wird, der ausreichend Zeit hat und ohnehin fest angestellt ist. Stattdessen ist mit der Vorbereitung einer Maschine für die Produktion normalerweise eine Rüstzeit verbunden, während der die Maschine nicht produktiv arbeitet, sondern nur abwartet, bis sie mit der Produktion beginnen kann. Je häufiger gerüstet wird, umso mehr produktiv nutzbare Zeit (Kapazität) der Maschine geht verloren. Das ist kein Problem, wenn die Kapazitätsauslastung so niedrig ist, daß es nie zu einer Engpaßsituation kommt.

Ist die Kapazität aber nicht unbegrenzt verfügbar, dann muß dies  in der Losgrößenplanung berücksichtigt werden. Versucht man nun, Kapazitätsüberschreitungen infolge zu häufigen Rüstens dadurch zu vermeiden, daß man jeden Rüstvorgang mit Rüstkosten "bestraft", dann führt dies nur dann zum optimalen Produktionsplan bzw. zu optimalen periodenbezogenen Losgrößen, wenn man die periodenbezogenen optimalen Strafkosten kennt. Diese hängen aber davon ab, wie knapp die Kapazität in den einzelnen Perioden ist. Bei dynamischer, d.h. periodenbezogener Nachfrage, ändert sich die Knappheit der Kapazität aber von Periode zu Periode aufgrund der Schwankungen der Nachfragemengen und in Abhängigkeit von den eingeplanten Losgrößen. Das heißt, um die optimalen Losgrößen bestimmen zu können, muß man die optimalen Rüstkosten kennen. Diese kennt aber aber erst, wenn man die optimalen Losgrößen bestimmt hat und man sagen kann, in welchen Perioden die Kapazität knapp ist.

Bei beschränkter Kapazität kommen wir mit den beiden genannten unkapazitierten Losgrößenmodellen - unabhängig davon, ob die Zeitachse kontinuierlich oder diskret modelliert wird - also nicht weiter. Das wurde in der betriebswirtschaftlichen Forschung schon vor einigen Jahrzehnten erkannt und hat zu einer großen Anzahl unterschiedlicher dynamischer Losgrößenmodelle geführt, die die begrenzten periodenspezifischen Kapazitäten einer betrachteten Ressource mit berücksichtigen.

All diese Modelle bilden im Prinzip dasselbe Problem ab, nämlich die ursprünglich von Ford W. Harris bereits 1913 formulierte Frage "How many parts to make at once" (Factory, The Magazine of Management, Volume 10, Number 2, February 1913, pp. 135–136, 152). Die dynamischen Losgrößenmodelle unterscheiden sich nun vor allem dadurch, wie grob sie die Zeitachse modellieren. Je kleiner die Periodeneinteilung ist, umso genauer kann man das tatsächliche Produktionsgeschehen, also nicht nur die Losgrößen, sondern u.U. auch die Reihenfolgen, in der die produktspezifischen Lose bearbeitet werden, bestimmen. Die Wahl der Periodenlänge wurde in der Vergangenheit auch von der numerischen Lösbarkeit der resultierenden Modelle bestimmt. Denn das Ziel der Modellierungsanstrengungen ist es ja, gemischt-(kontinuierlich)- ganzzahlige Modelle (sog. Mixed-Integer-Modelle, MIP-Modelle) zu finden, die mit einem kommerziellen Standard-Solver in vertretbarer Rechenzeit gelöst werden können.

Je feiner die Periodeneinteilung ist, desto mehr binäre Entscheidungsvariablen enthält ein solches gemischt-ganzzahliges Optimierungsmodell. Dies hat einen erheblichen Einfluß auf die Rechenzeit, die für die optimale Lösung verbraucht wird. 

In Abgängigkeit davon, ob in einer Periode beliebig viele Lose eingeplant werden können oder nicht, unterscheidet man Makroperioden-Modelle (big-bucket models) von Mikroperioden-Modellen (small-bucket models). Bei einem Makroperioden-Modell können beliebig viele Lose in einer Periode produziert werden (bis die Kapazität erschöpft ist). Im einfachsten Fall kann man aus der optimalen Lösung eines Makroperiodenmodells nur die Losgrößen entnehmen. Eine Aussage über die Produktionsreihenfolge der Lose innerhalb einer Makroperiode wird nicht getroffen. (Anmerkung: Allerdings gibt es Varianten von Makroperioden-Modellen, bei denen zumindest das erste und das letzte in einer Periode produzierte Produkt festgelegt werden, so daß man dann periodenübergreifende Rüstzustände berücksichtigen kann.)

Mit einem Mikroperioden-Modell dagegen wird neben den Losgrößen auch die Produktionsreihenfolge festgelegt. Das ist aber nur möglich, wenn man die Periodenlängen so festlegt, daß man die Kontrolle über den Produktionsbeginn und das Produktionsende eines jeden Loses hat. So kann man z.B. eine sehr feine Periodeneinteilung wählen und mit Hilfe von Entscheidungsvariablen in dem Losgrößenmodell festlegen, daß in jeder Periode genau ein Produkt produziert wird. Eine andere Modellvariante geht von der Vorstellung aus, daß in jeder Periode höchstens einmal umgerüstet wird. In diesem Fall können maximal zwei Produkte produziert werden: Ein Produkt am Periodenanfang (mit Übernahme des Rüstzustands der Maschine aus der Vorperiode) und ein Produkt, das nach einer Umrüstung der Maschine am Ende der Periode produziert wird.

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. Das CLSP ist ein Makroperioden-Modell. 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, Makroperioden-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-Relaxation (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 dem Standortmodell (siehe hierzu Tempelmeier (2020)).

Mittelgroße CLSP-Probleme lassen sich heute in vertretbarer Rechenzeit mit Standard-Software zur mathematischen Optimierung exakt lösen. Denn viele 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 Kapazität sowie Beschränkungen der Lagerdauern der Produkte 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.

In den letzten Jahren sind auch Varianten des CLSP für den Fall stochastischer Nachfragemengen entwickelt worden.

Siehe auch ...

Literatur

Günther, H.-O. und Tempelmeier, H. (2020). Supply Chain Analytics - Operations Management und Logistik. 13. Aufl., Norderstedt: Books on Demand.
Tempelmeier, H. (2020). Production Analytics - Modelle und Algorithmen zur Produktionsplanung, 6. Aufl., Norderstedt: Books on Demand.