Home

CLSP: ABC-Heuristik

Dynamische Losgrößenplanung mit Kapazitätsbeschränkungen: ABC-Heuristik

Es wird das einstufige Problem der Mehr-Produkt-Losgrößenplanung (CLSP - Capacitated Lot Sizing Problem) bei dynamischem Bedarf und mit Kapazitätsbeschränkungen betrachtet. Dabei handelt es sich um ein Losgrößenmodell, in dem sowohl dynamische Periodenbedarfe als auch die beschränkte Kapazität einer Ressource berücksichtigt werden. Bedarfsmengen einer Periode, die mangels verfügbarer Kapazität nicht "just-in-time" produziert werden können, werden auf Lager produziert. Wegen der knappen Kapazität wird also auf Vorrat produziert und folglich Lagerbestand aufgebaut.

Es wird die ABC-Heuristic von Maes eingesetzt. Alternativ kann die exakte Lösung mit einem Standard-MIP-Solver bestimmt werden.

Folgende Annahmen liegen dem Modell zugrunde:

Die einfachste Form des mathematische Optimierungsmodells für dieses Problem sieht wie folgt aus:

$\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}} tb_k\cdot q_{kt} \leq b_{t} \qquad {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:

$d_{kt}$ Bedarfsmenge des Produkts k in Periode t
$s_k$ Rüstkostensatz des Produkts k
$h_k$ Lagerkostensatz des Produkts k
$tb_k$ Stückbearbeitungszeit des Produkts k
$b_t$ Kapazität der Ressource in Periode t

Zur Lösung dieses Modells sind in diesem Modul mehrere Verfahren verfügbar:

"ABC-Heuristik" von Maes und Van Wassenhove

Dies ist ein Verfahren, das iterativ aus einer Matrix von Bedarfsmengen eine Matrix von Produktionsmengen erzeugt. Das Verfahren ist detailliert bei Tempelmeier (2020a) beschrieben. Als Auswahlkriterium können die Periodendurchschnittkosten, die Stückkosten und die Lagerkostensätze verwendet werden. Als Strategie für den Aufbau des Produktionsplanes können die Ost-Strategie und die Süd-Strategie eingesetzt werden.

Falls beim Übergang von einer Planungsperiode tau zu nächsten Periode tau+1 ein Kapazitätsfehlbedarf in den Periode tau+1, tau+2, ... festgestellt wird, müssen ein noch nicht eingeplante zukünftige Bedarfsmenge eines order mehrerer Produkte vorgezogen werden. Es wird zunächst versucht, ein vorhandenes Los in Periode tau zu vergrößern. Die Reihenfolge, in der die Produkte dabei betrachtet werden, richtet zu nach den Lagerkosten pro benötigter Kapazitätseinheit. Wenn die Vergrößerung eines solchen Loses nicht möglich ist, dann werden die Produkte nach ihren Rüstkosten sortiert und ein neues Los für das Produkt mit den geringsten Rüstkosten eingeplant.

Nach Eingabe der Daten und Auswahl der einzusetzenden Verfahrensvariante wird die Heuristik gestartet. Das Ergebnis mit den ausgeführten Zwischenschritten wird protokolliert:

Exakte Lösung des mathematischen Optimierungsmodells)

Hier gibt es drei Möglichkeiten: 

Online-Optimierung mit dem Neos-Server und Gurobi

Man kann für jedes Problem auch die optimale Lösung bestimmen lassen, indem man die AMPL-Schnittstelle des online verfügbaren Neos-Servers nutzt. Im Produktions-Management-Trainer wählt man unter Optionen -> AMPL-Datei (Neos) erzeugen. Es erscheint dann ein Dateiauswahlfenster, in dem man den Namen der zu erzeugenden AMPL-Dateien festlegt. Hat man z.B. "CLSP" angegeben, dann werden die AMPL-Dateien CLSP.MOD, CLSP.DAT und CLSP.RUN erzeugt. Als nächstes öffnet man die folgende Internet-Seite in einem Browser:

https://neos-server.org/neos/solvers/milp:Gurobi/AMPL.html

Auf dieser Seite sind in der "Web Submission Form" die Modelldatei (CLSP.MOD), die Datendatei (CLSP.DAT) und die Kommandodatei (CLSP.RUN) anzugeben. Dann betätigt man den Button "Submit to Neos" und nach einiger Zeit wird die optimale Lösung des Problems angezeigt.

Optimierung auf dem lokalen PC mit der Studentenversion von AMPL und CPLEX

Unter https://ampl.com/try-ampl/download-a-free-demo/#windows kann man die Studentenversion von AMPL herunterladen: entweder ampl.mswin32.zip oder ampl.mswin64.zip.

In dieser ZIP-Datei befindet sich ein Unterverzeichnis, das auf den PC kopiert werden muß. Im Produktions-Management-Trainer wählt man die Option AMPL-Datei (lokal) erzeugen. Es erscheint ein Dateiauswahldialog, in dem man das AMPL-Verzeichnis angeben sollte. In diesem Verzeichnis startet man dann die Datei "ampl.exe" und gibt man den Befehl "include clsp.run;" ein. Dieser Befehl startet die Lösung des Problems. Die Ergebnisse werden in der Datei CLSP.AUS gespeichert.

Für Python-Nutzer: Optimierung mit Python auf dem lokalen PC (nur falls Python-MIP auf dem Rechner installiert ist) 

Wählt man den letzten Menüpunkt "Optimierung mit Python aus" aus, dann wird das mathematische Optimierungsmodell in einer für Python-MIP lesbaren Form erzeugt und gelöst. Dabei können auch Rüstzeiten berücksichtigt werden. Die optimale Lösung wird dann in gleicher Weise wie nach Einsatz der Heuristik angezeigt. Wurde die optimale Lösung nicht gefunden, dann wird dies angezeigt.

Für Beispiel 1 könnte das so aussehen.

Falls Python nicht installiert ist, dann wird der letzte Menüpunkt nicht angezeigt.

Achtung: Alle Produktionsmengen im Ergebnisprotokoll sind in der Dimension "Kapazitätseinheiten" angegeben. Dies ist von Bedeutung, wenn die Stückbearbeitungszeit eines Produkts ungleich 1 ist.

Literatur:

- Tempelmeier (2020a)

Datenschutz | © 2020 POM Prof. Tempelmeier GmbH | Imprint