Game Changer in der Produktionsplanung

von Dr. Roman Stainko

Mathematische Modelle werden überwiegend in der Wissenschaft verwendet, insbesondere der Naturwissenschaften. Klassische Einsatzgebiete sind hier die theoretische Physik oder zur Zeit sehr prominent die Epidemiologie. Aber auch, und hier natürlich besonders nah thematisch verbunden, im Gebiet von Operational Research, mit all den Fragestellungen der Unternehmensplanung und der Logistik.

Über mathematische Modelle und reale Probleme

Auf den ersten Blick mögen die Mathematik und ihre theoretischen Modelle mit der realen Welt wenig gemeinsam haben. Bereits in der Schule wird im selten beliebten Unterrichtsfach Mathematik oft die Frage gestellt: Wozu braucht man denn das? Riskiert man aber einen zweiten gezielten Blick, so lässt sich erkennen, dass mathematische Modelle hinter vielen Prozessen des Alltags und realen Fragestellungen liegen. Bloß wo? Beispielsweise: Die nagenden Überlegungen der Studenten, den kürzesten Weg zwischen den Stationen des pub crawls zu finden. Die Anstrengungen der Junggastronomin, eine ideale Preisgestaltung der Speisekarte vorzunehmen. Das Bestimmen der optimalen Mengen an Verpflegung und Getränken für das Sommerfest. Wie kann der Unternehmer Bruno Bank die Bedingungen seiner Geldgeberin erfüllen? Doch dazu etwas später. All diese Fragestellungen lassen sich mittels mathematischer Modelle beschreiben und folglich mit mathematischen Methoden berechnen und lösen.

Klarerweise werden mathematische Modelle überwiegend in der Wissenschaft verwendet, insbesondere in den Naturwissenschaften. Ganz klassisch und seit jeher in der theoretischen Physik, die mit ihren mathematischen Modellen physikalische Prozesse erklärt. Unter anderem auch in der Epidemiologie, die in letzter Zeit besonders ins Rampenlicht gerückt ist und mit passenden Modellen die Verbreitung von Viren beschreibt. Aber auch, und hier natürlich besonders nah thematisch verbunden, im Gebiet von Operational Research, mit all den Fragestellungen der Unternehmensplanung und der Logistik.

Was kann man aber nun unter einem mathematischen Modell verstehen? Ein mathematisches Modell kann als Menge an mathematischen Funktionen, Vorschriften, Gleichungen und Ungleichungen gesehen werden, die in ihrer Gesamtheit eine reale Fragestellung in der Sprache der Mathematik beschreiben. Zielführenderweise sollte das Modell berechenbar sein, sodass man es mit mathematischen Werkzeugen auch berechnen und lösen kann. Für die Modellierung, also der Schritt von der realen Fragestellung zum Modell, gibt es leider kein allgemein gültiges Vorgangsrezept. Ein paar grundlegende Richtlinien helfen aber. Was ist wesentlich, auf was kann verzichtet werden? Es ist wichtig, nur jene Aspekte zu modellieren, die für den Prozess wirklich relevant sind. Bei einem Modell handelt es sich in der Regel immer um eine Vereinfachung der realen Ausgangslage. Wie genau müssen die Antworten sein? Auch lohnt es, sich Gedanken über die verwendeten Skalen und Einheiten (z.B. Ort und Zeit) zu machen. Die Verwendung von passenden Skalen hilft, das Modell in einer berechenbaren sinnvollen Größe zu halten. Und zu guter Letzt, welche Ziele sollen erreicht werden? Es ist oft nicht offensichtlich, von einer realen Fragestellung eine klare Zielvorgabe abzuleiten, für ein gutes Modell ist dies aber unerlässlich.

Die Kunst der mathematischen Modellierung liegt nun also darin, ein möglichst einfaches Modell zu erstellen, welches die ausgehende reale Fragestellung möglichst gut beschreibt. Dabei ist der Prozess der Modellierung kein fixer Ablauf von sequenziellen Arbeitsschritten. Es gibt keine feste Vorgehensweise, keine Rezeptur die immer zum Erfolg führen wird. Vielmehr kann man den Modellierungsprozess schematisch als Kreislauf verstehen, dessen Schritte in der Regel öfters durchlaufen werden müssen.

2021 02 10 Mathematische Modellierung Abbildung

Abbildung: Modellierungsprozess als schematischer Kreislauf

Ein kleines Beispiel zum Kennenlernen – Bruno Banks Bierbank Garnituren

Bruno Bank hat ein kleines StartUp-Unternehmen ins Leben gerufen. Er will innovative Bierbank-Garnituren produzieren und verkaufen. Allerdings besitzt er keine eigene Werkstatt und muss diese für die Produktion seiner Garnituren pro Monat um 1000 € mieten, unabhängig davon, wie viele Garnituren produziert werden. Die Herstellung einer Garnitur kostet Bruno 25 €. Die Produktion einer Garnitur pro Monat würde Bruno also beispielsweise 1025 € und von 100 Garnituren 3500 € kosten. Mehr als 500 Garnituren pro Monat kann Bruno allerdings nicht herstellen, denn er arbeitet alleine. Für die produzierten Garnituren steht ein Lager zur Verfügung, wobei pro Garnitur durchschnittlich 2 € Lagerkosten pro Monat anfallen. Die fertigen Garnituren können gut gestapelt werden, somit kann von unbegrenztem Lagerraum ausgegangen werden. 10 Garnituren hat Bruno bereits gefertigt und liegen im Lager.

Aus bereits getätigten Anfragen und Bedarfsanalysen konnte Bruno prognostizierte monatliche Absatzzahlen erstellen, die im Sommer die größten Werte aufweisen:

2021 02 10 Tabelle1 Mathematische Modellierung

Tabelle 1: Bedarfsprognose für Bierbank Garnituren für das kommende Jahr

Als Geldgeberin für seine Idee mit den Bierbänken hat Bruno Bank die Investorin Gabi Geld gewinnen können, die ihn mit 37000 € unterstützen wird. Allerdings stellt sie dafür eine Bedingung an seine Geschäftsplanung. Die Produktion muss auf die Bedarfsprognose abgestimmt werden und die sich daraus ergebenden Produktionskosten müssen sich durch das zur Verfügung gestellte Geld abdecken lassen. Aber wie soll er das bloß erreichen? Bruno beschließt ein paar Produktionsszenarien aufzustellen und deren Kosten zu berechnen. Vielleicht kann er so eine kostenminimale Produktion finden. Zwei Szenarien erscheinen ihm besonders vielversprechend. Einmal soll pro Monat genau die prognostizierte Menge produziert werden (Szenario A), um das Lager nicht zu benötigen. Das andere Mal soll die gesamte jährliche Bedarfsmenge gleich am Jahresanfang produziert werden (Szenario B), um die Werkstatt dann nicht mehr zu benötigen. Für beide Produktionsszenarien berechnet Bruno die voraussichtlichen Kosten und erhält 41760 € für Szenario A und 43900 € für Szenario B. Wobei sich die Kosten aus monatlicher Lagerhaltung, Werkstattmiete und Produktion ergeben. Wie Bruno die Kosten der Werkstattmiete und der Produktion zu berechnen hat, war ihm sofort klar. Bei den Lagerkosten nimmt er schließlich an, dass sich die eingelagerte Menge vom Stand am Monatsanfang zum Stand am Monatsende gleichmäßig verändert (linearer Verlauf).

2021 02 10 Tabelle2 Mathematische Modellierung

Tabelle 2: Berechnete Kosten für Szenario A (minimale Lagernutzung)

2021 02 10 Tabelle3 Mathematische Modellierung Neu

Tabelle 3: Berechnete Kosten für Szenario B (minimale Werkstattnutzung)

Das erste Produktionsszenario A scheint bereits ganz gut zu sein, aber seiner Investorin Gabi Geld ist die geplante Produktion noch zu kostenintensiv. Gibt es jedoch noch deutlich kostengünstigere Möglichkeiten? Um wirklich sicher zu gehen, bittet er seinen alten Schulfreund und Mathematiker, Otto Optimal, um Hilfe.

Otto Optimal ist sowohl von Brunos Bierbänken als auch von seiner Fragestellung der Produktionsplanung begeistert und wird seinem alten Freund mit seinem Wissen über Optimierungsprobleme unterstützen. Auch soll er dafür eine von Brunos Garnituren bekommen. Um Brunos Produktionsproblem zu lösen, wird Otto zuerst ein mathematisches Modell der Problemstellung erstellen, welches er dann mit einem passenden Lösungsalgorithmus zur Optimalität lösen wird. So wird zweifelsfrei die optimale Lösung, bzw. das optimale Produktionsszenario, gefunden werden.

Als ersten Schritt der Modellierung überlegt sich Otto Variablen für das Modell. Gesucht sind die idealen monatlichen Produktionsmengen der Garnituren. Somit liegen 12 Zeitperioden (nT = 12) und ein Produkttyp (Bierbank Garnitur) vor. Die Produktionsmenge pro Monat soll die Variable ​\( t ∈ [ 0 , 500 ] \)​ für t = 1, … nT, beschreiben, da ja die Produktion mit 500 Stück pro Monat beschränkt ist. Weiters wird ​\( i _t ≥ 0 \)​ den Lagerstand (​\( i _0 = 10 \)​ für den initialen Lagerstand) und ​\( s _t \)​ die Verwendung der Werkstatt pro Monat bezeichnen (0 … keine Verwendung, 1 … Verwendung).
Aber wie sollen sich diese Variablen nun verhalten? Notwendige Nebenbedingungen werden in weiterer Folge das Zusammenspiel der Variablen festlegen. Als zweiten Schritt der Modellierung identifiziert Otto zwei solcher Nebenbedingungen: die Materialflussgleichung, welche die Lagerstände und deren Ab- und Zuflüsse pro Monat beschreibt, und die Werkstattungleichung, welche die Verwendung der Werkstatt beschreibt. Der Lagerstand ​\( i _t \)​ im Monat t lässt sich durch den Lagerstand des Vormonats ​\( i _{t − 1} \)​ durch die Produktion ​\( x _t \)​ und den Bedarf ​\( d _t \)​ des aktuellen Monats t charakterisieren:

\[ i_t =i _{t − 1} + x _t − d_t ~~ für~ ~t=1,\dotsc,nT. \]

Die Verwendung der Werkstatt ist notwendig sobald mindestens eine Garnitur produziert wird. Diese Eigenschaft wird durch die folgende Ungleichung beschrieben:

\[ x_t ≤ M⋅s_t \;für\; t=1,\dotsc,nT, \]

wobei M für eine obere Schranke für den Wertebereich von \( x t ∈ [ 0 , 500 ] \) steht (maximale Produktionsmenge pro Monat), welche in diesem Fall mit 500 gegeben ist.
Als letzten Schritt beschreibt Otto die Kosten der Produktion mittels einer Kostenfunktion (oder einer Zielfunktion). Die anfallenden Kosten unterteilen sich in Kosten für Produktion, Lager und Werkstatt und werden durch die Koeffizienten \( c _p , c _i \) und ​\( c _s \)​abgebildet \( ( c_p=25,c_i=2,c_s=500 ). \) Die Kosten pro Monat t lassen sich somit wie folgt beschreiben:

\[ c_p⋅x_t+c_s⋅s_t+c_i\cfrac {i_{t−1}+i_t} 2 . \]

Somit kann Otto nun das gesamte Optimierungsmodell formulieren. Es gilt, die Zielfunktion unter Einhaltung der Nebenbedingungen durch optimale Wahl der Variablen zu minimieren:

Minimiere die Zielfunktion

\[ \displaystyle\sum^{nT}_{t=1} c_p⋅x_t+c_s⋅s_t+c_i\cfrac{i_{t−1}+t_t} 2 \]

unter Einhaltung der angeführten Nebenbedingungen

\( i_0=10 \) ,

\( i_t=i_{t−1}+x_t−d_t \) für \( t=1,\cdots,nT, \)

\( x_t≤M⋅s_t \) für  \( t=1,\cdots,nT, \)

\( i_t≥0 \) für \( t=1,\cdots,nT, \)

\( x_t∈[0,500] \) für \( t=1,\cdots,nT, \)

\( s_t∈\{0,1\} \)für \( t=1,\cdots,nT. \)

Wobei die vorkommenden Variablen folgende Bedeutung haben:

Variable Bedeutung
\( i_t \) Lagerstand pro Woche ​\( t \)
\( x_t \) Werkstattbenutzung pro Woche ​\( t \)
\( s_t \) Produktionsmenge pro Woche ​\( t \)

Bei genauer Betrachtung fällt Otto auf, dass alle vorkommenden Funktionen und Gleichungen linear in den Variablen sind, welche selber binär (diskret) ​\( ( s _t ) \)​ oder stetig sind ​\( ( i_t , x_t ) \)​. Bei einem solchen Modell spricht man von einem gemischt ganzzahligen (linearen) Modell (mixed integer (linear) program … MI(L)P). Das vorliegende Modell ist eine vereinfachte Variante des in der Literatur bekannten Capacitated Lot-Sizing Problems (CLSP), welches in das Gebiet der dynamischen Losgrößenplanung fällt.

Otto löst dieses Optimierungsmodell nun mit einem ihm verfügbaren MIP-Lösungswerkzeug, welches einen branch-and-bound bzw. branch-and-cut Algorithmus realisiert. Dafür schreibt er sein mathematisches Modell in einer Modellierungssprache, damit das Lösungswerkzeug das Modell lesen und anschließend lösen kann.

int   nT = 12;      // Anzahl der Zeitbereiche (Monate)
range T  = 1 .. nT; // Indexmenge aller Zeitbereiche
range T0 = 0 .. nT; // Indexmenge aller Zeitbereiche inkl. anfänglichem Zustand (Index 0)

int setupCosts = 1000; // Mietkosten der Werkstatt pro Monat
int prodCosts  =   25; // Produktionskosten per Bierbank
int invCosts   =    2; // Lagerkosten pro Bierbank pro Monat

int inv0 =  10; // Anfänglicher Lagerstand
int M    = 500; // Maximale Produktionsmenge pro Monat

int demand[ T ] = [ 50, 50, 50, 100, 200, 200, 200, 100, 100, 50, 50, 50 ];

dvar int     x[ T ] in 0 .. M; // Variable für die produzierte Anzahl an Bierbänken pro Monat im Wertebereich 0 bis M;
dvar float+  i[ T0 ];          // Variable für den Lagerstand an Bierbänken pro Monat mit dem Wertebereich nichtnegativer reeller Zahlen
dvar boolean s[ T ];           // Variable für die Verwendung der Werkstatt pro Monat mit dem Wertebereich 0 und 1
                               // (0 .. keine Verwendung, 1 .. Verwendung)

// Zielfunktion (zu minimierender Wert):
minimize
  sum( t in T )( prodCosts * x[t] + setupCosts * s[t] ) + sum( t in T )( 0.5 * invCosts * ( i[t-1] + i[t] ) );

// Minimierung der Zielfunktion unter der Einhaltung folgender Bedingungen:
subject to {

  i[0] == inv0; // Anfangsbestand
  forall( t in T ) {
    i[t] == i[t-1] + x[t] - demand[t]; // Materialflussgleichung für alle Zeitbereiche
    x[t] <= M * s[t];                  // Werkstattungleichung für alle Zeitbereiche
  }
};

Erwartungsgemäß unterbietet der optimale Zielfunktionswert von 35860 € die Werte der beiden Produktionsszenarien von Bruno, sogar um ca. 15 %. Aber insbesondere wird durch das optimale Produktionsszenario die Vorgabe der Investorin Gabi Geld eindeutig erfüllt.

2021 02 10 Tabelle4 Mathematische Modellierung

Tabelle 4: Optimales Produktionsszenario

Stolz präsentiert Otto am nächsten Tag Bruno die optimale Lösung (wie in Tabelle 4). Bruno kann nun die Bedingung von Gabi Geld erfüllen und eine hinreichend kostengünstige und sogar kostenoptimale Planung der Bierbankproduktion vorlegen.

Abschließend treffen sich Bruno, Gabi und Otto zu einem Austausch über eine weitere Zusammenarbeit. Natürlichen genießen sie dabei ein kühles Bier auf einer von Brunos Garnituren, sehr zum Wohle.

Quellenangaben und Literaturbeispiele:

  1. H. Paul Williams, Model Building in Mathematical Programming, 5th edition, 2013, John Wiley & Sons Ltd.
  2. Laurence A. Wolsey, Integer Programming, 1998, John Wiley & Sons Inc.
  3. Yves Pochet, Laurence A. Wolsey, Production Planning by Mixed Integer Programming, 2006, Springer Science+Business Media, Inc.
  4. George L. Nemhauser, Laurence A. Wolsey, Integer and Combinatorial Optimization, 1999, John Wiley & Sons Inc.

Autor

Roman Stainko

Dr. Roman Stainko ist Mathematical Optimization Specialist in der Unit Logistics Informatics.

Diesen Beitrag mit Ihrem Netzwerk teilen: