Heuristiken zur Lösung von Losgrößenproblemen

von: Jens Stöckhardt

Inhaltsverzeichnis

1. EINLEITUNG  2

2. BEGRIFFSERLÄUTERUNGEN  4

2.1. LOSGRÖßENPROBLEME 4
2.2. DER BEGRIFF DER HEURISTIK  6

3. AUSGEWÄHLTE MODERNE HEURISTIKEN 9

3.1. A LAGRANGEAN-BASED HEURISTIC FOR DYNAMIC MULTILEVEL MULTIITEM CONSTRAINED LOTSIZING WITH SETUP TIMES  9

3.1.1. Einführung  9
3.1.2. Problemformulierung 9
3.1.3. Beschreibung der heuristischen Lösungsmethode  11
3.1.4. Tests und deren erreichte Ergebnisse 13
3.1.5. Fazit  17

3.2. MULTILEVEL LOT SIZING WITH SETUP TIMES AND MULTIPLE CONSTRAINED RESSOURCES: INTERNALLY ROLLING SCHEDULES WITH LOT-SIZING WINDOWS 18

3.2.1. Einführung  18
3.2.2. Entscheidungsproblem und Modellformulierung  18
3.2.3. Ablaufpläne mit Planungsfenstern 19
3.2.4. Modellformulierung der Untermodelle 21
3.2.5. Berücksichtigung von Rüstzeiten  22
3.2.6. Errechnete Ergebnisse 23
3.2.7. Fazit  26

3.3. HEURISTIKEN MIT FORTSCHREITENDEN INTERVALLEN 27

3.3.1. Einführung  27
3.3.2. Das Mehr-Produkt-Modell mit Joint and Item-dependent Setup Costs (JIS)  28
3.3.3. Beschreibung der Heuristik  29
3.3.4. Ablauf der Lösungssuche 34
3.3.5. Tests und deren Ergebnisse 35

3.4. STEUERUNG EINER HEURISTIK ZUR LOSGRÖßENPLANUNG UNTER KAPAZITÄTSRESTRIKTIONEN MIT HILFE EINES PARALLELEN GENETISCHEN ALGORITHMUS  37

3.4.1. Ausgangspunkt dieser Heuristik  37
3.4.2. Das Modell (CLSPL)  37
3.4.3. Die Heuristik von Haase  39
3.4.4. Der genetische Algorithmus  40
3.4.5. Tests und Ergebnisse  42

4. ANHANG 43

4.1. LITERATURVERZEICHNIS  43
4.2. ABBILDUNGSVERZEICHNIS  44

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ätsterminierung 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üstkosten2 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ößenprobleme 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 Kostenausgleichsverfahren, 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 Beantwortung 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 Entscheidungsalternativen in einem Optimierungsmodell zusammenzufassen ist die Grundidee des Verfahrens von Bahl.
• Eine andere Lösungsmöglichkeit ist die Verwendung des zeitlichen Dekompositionsverfahrens 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.

[...]

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

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

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

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

5 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

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