Heuristiken zur Lösung von Losgrößenproblemen

Inhaltsverzeichnis

1. EINLEITUNG

2. BEGRIFFSERLÄUTERUNGEN
2.1. LOSGRÖßENPROBLEME
2.2. DER BEGRIFF DER HEURISTIK

3. AUSGEWÄHLTE MODERNE HEURISTIKEN
3.1. A LAGRANGEAN-BASED HEURISTIC FOR DYNAMIC MULTILEVEL MULTIITEM CONSTRAINED LOTSIZING WITH SETUP TIMES
3.1.1. Einführung
3.1.2. Problemformulierung
3.1.3. Beschreibung der heuristischen Lösungsmethode
3.1.4. Tests und deren erreichte Ergebnisse
3.1.5. Fazit
3.2. MULTILEVEL LOT SIZING WITH SETUP TIMES AND MULTIPLE CONSTRAINED RESSOURCES: INTERNALLY ROLLING SCHEDULES WITH LOT-SIZING WINDOWS
3.2.1. Einführung
3.2.2. Entscheidungsproblem und Modellformulierung
3.2.3. Ablaufpläne mit Planungsfenstern
3.2.4. Modellformulierung der Untermodelle
3.2.5. Berücksichtigung von Rüstzeiten
3.2.6. Errechnete Ergebnisse
3.2.7. Fazit
3.3. HEURISTIKEN MIT FORTSCHREITENDEN INTERVALLEN
3.3.1. Einführung
3.3.2. Das Mehr-Produkt-Modell mit Joint and Item-dependent Setup Costs (JIS)
3.3.3. Beschreibung der Heuristik
3.3.4. Ablauf der Lösungssuche
3.3.5. Tests und deren Ergebnisse
3.4. STEUERUNG EINER HEURISTIK ZUR LOSGRÖßENPLANUNG UNTER KAPAZITÄTSRESTRIKTIONEN MIT HILFE EINES PARALLELEN GENETISCHEN ALGORITHMUS
3.4.1. Ausgangspunkt dieser Heuristik
3.4.2. Das Modell (CLSPL)
3.4.3. Die Heuristik von Haase
3.4.4. Der genetische Algorithmus
3.4.5. Tests und Ergebnisse

4. ANHANG
4.1. LITERATURVERZEICHNIS
4.2. ABBILDUNGSVERZEICHNIS

1. Einleitung

Eine der wichtigsten Aufgaben im Produktionsbetrieb stellt die Produktionsprozessplanung dar. Sie legt die zeitliche, mengenmäßige und räumliche Durchführung der Produktion fest und kann in die Arbeitsschritte Losgrößenbestimmung, Durchlauf- und Kapazitätsterminie- rung sowie Reihenfolgeplanung und Feinterminierung gegliedert werden. Im Rahmen der Losgrößenbestimmung, wird entschieden, ob es sich lohnt Fertigungsaufträge gleicher Erzeugnisse zusammenzufassen und unmittelbar nacheinander zu fertigen. Die Menge bzw. Anzahl an Erzeugnissen, welche dabei von einer Produktiveinheit ohne Rüstvorgänge in einem Zug gefertigt werden, wird hierbei Los oder auch Losgröße genannt.¹ Je größer das Los gewählt wird, desto weniger muss beispielsweise eine Maschine umgerüstet werden. Das hat den Effekt, dass hierbei Rüstkosten 2 eingespart werden können. Allerdings ist zu beachten, dass durch die Losbildung eine Lagerung der Zwischen- als auch Endprodukte notwendig wird, da nicht alle Einheiten gleich im Anschluss weiterbearbeitet bzw. ausgeliefert werden können. Im Gegenzug zu den sinkenden Rüstkosten steigen daher die Lagerkosten bzw. Lagerhaltungskosten² mit zunehmender Größe eines Loses. Der gleiche Effekt kann bei der Bestellung eines Gutes beobachtet werden. Wird eine Bestellmenge größer gewählt, so verteilen sich die bestellfixen Kosten auf mehr Artikel. Dies führt zur Reduzierung der Kosten pro bestellter Einheit (Stückkosten). Zusätzlich können Mengen- und Sonderrabatte weitere positive Kostenwirkungen hervorrufen. Unumgänglich wird dabei wiederum die Lagerung, da kaum alle Güter gleichzeitig weiterverarbeitet oder von der Wareneingangskontrolle überprüft werden können. Somit wird den Kostenvorteilen einer Bestellmengenerhöhung entgegengewirkt.

Es ergeben sich aus dieser Situation also Probleme für die Kostenoptimierung im Betrieb. Die Losgrößenbildung verfolgt nun das Ziel, wirtschaftliche Mengen zu bestimmen, durch welche die entstehenden Gesamtkosten minimal sind.³

Aus diesem Anlass wurden in der Vergangenheit sehr viele Modelle und Algorithmen entwickelt und entsprechend der Betriebssituation angepasst. Auch in der betrieblichen Software der Gegenwart sind einfache Modelle integriert, um die Planung zu erleichtern. Nicht allzu selten sind diese Modelle jedoch noch zu wenig angepasst an die individuellen Bedingungen im Betrieb.⁴

Viele Probleme der Realität sind auch viel zu komplex, um sie in einfache Modelle zu fassen oder mit exakten Verfahren zu lösen. Aus diesem Grund wurden Verfahren entwickelt, die Näherungslösungen bieten und sowohl unabhängig von der Struktur der Realität als auch anpassungsfähig sind. Durch diese Komplexitätsreduktion können mit bedeutend weniger Rechenaufwand akzeptable bis gute Ergebnisse erreicht werden.

Aufgabe dieser Arbeit soll es sein, einen Überblick über die bedeutendsten Losgrößenprob- leme sowie deren Lösungsmethoden zu verschaffen. Die bekanntesten Lösungsverfahren sollen erwähnt und gegliedert werden. Da zu diesen Themen genügend Literatur zur Verfügung steht, wird im Rahmen dieser Arbeit lediglich auf weiterführende Quellen verwiesen. Vor allem neuere heuristische Lösungsansätze sollen hingegen ausführlicher dargestellt werden.

2. Begriffserläuterungen

2.1. Losgrößenprobleme

Zunächst soll eine Abgrenzung der verschiedenen Losgrößenprobleme in Anlehnung an Tempelmeier⁵ erfolgen.

Grundlegend wird zwischen statischen und dynamischen Losgrößenproblemen unterschieden. Statische Modelle gehen von einem unendlichen Planungszeitraum aus und betrachten den Bedarfsverlauf eines Produktes als gleich bleibend, während für dynamische Modelle meist ein endliches Planungsintervall und zeitlich veränderliche Bedarfe kennzeichnend sind. In dieser Arbeit sollen die statischen Losgrößenprobleme jedoch keine Beachtung finden, da sie in der Realität relativ wenig vorkommen.⁶

Dynamische Losgrößenprobleme können sowohl im Einprodukt-Fall als auch im Mehrprodukt-Fall betrachtet werden. Zur Lösung des dynamischen Einprodukt- Losgrößenproblems lassen sich stellvertretend die nachfolgenden Verfahren anführen:

- Least Unit Cost
- Part-Period-Verfahren
- Silver-Meal-Verfahren
- Grenzkostenverfahren von Groff
- Losgrößen-Saving-Verfahren

1.) Bei dem least unit cost-Verfahren (Verfahren der gleitenden wirtschaftlichen Losgröße) wird die Produktionsmenge in einer Periode solange erhöht, wie die durchschnittlichen Kosten je Mengeneinheit verringert werden. Es wird also für jede Planungsperiode das lokale Minimum der Stückkosten gesucht.
2.) Das part-period-Verfahren (Stückperiodenausgleichsverfahren) ist ein Kostenaus- gleichsverfahren, bei dem die Bedarfsmengen aufeinander folgender Perioden so lange zu einem Los zusammengefasst werden, bis die Rüstkosten in etwa den Lagerkosten entsprechen.
Auf Eigenschaften des klassischen Losgrößenmodells basierende Verfahren sind das Silver-Meal-Verfahren und das Groff-Verfahren.
3.) Die Annahme, dass bei optimaler Losgröße die durchschnittlichen Kosten pro Zeiteinheit ihr Minimum erreichen, soll bei der Anwendung des Silver-Meal-Verfahrens auf die dynamische Situation übertragen werden.
4.) Das Groff-Verfahren hingegen basiert auf der Eigenschaft, dass bei optimaler Losgröße Grenz-Rüstkosten und Grenz-Lagerkosten gleich sind.
5.) Die grundlegende Idee des Losgr öß en-Saving-Verfahrens, welches ein heuristisches Verfahren darstellt, ist die Übertragung eines Verfahrens zur Tourenplanung auf das Losgrößenproblem.

Im für die Realität bedeutsameren Mehrprodukt-Fall lassen sich einstufige und mehrstufige Verfahren unterscheiden. Die folgenden Verfahren können zur Lösung des einstufigen dynamischen Mehrprodukt-Losgrößenproblems herangezogen werden:

- Das Verfahren von Dixon basiert auf dem Verfahren von Silver und Meal. Es ist auf eine Ressource beschränkt und vernachlässigt die Rüstkosten.
- Voraussetzung bei der Anwendung des ABC-Verfahrens von Maes, ist die Beantwor- tung der Fragen A, B und C. Die Lösgrößenplanung erfolgt dann aufgrund der unterschiedlichen Kombinationen von Antworten auf die drei Fragen.
- Eine endliche Menge von produktbezogenen Produktionsplänen mit jeweils unterschiedlichen Produktionszyklen zu erzeugen und diese als Entscheidungsalternati- ven in einem Optimierungsmodell zusammenzufassen ist die Grundidee des Verfahrens von Bahl.
- Eine andere Lösungsmöglichkeit ist die Verwendung des zeitlichen Dekompositionsver- fahrens von Stadtler. Dabei wird der aus einer bestimmten Anzahl von Perioden bestehende Planungszeitraum in kürzere Planungsfenster unterteilt, wobei sich das dadurch verkleinerte Losgrößenproblem für jedes Planungsfenster exakt lösen lässt.
- Die Heuristiken mit fortscheitenden Intervallen lösen einstufige Probleme ähnlich dem Verfahren von Stadtler in mehreren Stufen über fortschreitende Berechnungsintervalle.

Die mehrstufigen dynamischen Mehrprodukt-Lösgrößenprobleme lassen sich noch einmal in Probleme ohne Kapazitätsbeschränkungen und Probleme mit Kapazitätsbeschränkungen unterteilen.

Ein Verfahren zur Lösung dynamischer Losgrößenprobleme ohne Kapazitätsbeschrän- kungen ist das Verfahren von Heinrich. Heinrich geht davon aus, dass ein Produkt mehrere Nachfolger in der Erzeugnisstruktur haben kann. Das Verfahren besteht aus zwei Phasen. In der ersten Phase wird mit Hilfe eines heuristischen Verfahrens ein dem dynamischen Problem sehr ähnliches mehrstufiges stationäres Losgrößenproblem betrachtet. Die Lösung dieses Ersatzproblems dient dann in der zweiten Phase der Erzeugung eines dynamischen Produktionsplans.

Eine andere Möglichkeit ist die Anwendung einer Lagrange-Heuristik. Schwierige Nebenbedingungen eines Modells werden entfernt und mit Hilfe von Lagrange- Multiplikatoren in die Zielfunktion integriert. Das vereinfachte Modell lässt sich nun besser lösen, wobei die Werte der Lagrange-Multiplikatoren so festzulegen sind, dass die kritischen Nebenbedingungen eingehalten werden.

Verschiedene heuristische Verfahren zur Lösung des mehrstufigen dynamischen Mehrprodukt-Losgrößenproblems mit Kapazitätsbeschränkungen sind von Maes entwickelt worden. Auf die einzelnen Varianten soll an dieser Stelle nicht eingegangen werden.

Das Verfahren von Helber greift das schon genannte Verfahren von Heinrich auf. Die bestehenden Kapazitätsbeschränkungen können dazu führen, dass ein in der zweiten Phase ermittelter Produktionsplan nicht zulässig ist. Dieses Problem versucht das Verfahren von Helber zu lösen.

Es ist auch möglich dieses Problem mit Hilfe einer Lagrange-Heuristik zu lösen. Hierzu kann das Verfahren von Tempelmeier und Derstroff verwendet werden. Dieses Verfahren wird im Punkt 3.1. näher beleuchtet.

Die nachfolgende Grafik verdeutlicht noch einmal die Gliederung der dynamischen Losgrößenprobleme und deren bekannteste Lösungsverfahren:

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.1: Gliederung der dynamischen Losgrößenprobleme

2.2. Der Begriff der Heuristik

Um einen Überblick zu gewinnen, soll zu Anfang die Systematik von Algorithmen betrachtet werden. Unter einem Algorithmus wird allgemein eine genau definierte Handlungsvorschrift zur Lösung eines Problems oder einer bestimmten Art von Problemen verstanden. Bezug nehmend auf Streim⁷ unterscheidet die Systematik zunächst zwischen Algorithmen mit sich wiederholenden Schrittfolgen - auch iterative Algorithmen genannt - und direkten Algorithmen, welche in einem einzigen Schritt zum Ergebnis gelangen. Als Algorithmus wird dabei „…eine Vorschrift, nach der Eingabedaten in einer vorgegebenen Reihenfolge durch eine endliche Anzahl von Schritten (Operationen) in Ausgabedaten (Ergebnisse, Lösungen) umgeformt werden…“⁸ verstanden.

Die nächste Unterscheidung innerhalb der iterativen Algorithmen wird bezüglich des garantierten Findens einer optimalen Lösung getroffen. Verfahren, die nicht in jedem Fall zu einer optimalen Lösung führen, werden als Heuristiken bezeichnet. Heuristiken arbeiten nach dem Prinzip, die Entscheidungsmöglichkeiten einzuschränken. Es werden nur bestimmte Lösungen weiterverfolgt. Dabei können aber auch relevante Lösungen, die unter Umständen sogar das Optimum geliefert hätten, verloren gehen.

Ein anderer Teil von iterativen Algorithmen wird als konvergierend bezeichnet, da sich hier die Lösungen mit zunehmenden Iterationen an das Optimum annähern. Als finit wird ein iterativer Algorithmus dann bezeichnet, wenn dieser nach einer endlichen Anzahl von Operationen die optimale Lösung erreicht. Als Beispiel für einen finiten Algorithmus mit Pfadstruktur kann man den Simplex-Algorithmus nennen. Ein finiter Algorithmus mit Baumstruktur ist beispielsweise das Branch and Bound. Algorithmen, die mit einer definierten Genauigkeit gegen das Optimum konvergieren, werden approximative Algorithmen genannt. Beispielhaft wäre das Newton-Verfahren zur Nullstellenbestimmung zu nennen.

Die folgende Abbildung verdeutlicht die Gliederung von Algorithmen noch einmal:

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.2: Systematik von Algorithmen⁹

Im Folgenden soll noch etwas genauer auf die heuristischen Verfahren eingegangen werden. Bei komplexen Optimierungsproblemen, deren optimale Lösung nur sehr aufwendig über exakte Verfahren zu berechnen ist, liefern Heuristiken akzeptable Lösungen mit weniger Rechenaufwand. Dabei kann nur eine eingeschränkte Aussage zur Güte der Lösung getroffen werden. Es wird also ein Kompromiss zwischen Rechenaufwand und Güte der Lösung eingegangen.¹⁰

Eine Heuristik ist demnach ein auf ein spezielles Problem zugeschnittenes, näherungsweises Lösungsverfahren, das keine Garantie für das Finden einer optimalen Lösung gibt und mögliche Lösungen durch nichtwillkürliche Regeln ausschließen kann.¹¹

Heuristiken können nach Domschke¹² im Wesentlichen in Eröffnungsverfahren, Verbesserungsverfahren und unvollständige exakte Verfahren unterteilt werden. Eröffnungsverfahren erzeugen die zulässigen Lösungen eines bestimmten Problems. In jedem Verfahrensschritt wird nach der größtmöglichen Verbesserung des Zielfunktionswertes gesucht (Greedy-Heuristik). Es gibt auch Verfahren, die vorausschauend bei jedem Schritt abschätzen, welchen Einfluss dieser auf die nächsten Schritte und die Güte der Lösung hat. Prioritätsregeln, als Beispiel für ein Eröffnungsverfahren, sind wegen ihrer leichten Handhabbarkeit und ihrer vergleichsweise einfachen Funktionsweise, das derzeit vorherrschende Planungshilfsmittel. Bei der Vorgabe von mehreren Zielen geht der Vorteil der leichten Handhabbarkeit jedoch schnell verloren, weshalb die Prioritätsregeln im Hinblick auf die Güte der Lösung zumeist hinter leistungsfähigeren Verfahren liegen. Zu den Verbesserungsverfahren zählen Verfahren, die den Zufall gezielt ausnutzen. Diese werden als stochastische Suchverfahren bezeichnet. Sie starten meist mit einer zufällig bestimmten Lösung oder mit einer Lösung, die durch ein Eröffnungsverfahren ermittelt wurde. Danach wird in jeder Iteration zu einer Lösung aus der Nachbarschaft fortgeschritten. Bei Verbesserungsverfahren sind alle gefundenen Lösungen unterschiedlich. Solche Verfahren werden verwendet, wenn die Regularitätsbedingungen der Zielfunktion nicht existieren oder nicht bekannt sind und eine schnelle und hinreichend gute Näherung der optimalen Lösung ausreicht. Zu den Verbesserungsverfahren gehören auch Verfahren, die zwar den Zufall nutzen, aber gezielt bestimmte Teile des Lösungsraums durchsuchen. Als Beispiel wäre hier Simulated Annealing oder Tabu Search zu nennen. Diese Verfahren sind bei praktischen Problemen von Vorteil, weil sie unabhängig von der Struktur des Lösungsraumes und von der Zielfunktion genutzt werden können. Da sie offen für Erweiterungen und Modifikationen sind, werden sie auch als Metaheuristiken bezeichnet. Verbesserungsverfahren enden, sobald keine bessere Nachbarschaftslösung existiert. Es kann also sein, dass die gefundene Lösung nur ein lokales Optimum darstellt. Verfahren die auch zu einer zwischenzeitlichen Verschlechterung des Zielfunktionswertes führen dürfen, werden als lokale Suchverfahren bezeichnet. Dabei kann es vorkommen, dass bereits gefundene Lösungen erneut auftreten.

Auch unvollständig ausgeführte exakte Verfahren sind zu den Heuristiken zu zählen. Dabei wird das exakte Verfahren nach einer bestimmten Rechenzeit und dem Erreichen einer ausreichenden Lösungsgüte abgebrochen.

Wird eine zulässige Lösung durch geringe Veränderungen des Zielfunktionswertes erzeugt spricht man von einer Lagrange-Heuristik.

3. Ausgewählte moderne Heuristiken

In diesem Kapitel sollen einige neuere Ansätze vorgestellt werden, um komplexe Probleme in der Berechnung von optimalen Losgrößen in der Bestellplanung als auch in der Produktionsplanung zu lösen.

Diese Arbeit beschränkt sich dabei auf Ansätze zum Mehr-Produkt-Losgrößenproblem unter Kapazitätsbeschränkungen.

3.1. A Lagrangean-based Heuristic for Dynamic Multilevel Multiitem Constrained Lotsizing with Setup Times

3.1.1. Einführung

Mithilfe dieses von Horst Tempelmeier und Matthias Derstroff¹³ entwickelten Verfahrens sollen dynamische mehrstufige Mehrproduktlosgrößenprobleme bei generellen Erzeugnisstrukturen mit mehrfach gebundenen Ressourcen und Rüstzeiten gelöst werden. Dieses Losgrößenproblem tritt typischerweise in Materialbedarfsplanungssystemen (MRP) auf, von denen bekannt ist, dass sie Kapazitätsbeschränkungen in der Losgrößenplanungs- phase nicht erkennen, und somit die Produktionsanlagen überlasten. Zur Lösung dieses Problems wird eine mehrstufige iterative Vorgehensweise beschrieben. Mittels Lagrange- Multiplikatoren und Kapazitätsnebenbedingungen wird das Problem in mehrere unbeschränkte dynamische Einproduktlosgrößenprobleme mit zeitlich variierenden Produktionskosten zerlegt. Diese werden mit einem exakten Lösungsverfahren gelöst. Verletzungen der Lagerbilanzgleichung und der Kapazitätsnebenbedingungen werden durch die Lagrange-Multiplikatoren, die durch ein integriertes Optimierungsverfahren aktualisiert werden, berücksichtigt. Ausgehend von den gefundenen Lösungen der Einproduktlosgrößen- probleme wird dann die untere Schranke des minimalen Wertes der Funktion errechnet. Die oberen Schranken errechnen sich mit einem endlichen heuristischen Verfahren. Die Herangehensweise ist sehr stark mit der Arbeit von Billington¹⁴ zu vergleichen.

3.1.2. Problemformulierung

Betrachtet werden verschiedene Endprodukte Pn, jedes mit einer bekannten externen Nachfrage, über einen endlichen Zeitraum hinweg. Zur Produktion der Endprodukte werden mehrere Komponenten (Einzelteile) En und Baugruppen Bn benötigt. Die folgende Abbildung liefert Informationen über die Arbeitsgänge und die dazu benötigten Ressourcen.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.1: Produktstruktur

Anzumerken ist, dass sich die Abfolge, ausgehend vom Blickwinkel der Ressource, periodisch wiederholen kann.

Das dynamische mehrstufige Mehrproduktlosgrößenproblem mit mehreren Ressourcen ist folgendermaßen festgesetzt:

- generelle Erzeugnisstruktur (mit mehreren möglichen Endprodukten), d.h. ein Produkt hat nicht nur einen eindeutigen Nachfolger
- die externe Nachfrage nach den Endprodukten ist gegeben
- mehrere Ressourcen mit gegebenen Kapazitäten werden einbezogen
- jeder Arbeitschritt ist einer einzigen Ressource zugeordnet
- Auftragsüberhänge sind nicht erlaubt
- wenn ein Produkt hergestellt wird, fallen, zusätzlich zu den variablen Produktionskos- ten, fixe Rüstkosten und Rüstzeiten an
- Lagerhaltungskosten werden anhand des Lagerbestandes am Ende einer Periode ermittelt

Die mathematische Formulierung der Zielfunktion des ab hier MLCLSP-Modell (Multi-Level Capacitated Lot Sizing Problem) genannten Modells ist folgendermaßen festgesetzt:

Abbildung in dieser Leseprobe nicht enthalten

Die Zielfunktion unterliegt folgenden Nebenbedingungen:

Abbildung in dieser Leseprobe nicht enthalten

Die Zielfunktion setzt sich aus variablen Produktionskosten, Instandhaltungskosten und Rüstkosten zusammen. Die Nebenbedingungen beschreiben die Beziehungen zwischen dem Bestand am Anfang und am Ende einer Periode, die externe Nachfrage, den Bedarf, der sich aus den Produktionsaufträgen für Nachfolgeprodukte ergibt und die Produktionsmenge eines Produktes. Außerdem erzwingen die Nebenbedingungen die Einhaltung der Ressourcen- bzw. Kapazitätsbeschränkungen.

3.1.3. Beschreibung der heuristischen Lösungsmethode

Lagrange-Heuristiken sind eine bekannte Möglichkeit die direkte Berücksichtigung schwieriger Nebenbedingungen zu umgehen, indem die Nebenbedingungen mit Strafkosten multipliziert und in die Zielfunktion integriert werden. In dieser Heuristik findet eine Vereinfachung hinsichtlich der Kapazitätsnebenbedingung und der LagerbestandsNebenbedingung statt. Zur einfacheren Erklärung wird angenommen, dass alle Durchlaufzeiten null sind. Die Lösung basiert somit auf den Nebenbedingungen (1) und (2) des MLCLSP-Modells aus Abschnitt 3.1.2..

Zunächst werden in einem Schritt 0 Lagrange-Multiplikatoren initialisiert. Im Schritt 1 erfolgt die Aufteilung des Losgrößenproblems in mehrere Unterprobleme. Die Auflockerung der Kapazitätsnebenbedingungen führt dazu, dass ein unbeschränktes mehrstufiges Mehrproduktlosgrößenproblem entsteht. Da aber noch keine Lösungsmethode für solche Probleme zur Verfügung steht, wird eine zweite Vereinfachung in Bezug auf die Lagerbilanznebenbedingung ausgeführt. Diese Lockerung führt dann zu dynamischen Einproduktlosgrößenunterproblemen des Wagner-Whitin-Typs, die problemlos gelöst werden können. Die Ergebnisse dieser Unterprobleme werden dann verwendet, um die untere Schranke bezüglich des Minimums der Zielfunktion zu errechnen. Zur Berechnung der unteren Schranke findet eine Vereinfachung des MLCLSP-Modells mittels Umformungen und Einsatz von Lagrange-Multiplikatoren statt. Dies endet schließlich in der Formulierung von unbeschränkten dynamischen Einproduktlosgrößenproblemen, die mit einem der bekannten Lösungsverfahren zur Lösung von Einproduktlosgrößenproblemen gelöst werden können.

Im nun folgenden Schritt 2 werden zunächst die Ressourcenauslastung und die Rückstände, die in Schritt 1 ermittelt wurden, mit Hilfe der Gleichungen (1) und (2) festgelegt. Die dabei beobachteten Nebenbedingungsverletzungen werden zur Verbesserung der Lagrange- Multiplikatoren mittels eines Optimierungsverfahrens genutzt. Ausgehend von gegebenen Werten erzeugt dieses Optimierungsverfahren, durch Addition der Ausgangswerte mit einem Richtungsvektor, der mit einer Schrittweite multipliziert wurde, eine Folge von Lagrange- Multiplikatoren.

Die obere Schranke bezüglich des Minimums der Zielfunktion wird in Schritt 3 berechnet. Hierbei muss sichergestellt werden, dass die vorgesehenen Produktionsmengen der später stattfindenden Produktionsschritte nicht zu Rückständen bei den vorangegangenen Schritten führen. Dazu werden die geplanten Produktionsmengen auf die unmittelbar vorangegangenen Arbeitsschritte aufgegliedert, wo dann die Losgrößenplanung durchgeführt wird. Diese Aufteilung auf die jeweiligen Vorgänger erfolgt bis zu den ersten Schritten der Produktion. Die Kapazitätsbeschränkungen finden Berücksichtigung durch ein endliches heuristisches Ablaufverfahren, das sich auf einen Produktionsplan bezieht, der hinsichtlich der Lagerbilanznebenbedingungen durchführbar ist. Dabei wird zuerst die aktuelle Auslastung berechnet und mit den verfügbaren Ressourcen verglichen. Dann wird eine mögliche Lösung des MLCLSP-Problems konstruiert, indem die Produktion aus überlasteten Perioden in nicht- überlastete Perioden verlagert wird. Dies wird solange wiederholt, bis eine durchführbare Lösung ereicht ist oder eine vorgegebene maximale Anzahl von Iterationsschritten überschritten wurde. Diese Verfahrensweise kann mittels eines vorwärts gerichteten Durchlaufs, das heißt Produktionsmengen aus der ersten Periode mit Kapazitätsüberlastung werden in nachfolgende Perioden verlagert, angewandt werden. Hierbei wird mit den überlasteten Ressourcen, die von Produktionsschritten mit wenigen Nachfolgern benötigt werden, begonnen (meist die Endprodukte). Die zweite Möglichkeit ist die Anwendung mittels rückwärts gerichteten Durchlaufs, die genau anders herum erfolgt. Hier wird mit überlasteten Ressourcen begonnen, die von vielen Vorgängern benötigt werden. Eine weitere Unterscheidung kann in Bezug auf die Anzahl der gleichzeitig betrachteten Produktions- schritte vorgenommen werden. Die Umverteilung der Produktion einer überlasteten Periode zu einer anderen Periode kann bezüglich eines einzelnen Produktionsschrittes oder einem ganzen Teil der Produktionsabfolge geschehen, wobei die Umverteilung ganzer Teile der Produktion erst angewandt wird, wenn keine Umverteilung bei einzelnen Produktionsschrit- ten mehr möglich ist.

Wenn nicht eines der Stop-Kriterien (hier nicht näher beschrieben) erreicht wird, springt die Prozedur wieder zu Schritt 1, anderenfalls ist sie beendet.

3.1.4. Tests und deren erreichte Ergebnisse

Die in 3.1.3. beschriebene Vorgehensweise wurde unter Verwendung von verschiedenen Zusammenstellungen wahllos erzeugter Probleme getestet. Dabei wurden fünf Klassen von Problemgrößen (A bis E) mit bis zu 100 Produkten bzw. Produktionsschritten, bis zu zehn verschiedenen Ressourcen und bis zu 16 Perioden betrachtet.

Folgende Vorgehensweise zur Erzeugung der Endproduktbedarfsreihen wurde angewandt. Für jedes Endprodukt wurde der Durchschnittsbedarf pro Periode festgelegt. Dann wurde, ausgehend von diesem Durchschnittsbedarf und einem Sollwert der üblichen Schwankung, der Bedarfs pro Periode festgelegt. Mittels Division des Durchschnittsbedarfs durch die anvisierte Kapazitätsausnutzung wurde die verfügbare Kapazität errechnet. Dieses Vorgehen erhält den Sollwert der Schwankung, führt aber einen Trend in die Bedarfsreihen ein.

Durchlaufzeiten, Anfangsbestände und ausstehende Aufträge wurden in allen Problemen vernachlässigt. Bei Problemen mit Rüstzeiten hängt die effektive Verwendung der Ressourcen von der Anzahl der Umrüstungen ab. Dabei wurde, basierend auf der angestrebten Auslastung, die erforderliche Kapazität berechnet und genutzt, um die Problemfälle zu erzeugen. Für Probleme der Klasse B hat sich gezeigt, dass die durchschnittliche effektive Auslastung sehr nahe bei der angestrebten Auslastung liegt, wogegen die effektive Auslastung bei Problemen der Klasse D beträchtlich geringer ist als die angestrebte Auslastung. Deshalb wurde für Probleme der Klasse D die verfügbare Kapazität schrittweise reduziert bis die durchschnittliche effektive Auslastung nahe an der angestrebten Auslastung lag.

Die obere Begrenzung der Anzahl der Iterationen liegt für alle Problem-Klassen bei 50, die untere Begrenzung bei 30 Iterationen.

Im Folgenden sollen die Merkmale der Problemklasse A bis E näher erläutert werden:

Die Problemklasse A besteht aus 300 kleinen Problemen mit jeweils zehn Produkten, vier Perioden und drei Ressourcen. Die konkreten Probleme wurden aus Kombinationen von vier unterschiedlichen Produktionsstrukturen, drei verschiedenen Endprodukten, fünf Kombinationen der Zeit zwischen den Aufträgen und fünf Kombinationen der Kapazitätsauslastung erzeugt. Insgesamt wurden so 1.500 Problemfälle in Betracht gezogen, für die Tempelmeier und Helber schon 1994 mit Hilfe der LINDO-Software optimale Lösungen berechnet haben.¹⁵

In der nachfolgenden Tabelle sind die Ergebnisse der Berechnungen dargestellt.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 3.1: durchschnittliche Abweichung vom Optimum

In der Tabelle 3.1 sind die Ergebnisse, gegliedert nach Kapazitätsauslastungsprofil (90%, 70%, 50%), Zeit zwischen den Aufträgen (TBO) und Variationskoeffizient, aufgeführt. Die durch Schrägstriche getrennten Zahlen kennzeichnen die durchschnittliche Auslastung in Prozent (90/70/50 und 50/70/90) beziehungsweise die Zeit zwischen den Aufträgen (TBO) für die obere, mittlere und untere Stufe der Produktionsstruktur.

Die Entwicklung der Lösungsqualität ist der folgenden Abbildung zu entnehmen. Dabei ist zu bemerken, dass die durchschnittliche Abweichung vom Optimum nach nur einer Iteration nur noch bei 3,54% liegt.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.2: Iterationsverlauf

In der Problemklasse B werden die Annahmen aus Klasse A beibehalten aber zusätzlich mit zwei Rüstzeitprofilen kombiniert. Die Rüstzeiten variieren zwischen fünf und 15 Zeiteinheiten, wobei eine Zeiteinheit die Produktionszeit für eine Einheit des Produktes darstellt. Im ersten Rüstzeitenprofil sind hohe Rüstzeiten für Produkte bzw. Arbeitsgänge, die nahe am Endprodukt liegen, festgesetzt. Dagegen wurden im zweiten Rüstzeitenprofil für Arbeitsgänge, die sich am Anfang der Produktionsstruktur befinden, hohe Rüstkosten festgelegt. Daraus ergeben sich für die Problemklasse B 600 Problemfälle, die alle sowohl exakt als auch mit der heuristischen Lösungsmethode gelöst wurden. Dabei wurden keine gravierenden Unterschiede zur Problemklasse A festgestellt. Um weitere Erkenntnisse zu erlangen, wurden die Auslastungsprofile von 50%, 70% und 90% auf 59%, 79% und 99% erhöht. Für drei der 600 Probleme konnte dabei mit der heuristischen Lösungsmethode keine gültige Lösung gefunden werden. Eine weitere Erhöhung der Auslastungsprofile auf 60%, 80% und 100% ergab elf von 600 Problemfällen, bei denen keine gültige Lösung ermittelt werden konnte. Dass aber eine gültige Lösung existiert, konnte mit der LINDO-Software leicht nachgewiesen werden.

Die Problemklasse C besteht aus 300 Problemen einschließlich 40 Produkten, 16 Perioden und sechs Ressourcen. Dabei wurden die einzelnen Probleme, analog zur Klasse A, durch die Kombination von vier unterschiedlichen Produktionsstrukturen, drei verschiedenen Endprodukten, fünf Kombinationen der Zeit zwischen den Aufträgen und fünf Kombinationen der Kapazitätsauslastung generiert. Für jeden Variationskoeffizient wurden zwei Endproduktnachfrageserien erzeugt, was insgesamt 600 Problemfälle ergibt. Probleme dieser Größe exakt zu lösen ist sehr schwierig, wenn nicht sogar unmöglich. Aus diesem Grund ist die Beurteilung der Ergebnisse der heuristischen Lösungsmethode hinsichtlich der Lösungsgüte ausgeschlossen. Um trotzdem Erkenntnisse bezüglich der vorgestellten Heuristik anbieten zu können, wurde ein Vergleich mit dem Verfahren von Tempelmeier und Helber und der unteren Schranke vorgenommen.

Die folgende Tabelle zeigt die durchschnittliche Abweichung von der Tempelmeier/Helber- Lösung.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 3.2: durchschnittliche Abweichung von der Tempelmeier/Helber-Lösung

Die Annahmen der Problemklasse D entsprechen denen der Klasse C, zusätzlich werden vier Rüstzeitprofile kombiniert. Es wird aber nur eine zufällig erzeugte Endproduktnachfrage in Betracht gezogen. Aufgrund der Einbeziehung von Rüstzeiten ist ein Vergleich mit der Tempelmeier/Helber-Heuristik in diesem Fall nicht möglich. Die Beurteilung der Lösungsqualität beruht hier allein auf der unteren Schranke.

Die durchschnittlichen Abweichungen der Lösungen von der unteren Schranke in Prozent von der oberen Schranke sind in folgender Tabelle dargestellt.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 3.3: durchschnittliche Abweichung der Lösungen von der unteren Schranke

Aus Testgründen wurde auch hier die angestrebte Auslastung erhöht (auf über 90%). Für diesen Fall fand die Heuristik keine gültigen Lösungen. Aufgrund der hohen Komplexität der Durchführung konnte nicht geprüft werden, ob eine gültige Lösung für einen dieser Problemfälle existiert.

Die Problemklasse E beinhaltet 150 Probleme mit 100 Produkten, 16 Perioden und zehn Ressourcen. Dabei wurden die einzelnen Probleme durch die Kombination von zwei unterschiedlichen Produktionsstrukturen, drei verschiedenen Endproduktstrukturen, fünf Kombinationen der Zeit zwischen den Aufträgen und fünf Kombinationen der Kapazitätsauslastung erzeugt. Rüstzeiten wurden nicht einbezogen. Die Ergebnisse können mit den Lösungen der Heuristik von Tempelmeier und Helber verglichen werden. Zu beachten ist, dass die Lösungsgüte verglichen mit der unteren Schranke dieselbe Größenordnung aufweist wie die, der viel kleineren Problemklasse C. Der Abstand zwischen oberer Schranke und unterer Schranke ist verhältnismäßig groß.

[...]

---

¹ W. Domschke; A. Scholl; S. Voß: Produktionsplanung. Springer-Verlag, 2.Auflage, 1997, S. 15 ff

² Erläuterung siehe W. Domschke; A. Scholl; S. Voß. Produktionsplanung. Springer-Verlag, 2.Auflage, 1997, S. 71 Nr.7

³ J. Käschel, T. Teich: Produktionswirtschaft Band 1: Grundlagen, Produktionsplanung und -steuerung, Lehrund Übungsbuch; Chemnitz, 2004, S.165

⁴ Download: http://www.produktion-und-logistik.de/produktionundlogistik-139.htm

⁵ H. Tempelmeier: Material-Logistik: Modelle und Algorithmen für die Produktionsplanung und -steuerung und das Supply Chain Management, 5. neu bearbeitete Auflage 2003, S.140-350

⁶ weiterführende Literatur: W.Domschke; A.Scholl; S.Voß. Produktionsplanung. Springer-Verlag, 2.Auflage, 1997, S.76 ff.

⁷ H. Streim: Heuristische Lösungsverfahren - Versuch einer Begriffsklärung, Zeitschrift f ü r Operations Research, 25(3), 1975, S.143-162

⁸ W. Domschke; A. Scholl; S. Voß: Produktionsplanung. Springer-Verlag, 2.Auflage, 1997, S.39

⁹ J. Käschel, T. Teich: Produktionswirtschaft Band 1: Grundlagen, Produktionsplanung und -steuerung, Lehrund Übungsbuch; GUC-Verlag, Chemnitz, 2004, S.295

¹⁰ Download: http://de.wikipedia.org/wiki/Heuristik

¹¹ J. Käschel, T. Teich: Produktionswirtschaft, Band 1: Grundlagen, Produktionsplanung und -steuerung, Lehrund Übungsbuch; GUC-Verlag, Chemnitz, 2004, S.293

¹² W. Domschke; A. Scholl; S.Voß. Produktionsplanung. Springer-Verlag, 2.Auflage, 1997, S.44-52

¹³ H. Tempelmeier, M. Derstroff: Management Science 42, 1996, S.738-757

¹⁴ P. Billington: Multi-level Lot-sizing with a Bottleneck Work Center, Ph.D. Dissertation, Cornell University, Ithaca, NY, 1983

¹⁵ H. Tempelmeier, S. Helber: A Heuristic for Dynamic Multi-item Multi-level Capacitated Lotsizing for General Product Structures; European Journal of Operations Research 75, 1994, S.296-311