Dynamische Losgrößenmodelle mit Kapazitätsbeschränkungen

Inhaltsverzeichnis

1 Einführung

2 Losgrößen in der Produktionsplanung
2.1 Modellformulierung für das einstufige Losgrößenproblem
2.2 Lösungsverfahren
2.3 Komplikationen des Modellansatzes

3 Einstufige kapazitierte Losgrößenplanung
3.1 CLSP-Modell: Modellformulierung
3.2 Lösungsansätze
3.3 Das Dixon-Verfahren
3.4 Das modifizierte Dixon-Verfahren
3.5 Das Dekompositionsverfahren von Stadtler
3.6 Das Verfahren von Maes

4 Losgrößen bei kapazitierter mehrstufiger Fertigung
4.1 Das MLCLSP-Modell
4.2 Konzept des systemweiten Lagerbestandes
4.3 Reformulierung des Modells
4.3.1 Bildung der Lagrange-Relaxation
4.3.2 Anpassung an die Kürzeste-Wege-Formulierung
4.3.3 Anpassung an das Standortplanungsproblem
4.4 Praktische Anwendbarkeit

5 Numerische Untersuchung
5.1 Umsetzung des Verfahrens von Maes in Matlab
5.2 Implementierung des Verfahrens von Dixon
5.3 Untersuchung des Laufzeitverhaltens

6 Schlussbetrachtung

Literaturverzeichnis

Symbolverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

Abbildungsverzeichnis

Abbildung 1 Modelldarstellung als Kürzeste-Wege-Problem

Abbildung 2 Kürzeste-Wege-Problem mit expliziten Rüstkosten

Abbildung 3 Modelldarstellung als Standortproblem

Abbildung 4 Erstellung eines zulässigen Produktionsplans in einer Periode

Abbildung 5 Flussdiagramm des Dixon-Verfahrens

Abbildung 6 Dekomposition des Zeitraums

Abbildung 7 Dekomposition mit überlappendem Planungsfenster und Relaxation

Abbildung 8 Erzeugnisstrukturen bei mehrstufiger Fertigung

Abbildung 9 Berücksichtigung von Kapazitätsrestriktionen

Abbildung 10 Darstellung des Losgrößenproblems als Kürzeste-Wege-Problem

Abbildung 11 Darstellung als Standortproblem

Abbildung 12 Vergleich von Sukzessiv und Simultanplanung

Abbildung 13 Laufzeit des modifizierten Dixon-Verfahrens

Tabellenverzeichnis

Tabelle 1 Laufzeitverhalten der Verfahren in Abhängigkeit vom Planungshorizont

1 Einführung

Abbildung in dieser Leseprobe nicht enthalten

ie Problematik der Losgrößenplanung genießt eine sonderbare Stellung in der betriebswirtschaftlichen Literatur: wissenschaftliche Arbeiten auf diesem Gebiet zählen zur Grundlagenforschung, der Bereich der Produktionsprogrammplanung gilt als Königsdisziplin^[1]. Dabei kann man das zu Grunde liegende Problem weder als neu noch als praxisfremd bezeichnen: bereits 1913 entwickelte Ford W. Harris die Economic Order Quantity -Formel – einen Ansatz zur Bestimmung der kostenminimalen Bestellmenge, der auch zur Losgrößenbestimmung geeignet ist. Heute – fast 100 Jahre später – existiert immer noch kein praktikables Verfahren für ein Problem, dessen optimale Lösungen nur für triviale Probleminstanzen existieren: das mehrstufige Losgrößenproblem mit beschränkten Ressourcen.

In dieser Arbeit stellen wir zwei Modellierungskonzepte vor, die die grundlegenden Annahmen der klassischen Losgrößenformel fallen lassen: beide gehen von dynamischer Nachfrage und Kapazitätsrestriktionen aus und bilden mit optionalen Erweiterungen die meisten praxisrelevanten Alternativen ab, ohne allerdings eine Lösung für sie zu liefern. Sie stellen also lediglich den ersten Schritt in die Richtung der simultanen Planung dar, die im Stande wäre, das Losgrößenproblem auf globaler Ebene optimal zu lösen.

Auch wenn wir später feststellen werden, dass das Problem in dieser Form nicht lösbar ist, liefert die Modellformulierung mehrere Möglichkeiten, dennoch durchführbare Produktionspläne zu erstellen. Den Ausgangspunkt liefert uns hierbei die einstufige unkapazitierte Losgrößenplanung, die wir im zweiten Abschnitt beschreiben.

Im Abschnitt 3 wird nun die Betrachtung der Ressourcen im Modell integriert und mehrere Reformulierungen werden vorgestellt, die zur Lösung der Problematik herangezogen werden können. Anschließend werden mehrere Lösungsverfahren vorgestellt, deren Effizienz über der in der Praxis dominierenden sukzessiven Vorgehensweise liegt.

Der Abschnitt 4 geht einen Schritt weiter und stellt ein Modell für die mehrstufige Fertigung vor. In Analogie zum Abschnitt 3 werden auch hier einige Lösungsmöglichkeiten aufgezeichnet und ihre praktische Anwendbarkeit kritisch hinterfragt. Im darauf folgenden Abschnitt ziehen wir einen Vergleich der Leistungsfähigkeit von einigen vorgestellten Lösungsansätzen, deren Implementierung im Rahmen dieser Seminararbeit erfolgte, um einen Gütevergleich zwischen heuristischen und mathematischen Methoden zu erhalten. Im letzten Abschnitt werden die Ergebnisse der Arbeit zusammengefasst und hierzu kritisch Stellung genommen.

Wir fangen jedoch mit der Bedeutung der Losgrößenplanung in der Produktionsplanung an und gehen im nächsten Abschnitt auf die Probleme bei der Bestimmung ihrer Einflussgrößen ein.

2 Losgrößen in der Produktionsplanung

Abbildung in dieser Leseprobe nicht enthalten

ie praktische Bestimmung der Rüstkosten und ihrer Zusammensetzung wird oft dadurch erschwert, dass die Opportunitätskosten, die den entgangenen Nutzen in Form von für Rüstvorgänge reservierten Maschinenzeiten darstellen, im Falle eines Mehrsproduktunternehmens nicht ohne Weiteres durch den entgangenen Deckungsbeitrag des jeweiligen Produktes zu quantifizieren sind, sondern aufgrund von Interdependenzen zwischen einzelnen Produkten nur simultan bestimmt und optimiert werden können.

Ein weiteres Problem bei der Losbildung eines Endproduktes oder eines übergeordneten Erzeugnisses entsteht durch die Notwendigkeit der frühzeitigen Fertigstellung von untergeordneten Erzeugnissen, deren Losgrößenbestimmung ihrerseits aufgrund der Mehrstufigkeit der Erzeugnisstruktur mit Wechselwirkungen verbunden sind, die im Rahmen der Optimierung berücksichtigt werden müssen. Im Falle eines dynamischen Bedarfes würde die Veränderung der Periodenbedarfsmengen eines Produktes eine Anpassung der optimalen Losgröße zur Folge haben, was gleichzeitig zu neuen Losgrößenproblemen auf untergeordneten Stufen führen würde.

Man geht davon aus, dass sich mehrstufige Modelle aufgrund ihrer Komplexität in einstufige Modelle zum Beispiel mit Branch&Cut -Verfahren zerlegen und separat optimieren lassen. Darüberhinaus liefern uns die Methoden zur Lösung von einstufigen Losgrößenproblemen Optimierungsansätze, die die Optimierung der mehrstufigen Fertigung eines Mehrproduktunternehmens ermöglichen oder diese um zahlreiche Fassetten erweitern. Das ist die Rechtfertigung für das Erwähnen der einstufigen unkapazitierten Losgrößenmodelle in unserer Seminararbeit.

2.1 Modellformulierung für das einstufige Losgrößenproblem

Bei einem Einprodukt-Unternehmen mit Losfertigung und variablen Periodenbedarfen^[2] lässt sich das Problem der Losgrößenplanung wie folgt darstellen. Für einen Planungshorizont von Abbildung in dieser Leseprobe nicht enthalten Perioden liegen prognostizierte Nettobedarfsmengen von Abbildung in dieser Leseprobe nicht enthalten mit Abbildung in dieser Leseprobe nicht enthalten vor.

Der Lagerbestand Abbildung in dieser Leseprobe nicht enthalten beträgt am Anfang und am Ende des Planungszeitraum Null oder entspricht optional dem Mindestlagerbestand. Die Produktion erfolgt auf einer Maschine mit unbeschränkter Kapazität, die Beschaffungs- und Produktionszeiten sind losgrößenunabhängig und werden im Modell entsprechend nicht berücksichtigt. Man geht von vollständiger und termingerechter Befriedigung des geplanten Bedarfes aus (Tempelmeier, 2006 S. 139).

Abbildung in dieser Leseprobe nicht enthalten

Bei der Zielfunktion handelt es sich um eine Summe, die aus den von der Auflagehäufigkeit abhängigen Rüstkosten, aus den von der Losgröße abhängigen Lagerkosten und aus den variablen Produktionskosten besteht. Die Nebenbedingung setzt die Bedarfsmenge mit der Produktionsmenge einer Periode in Beziehung, berücksichtigt dabei aber auch den Anfangs- und Endlagerbestand der jeweiligen Perioden^[3].

Die im definierte Binärvariable Abbildung in dieser Leseprobe nicht enthalten nimmt den Wert von 1 an, wenn in Periode Abbildung in dieser Leseprobe nicht enthalten ein Los aufgelegt wird. Die Nebenbedingung schränkt zum einen die maximale Losgröße auf den Gesamtbedarf über alle folgenden Perioden Abbildung in dieser Leseprobe nicht enthalten ein und zwingt zum anderen die VariablenAbbildung in dieser Leseprobe nicht enthalten den Wert 1 anzunehmen, falls eine positive Losgröße aufgelegt wird.

In der Modellformulierung wurden keine Ressourcen und keine Kapazitäten erfasst, so dass die so ermittelten Losgrößen eventuell nicht produziert werden können. Die groben Zeitvorgaben lassen sich jedoch durch die im Rahmen der Ablaufplanung vorhandene Freiheitsgrade z.B. durch Änderung der Produktreihenfolge der einzelnen Aufträge an einer Maschine und damit durch eine mögliche Verminderung der Rüstzeiten unter Umständen doch einhalten.

Dieses Problem wurde von Wagner und Within (Wagner, et al., 1958) durch Dynamische Programmierung mit Abbildung in dieser Leseprobe nicht enthalten-Aufwand^[4] gelöst^[5]. Sie kamen zur Erkenntnis, dass bei einer optimalen Lösung nur dann produziert wird, wenn der Lagerbestand null ist, d.h. bei einer kostenminimalen Lösung niemals teilweise aus dem Lager und teilweise durch die aktuelle Produktion befriedigt wird (Rossi, 2003 S. 26). Von diesem Optimum ausgehend lässt sich eine Regel ableiten, nämlich dass die kostenminimale Losgröße eine ganzzahlige Summe aus Bedarfen von verschiedenen, aufeinanderfolgenden Perioden sein muss, was eine schärfere Formulierung des Problems ermöglicht.

Eine der Reformulierungen dieses Problems stellt das Shortest Route Problem (SRP) bzw. Kürzeste-Wege-Problem dar: am Anfang jeder Periode wird entschieden, Bedarfe welcher künftigen Perioden zu produzieren sind. Losgrößen, die die entsprechenden Bedarfsmengen decken, werden durch Pfeile repräsentiert, die die verschiedene Periodenbedarfe – als Knoten dargestellt – verbinden.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1 Modelldarstellung als Kürzeste-Wege-Problem^[6]

Eine zulässige Lösung des Problems in der Kürzesten-Wege-Formulierung entspricht einem vollständigen Weg vom Anfangs- bis zum Endknoten, bei der optimalen Lösung ist die Summe aus Rüst-, Lager- und Produktionskosten minimal. Die Einschränkung des Lösungsraumes durch Überführung des betrachteten Losgrößenproblems liefert neben der höheren Effizienz in der Datenverarbeitung auch die Möglichkeit der Berücksichtigung von Kapazitäten, Verfallsdaten oder der maximalen Lagerdauer.

Im Rahmen des Verfahrens lassen sich auch weitere Parameter einbauen oder - wie die Abbildung 2 zeigt - Rüstkosten explizit berücksichtigen. Diese Vorgehensweise werden wir später auch auf das mehrstufige Modell übertragen.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2 Kürzeste-Wege-Problem mit expliziten Rüstkosten

Als eine weitere Modellformulierung ist das Plant-Location-Problem^[7] (PLP) bzw. Standortproblem zu nennen, für das Lösungsverfahren existieren. In diesem Fall werden die Zeitpunkte der Produktion in Form von Standorten dargestellt, die mittels Produktion in Periode Abbildung in dieser Leseprobe nicht enthaltendie Nachfrage in Periode Abbildung in dieser Leseprobe nicht enthalten decken können. Die Menge Abbildung in dieser Leseprobe nicht enthalten stellt also die Menge der zum Zeitpunkt Abbildung in dieser Leseprobe nicht enthaltenherzustellenden Produkte dar, um die Nachfrage in Abbildung in dieser Leseprobe nicht enthalten decken zu können. Die Zielfunktion minimiert die Gesamtkosten und hat die Vorteile einer schärferen Formulierung des Modells mit einer ganzzahligen Lösung.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3 Modelldarstellung als Standortproblem^[8]

Eine weitere Möglichkeit den Lösungsraum des gemischt-ganzzahligen Programms einzuschränken liegt in einer schärferen Formulierung des Problems, indem man zusätzliche Ungleichungen einführt, die die Anzahl von zulässigen Lösungen weiter einschränken.

Die durch Hinzunahme von Ungleichungen entstandenen Schnittebenen des einstufigen Problems können auf das strukturell ähnlich aufgebaute mehrstufige Problem übertragen werden, wobei die Fehlmengenrestriktionen verschiedener Stufen entsprechend berücksichtigt werden müssen.

2.2 Lösungsverfahren

Für das dynamische einstufige Losgrößenproblem eines Einprodukt-Unternehmens existieren nur wenige exakte Verfahren und mehrere heuristische Ansätze. Der klassische Lösungsweg besteht in der Anwendung des bereits erwähnten Verfahren von Wagner und Within sowie seine Modifikationen^[9] im Rahmen der dynamischen Programmierung. Obwohl der Wagner-Within-Algorithmus bei effizienter Implementierung keinen großen Aufwand erfordert, findet er in der Praxis kaum Anwendung (Neumann, 1996 S. 50).

Insbesondere die fehlende Möglichkeit über den Planungshorizont „hinauszudenken“, sowie die mangelnde Fähigkeit der Integration in die rollierende Planung führen dazu, dass heuristische Verfahren in der Praxis nach wie vor eine große Rolle spielen (Hansmann, 2006 S. 307.).

Bei den Heuristiken handelt es sich vorwiegend um Eröffnungsverfahren zur Bestimmung einer zulässigen Lösung. Hierzu zählt die Heuristik von Silver und Meal, das Verfahren der gleitenden wirtschaftlichen Losgröße (Least unit Cost-Verfahren), sowie das Stückperiodenausgleichsverfahren. Außerdem existiert eine Menge von Verbesserungsverfahren, die, von einer zulässigen Lösung ausgehend, durch Verschiebung oder Vertauschung von Bedarfsmengen zeitlich benachbarter Lose eine Verbesserung der Ausgangssituation erreichen (Domschke, et al., 1997 S. 130).

2.3 Komplikationen des Modellansatzes

Die Berücksichtigung von Rabatten, Kapazitätsrestriktionen und variablen Fertigungskosten bis hin zur rollierenden Planung im Wagner-Within-Modell kann die Komplexität des Models sehr stark erhöhen. Doch die Anwendbarkeit dieser Einproduktmodelle, die Spezialfälle des kapazitierten Mehrproduktmodells sind, bleibt bestehen, auch wenn diese Verfahren in Standard-Software-Systemen zur Produktionsplanung- und Steuerung (PPS-Systeme) in nicht problemadäquater Weise für die Bestimmung von Losgrößen in mehrstufigen Erzeugnisstrukturen eingesetzt werden (Tempelmeier, 2006 S. 160).

Insbesondere, wenn es sich um Produkte handelt, die gemeinsamen Ressourcen beanspruchen, was Restriktionen zur Folge hat, entstehen systematische Planungsfehler bzw. nicht umsetzbare Produktionspläne. Im folgenden Abschnitt gehen wir nun zu Modellierungsmöglichkeiten für dynamische Mehrproduktprobleme über, bei denen Konkurrenzbeziehungen zwischen einzelnen Produkten um vorhandene Produktionskapazitäten bestehen.

3 Einstufige kapazitierte Losgrößenplanung

Abbildung in dieser Leseprobe nicht enthalten

ine wesentliche Einschränkung der bisher vorgestellten Modelle für die Bestimmung von Losgrößen liegt darin, dass vorhandene und zumindest in kurzfristiger Betrachtung limitierte Ressourcen in Form von Maschinen und Arbeitskräften nicht entsprechend berücksichtigt werden. Dabei können Restriktionen in Form von konstanten oder in der Zeit variablen Kapazitäten auftreten.

Im Folgenden gehen wir von konstanten, also zeitinvarianten Kapazitäten, die für die Herstellung mehrerer Produkte herangezogen werden können. Dieser Modelltyp wird in der englischsprachigen Literatur als Capazitated Lot-Sizing Problem (CLSP) bezeichnet. Man spricht hier von einem big-bucket -Modell, da viele Produkte in einer Periode produzierbar sind. Eine Fertigungsreihenfolge wird dabei nicht ermittelt, so dass dieses Modell zur kurz- bzw. mittelfristigen Planung von Losgrößen herangezogen werden kann. Anstelle der Verwendung zur Planung von Produktionslosen kann das Modell auch zur Bildung von Bestellaufträgen herangezogen werden (Reith-Ahlemeier, 2002 S. 34).

Neben Verknüpfungen hinsichtlich der Ressourcen können auch die Mehrstufigkeit der Fertigung oder zusätzliche Nebenbedingungen als Grund für die Notwendigkeit gemeinsamer Planung auftreten. Mit dieser Problematik beschäftigen wir uns im Abschnitt 4.

3.1 CLSP-Modell: Modellformulierung

Die im Abschnitt 2.1 vorgestellte Modellformulierung wird nun auf mehrere Produkte mit dynamischer Nachfrage erweitert. Bei Mehrproduktmodellen wird im Allgemeinen davon ausgegangen, dass zwischen einzelnen Produkten Interdependenzen der Art vorliegen, dass die Reduktion des Modells auf mehrere Einprodukt-Modelle nicht möglich ist.

Das Planungsproblem besteht darin, den Nettobedarf Abbildung in dieser Leseprobe nicht enthalten der Produkte Abbildung in dieser Leseprobe nicht enthalten in jeder Periode Abbildung in dieser Leseprobe nicht enthalten bereitzustellen ohne dabei den Rahmen der vorhandenen Kapazitäten Abbildung in dieser Leseprobe nicht enthaltender Ressource Abbildung in dieser Leseprobe nicht enthalten in Periode Abbildung in dieser Leseprobe nicht enthalten zu sprengen. Die Produkte können in jeder Periode mit Lagerbestand Abbildung in dieser Leseprobe nicht enthaltengelagert werden, wobei der Anfangslagerbestand Abbildung in dieser Leseprobe nicht enthalten null ist. In jeder Periode wird die Produktionsmenge Abbildung in dieser Leseprobe nicht enthalten durch die zur Verfügung stehende Kapazität begrenzt; für die Produktion einer Mengeneinheit des Produktes Abbildung in dieser Leseprobe nicht enthalten an Ressource Abbildung in dieser Leseprobe nicht enthalten wird eine Bearbeitungszeit von Abbildung in dieser Leseprobe nicht enthalten benötigt.

Beim Auflegen eines Loses entstehen Rüstkosten in Höhe von Abbildung in dieser Leseprobe nicht enthalten einerseits und Rüstzeiten in Höhe von Abbildung in dieser Leseprobe nicht enthalten andererseits. Die Zielfunktion minimiert die Summe aus Rüst-, Lager- und Produktionskosten (Tempelmeier, 2006 S. 162):

Abbildung in dieser Leseprobe nicht enthalten

Die Lagerbilanzgleichung stellt sicher, dass die geforderten Bedarfe der Planungsperiode für alle Produkte auch tatsächlich gedeckt werden. Die Kapazitätsbedingung schränkt die aus Rüst- und Produktionszeiten eingeplante Ressourcenbeanspruchung auf die verfügbare Kapazität ein. Mit der Restriktion wird dafür gesorgt, dass beim Auflegen eines Loses auch gerüstet wird. Daraus ergibt sich eine maximale Produktionsmenge von:

[...]

^[1] Zitate aus Vorlesungen zur Materiallogistik (Prof. Dr. Stadtler) sowie Produktion (Dr. Boysen) an der Universität Hamburg

^[2] Dieses Problem wird im Allgemeinen als Single -Level Uncapacitated Lot Sizing Problem (SLULSP) bzw. als Wagner-Within-Problem bezeichnet

^[3] Der Lageranfangsbestand einer Periode entspricht dabei dem Endbestand der Vorperiode.

^[4] Bei O-Notation handelt es sich um ein Maß für die rechnerische Komplexität bei Realisierung eines Algorithmus auf einem Computer. In diesem Fall handelt es sich um quadratischen Aufwand, der typisch für Vektormultiplikation ist.

^[5] Es wurden bereits Algorithmen vorgestellt, die diese Problem mit einer Komplexität von also mit quasilinearem Aufwand lösen.

^[6] In Anlehnung an (Rossi, 2003 S. 28)

^[7] In der Literatur werden auch andere Bezeichnungen wie Warehouse Location-Problem (WLP) verwendet, je nach dem, ob es sich um die Optimierung der Bestellmenge oder der Losgröße handelt (Domschke, et al., 1997 S. 119).

^[8] In Anlehnung an (Rossi, 2003 S. 30)

^[9] Eine weitere modifizierte Modellformulierung und ihre Lösung mittels dynamischer Optimierung stellt das Verfahren von Wagelmanns dar (Wagelmans, et al., 1992).