Mehr ...

SIULSP: Single-Item Uncapacitated Lotsizing Problem (Wagner-Whitin-Problem)

Das dynamische Losgrößenmodell SIULSP (Single-Item Uncapacitated Lotsizing Problem) wurde von Wagner und Whitin vorgeschlagen und heißt deshalb auch Wagner-Whitin-Modell. Das dem Modell zugrunde liegende Problem heißt Wagner-Whitin-Problem. Bei diesem Modell geht es darum, für eine gegebene Zeitreihe von deterministischen, periodenbezogenen Nachfragemengen die kostenminimalen Losgrößen in den einzelnen Perioden zu bestimmen. Kapazitätsbeschränkungen werden in diesem einfachen Modell nicht berücksichtigt. Die Häufigkeit der Lose wird über die Rüstkosten gesteuert.

Annahmen:

  • ein Produkt
  • dynamische Nachfragemengen (periodenbezogen, Tage, Wochen usw.)
  • keine Kapazitätsbeschränkung

Dieses Problem wird auch als Wagner-Whitin-Problem bezeichnet.

Die einfachste mathematische Formulierung lautet:

$\mathrm{Minimiere }\; Z=\displaystyle{\sum_{t=1}^T \big( {h\cdot y_t} + { s\cdot \gamma _t} \big)}$

unter den Nebenbedingungen:

$y_{t-1}+q_t-y_t=d_t \qquad {t=1,2,\ldots,T}$

$q_t-M\cdot \gamma _t\le 0 \qquad {t=1,2,\ldots,T}$

$q_t\geq 0 \qquad {t=1,2,\ldots,T}$

$y_t\geq 0 \qquad {t=1,2,\ldots,T}$

$\gamma _t\in \left\{ {0,\,1} \right\} \qquad {t=1,2,\ldots,T}$

Symbole:

$d_t$ Nettobedarfsmenge in Periode $t$
$h$ Lagerkostensatz
$M$ große Zahl (M muß größer als die maximal mögliche Losgröße sein)
$s$ Rüstkostensatz
$T$ Länge des Planungszeitraums
$q_t$ Losgröße in Periode $t$
$y_t$ Lagerbestand am Ende der Periode $t$
$\gamma_t$ binäre Rüstvariable

Bei genauer Betrachtung des Modells SIULSP stellt man fest, daß es sich um den auf ein isoliert betrachtetes Produkt bezogenen Ausschnitt des Modells MLCLSP handelt. Der Produktindex $k$ sowie die Kapazitätsbeschränkung wurden gestrichen. Die Sekundärbedarfsmengen und die Vorlaufzeitverschiebung wurden ebenfalls vernachlässigt. Sie werden bei Anwendung des Dispositionsstufenverfahrens außerhalb der Losgrößenplanung erfaßt.

Zur Lösung des Modells SIULSP wurde von Wagner und Whitin ein Verfahren der dynamischen Optimierung vorgeschlagen:

Modul Dynamische Losgrößenplanung SIULSP: Exakte Lösung im Produktions-Management-Trainer:

PMT

Das Modell SIULSP hat eine spezielle Struktur, die es gestattet, es auf das Problem der Bestimmung des kürzesten Weges in einem Netzwerk zurückzuführen. Es ist daher z.B. mit dem Verfahren von Dijkstra (sieh hierzu Domschke et al. (2015)) sehr leicht exakt zu lösen. Das wird im folgenden Beispiel für ein Produkt mit folgenden  Periodenbedarfen veranschaulicht. Das Beispiel stammt aus Tempelmeier (2020a), Abschnitt C.1.2.1.

Periode 1 2 3 4 5 6
Menge $d_t$ 20 80 160 85 120 100

Der Rüstkostensatz beträgt $s=500$ und der Lagerkostensatz ist $h=1$. Zur Anwendung des Kürzeste-Wege-Algorithmus von Dijkstra wird zunächst für jede Periode $t=(1,2,...,6)$ und eine Dummy-Periode $T=7$ ein Knoten erzeugt. Dann wird jeder Knoten $t=(1,2,...,6)$ durch einen Pfeil mit allen anderen Knoten $j>t$ verbunden. Das sieht dann so aus:

Ein Pfeil vom Knoten $t$ zum Knoten $j$ bedeutet, daß in Periode $t$ die gesamte Nachfragemenge der Perioden $t$ bis $j-1$ produziert wird. Die "Entfernungsangaben" an den Pfeilen in diesem "Wegenetz" sind die jeweiligen Rüst- und Lagerkosten. Für den Pfeil von $1$ nach $3$ gilt z.B.: $580 = 500 + 1 \cdot 80$.

Gesucht ist jetzt der kostengünstigste bzw. kürzeste Weg vom Knoten $1$ bis zum Knoten $T=7$. Das Dijkstra-Verfahren wird in den folgenden Bildern veranschaulicht. Dabei ist $d_i$ die kürzeste Entfernung vom Startknoten $1$ zum Knoten $i$ und $r_i$ der direkte Vorgänger von $i$ auf dem kürzesten Weg vom Startknoten zum Knoten $i$. $d_i$ und $r_i$ werden iterativ aktualisiert.

Start:  Startknoten = 1; MK={1}; $d_1=0$, alle anderen Entfernungen $d_j= \infty$

Iteration 1:

$h=1$.

Neue Entfernung $d_2=500$
Neue Entfernung $d_3=580$
Neue Entfernung $d_4=900$
Neue Entfernung $d_5=1155$
Neue Entfernung $d_6=1635$
Neue Entfernung $d_7=2135$
Menge MK: { 2 3 4 5 6 7 }

Die aktuell kürzesten Entfernungen sind in den folgenden Bildern jeweils an den Knoten notiert.

Iteration 2:

Nächstgelegener Knoten: $h=2$
Endgültig kürzeste Entfernung $d_2 =  500$
Betrachte alle direkten Nachfolger von $h=2$:
$j=3$: Bisherige Entfernung $d_3=580$
$j=4$: Bisherige Entfernung $d_4=900$
$j=5$: Bisherige Entfernung $d_5=1155$
$j=6$: Bisherige Entfernung $d_6=1635$
$j=7$: Bisherige Entfernung $d_7=2135$; neue Entfernung $d_7=2090$, da Weg von 1 über 2 nach 7 kürzer: $2135 > 500+ 1590$
Menge MK: { 3 4 5 6 7 }

Iteration 3:

Nächstgelegener Knoten: $h=3$.

Endgültig kürzeste Entfernung $d_3 = 580$
Betrachte alle direkten Nachfolger von $h=3$:
$j=4$: Bisherige Entfernung $d_4=900$
$j=5$: Bisherige Entfernung $d_5=1155$
$j=6$: Bisherige Entfernung $d_6=1635$; neue Entfernung $d_6=1405$,  da Weg von 1 über 3 nach 6 kürzer:
$1635 > 580+ 825$
$j=7$: Bisherige Entfernung $d_7=2090$; neue Entfernung $d_7=1705$, da Weg von 1 über 3 nach 7 kürzer:
$2090 > 580+ 1125$

Menge MK: { 4 5 6 7 }

Iteration 4:

Nächstgelegener Knoten: $h=4$
Endgültig kürzeste Entfernung $d_4 = 900$
Betrachte alle direkten Nachfolger von h=4:
$j=5$: Bisherige Entfernung $d_5=1155$
$j=6$: Bisherige Entfernung $d_6=1405$
$j=7$: Bisherige Entfernung $d_7=1705$
Menge MK: { 5 6 7 }

Iteration 5:

Nächstgelegener Knoten: $h=5$
Endgültig kürzeste Entfernung $d_5 = 1155$
Betrachte alle direkten Nachfolger von $h=5$:
$j=6$: Bisherige Entfernung $d_6=1405$
$j=7$: Bisherige Entfernung $d_7=1705$
Menge MK: { 6 7 }

Iteration 6:

Nächstgelegener Knoten: $h=6$
Endgültig kürzeste Entfernung $d_6 = 1405$
Betrachte alle direkten Nachfolger von $h=6$:
$j=7$: Bisherige Entfernung $d_7=1705$
Menge MK: { 7 }

Iteration 7:

Nächstgelegener Knoten: $h=7$
Endgültig kürzeste Entfernung $d_7 = 1705$

Menge MK ={}. Ende des Verfahrens.

Optimale Lösung: Der kostenminimale Weg von 1 nach 7 führt über 3, d.h. produziere in den Perioden 1 und 3. Die Losgrößen sind dann $q_1=100$ und $q_3=465$. Die Kosten dieser Lösung betragen 1705.

Durch die spezielle Kostenstruktur ist $h$ hier jeweils der Index der nächsten Periode. Das ist in einem allgemeinen Kürzeste-Wege-Modell nicht der Fall. Siehe hierzu das Beispiel von Domschke et al. (2015).

Modul Kürzeste-Wege-Modell im Produktions-Management-Trainer:

PMT

Das Modell SIULSP bildet die Grundlage für zahlreiche Losgrößenheuristiken, die in den in der Praxis verbreiteten ERP-/PPS-Systemen und Advanced-Planning-Systemen eingesetzt werden. Typische Losgrößenheuristiken sind:

  • Verfahren von Silver und Meal
  • Verfahren von Groff
  • Stückkostenverfahren (Verfahren der gleitenden wirtschaftlichen Losgröße)
  • Stückperiodenausgleichsverfahren (Part-Period-Verfahren)

Bei den Heuristiken geht man i.d.R. so vor, daß man in einer Periode $\tau$ ein Los auflegt und dieses so lange vergrößert, bis sich ein Optimierungskriterium, dessen Wert sich zunächst verbessert hat, wieder verschlechtert.

Bei der Silver-Meal-Heuristik z.B. beschreibt das Optimierungskriterium die durchschnittlichen Kosten pro Periode, wenn in Periode $\tau$ ein Los aufgelegt wird, das alle Periodenbedarfe bis einschließlich Periode $t$ deckt:

$c_{\tau t}=\frac{s+h\cdot \displaystyle{\sum_{l=\tau }^t} {(l-\tau )\cdot d_l}}{t-\tau +1}\qquad \tau \le t $

Modul Dynamische Losgrößenplanung SIULSP: Heuristiken im Produktions-Management-Trainer:

PMT

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. (2020a). Production Analytics - Modelle und Algorithmen zur Produktionsplanung, 6. Aufl., Norderstedt: Books on Demand.
Tempelmeier, H. (2020b). Analytics in Supply Chain Management und Produktion - Übungen und Mini-Fallstudien. 7. Aufl., Norderstedt: Books on Demand.
Domschke, W., Drexl, A., Klein, R., und Scholl, A. (2015), Einführung in Operations Research. 9. Aufl., Berlin: Springer.
Briskorn, D. (2020), Operations Research. Berlin:Springer.