Integrierte Losgrößen- und Reihenfolgeplanung (GLSP)

Inhaltsverzeichnis

Abbildungsverzeichnis

Tabellenverzeichnis

Abkürzungsverzeichnis

1. Einleitung

2. Strukturmerkmale von Modellen
2.1. Technische Restriktionen
2.2. Modellierungstechnische Annahmen
2.3. Losgröße
2.4. Zielkriterien

3. Modelle zur simultanen Losgrößen- und Reihenfolgeplanung
3.1. PLSP
3.2. GLSP
3.2.1. Modellformulierung
3.2.2. Einordnung
3.2.3. Das PLSP als Spezialfall des GLSP
3.2.4. Das GLSP mit Rüstzeiten (GLSPST)

4. Lösungsverfahren für das GLSPST
4.1. Benötigte Verfahren und Modelle zur Lösung des GLSPST
4.1.1. Erweiterung des GLSPST zum GLSPST’
4.1.2. Fixierung des Rüstmusters und GLSPST’FIX
4.1.3. Formulierung des GLSPST’FIX als Netzwerkflussproblem
4.1.4. Das duale Problem zu NFPPrimal
4.1.5. Konstruktion einer neuen dual zulässigen Lösung
4.1.6. Die Metaheuristiken TA und SA
4.2. Kombination von dualer Reoptimierung mit Metaheuristiken

5. Zusammenfassung und Ausblick

Literaturverzeichnis

Abbildungsverzeichnis

Abbildung 1: GLSPST’FIX als Netzwerkflussproblem mit J=3 und T=

Abbildung 2: Threshold Accepting mit dualer Reoptimierung für die aktuelle Lösung h und den Kandidaten r

Tabellenverzeichnis

Tabelle 1: Indizes , Daten, Variablen für das PLSP

Tabelle 2: Indizes , Daten, Variablen für das GLSP

Abkürzungsverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

1. Einleitung

Möchte sich ein Anbieter eines Standardproduktes von seinen Wettbewerbern abheben, so ist eine Möglichkeit dazu über den Preis des Produktes^[1]. Ein nahe liegender Weg, ein Produkt möglichst kostengünstig anbieten zu können, ist das Produkt mit möglichst geringen Kosten zu produzieren.

Vor diesem Hintergrund beschreibt die vorliegende Arbeit die grundlegende Problemstellung bei der simultanen Losgrößen- und Reihenfolgeplanung im Rahmen eines kapazitätsorientierten hierarchischen Produktionsplanungs- und Steuerungs- Systems^[2] mit dem Ziel einer Kosten sparenden Planung. Zwei ausgesuchte Modelle zur simultanen Losgrößen- und Reihenfolgeplanung werden vorgestellt, anhand ihrer Strukturmerkmale eingeordnet, und miteinander verglichen. Für einen Spezialfall eines dieser Modelle wird schließlich ein effizientes Lösungsverfahren mit hoher Lösungsgüte vorgestellt.

Im Vordergrund der Betrachtung stehen Produkte, die in kontinuierlicher Fließfertigung auf einer Produktionsstufe hergestellt werden. Die Produktionsstufe setzt sich aus einer oder mehreren Produktionslinien mit beschränkter Kapazität zusammen, wobei die Produktionslinien / Maschinen^[3] als planerische Einheit betrachtet werden. Produzierte Artikel gehören zu Rüstfamilien; wird auf einer Produktionslinie auf einen Artikel einer anderen Rüstfamilie als der des zuletzt aufgelegten Artikels umgestellt, muss umgerüstet werden. Dies kann Rüstkosten und Rüstzeiten verursachen. Hängen diese von der Art des zuletzt aufgelegten Artikels ab, spricht man von reihenfolgeabhängigen Rüstkosten bzw. –zeiten. Der Bedarf an Artikeln steht zum Planungszeitpunkt lediglich in Form einer Prognose zur Verfügung. Da man möglichst große Produktionslose bilden möchte, um Kosten für Umrüstvorgänge zu sparen, wird oft über den prognostizierten Bedarf hinaus für spätere Verwendung produziert, und es fallen für den Überschuss Lagerkosten an, welche von Bestandshöhe und Lagerdauer abhängen.

Die Gegenläufigkeit dieser beiden Ziele („wenige / billige Umrüstungen“ und „niedrige Losgrößenbestände“) führt zum zentralen Problem der simultanen Losgrößen- und Reihenfolgeplanung: „Wann und in welcher Menge sind Artikel auf einer vorgegebenen Produktionslinie möglichst kostengünstig herzustellen, so dass die Bedarfsprognosen erfüllt werden und die Linienkapazität nicht überschritten werden muss?“^[4]. Für den Fall dass mehrere, evtl. heterogene Produktionslinien mit unterschiedlichen Kosten für die Produktion der Artikel zur Verfügung stehen, muss zusätzlich noch entschieden werden, auf welcher dieser Maschinen ein Artikel zu welcher Zeit am besten hergestellt wird.

Da sich die Entscheidungen über Losgrößen, Reihenfolge der Lose, und Zuordnung der Lose zu Produktionslinien gegenseitig beeinflussen, ist zur Lösung des geschilderten Problems eine simultane, integrierte Planung vorzunehmen.

In der Literatur gibt es eine Vielzahl von Modellen und Lösungsansätzen für das vorgestellte Problem; im weiteren Verlauf der Arbeit werden deswegen in Kapitel 2 zuerst die wichtigsten charakteristischen Merkmale, anhand derer sich diese Modelle klassifizieren lassen, erläutert.

Stellvertretend für die in der Praxis momentan eingesetzten Modelle wird das Proportional Lotsizing and Scheduling Problem (PLSP) vorgestellt und anhand seiner Merkmale eingeordnet. Der Schwerpunkt des dritten Kapitels ist dann das General Lotsizing and Scheduling Modell (GLSP), welches eher ein allgemeines Erklärungsmodell darstellt, aus dem sich aber alle in der Praxis eingesetzten Modelle ableiten lassen. Auch das GLSP wird anhand seiner Merkmale klassifiziert, und es wird erläutert, wie sich das vorher vorgestellte PLSP aus dem GLSP ableiten lässt. Des Weiteren wird ein Spezialfall des GLSP, das GLSPST, vorgestellt.

Im zweiten Teil der Arbeit wird dann in Kapitel 4 ein Lösungsverfahren für das GLSPST vorgestellt, welches auf der Kombination von auf Local Search basierenden Metaheuristiken mit dualer Reoptimierung beruht.

2. Strukturmerkmale von Modellen

Im Folgenden werden die wichtigsten Merkmale, mit Hilfe derer sich Modelle der Losgrößen- und Reihenfolgeplanung klassifizieren lassen, vorgestellt.^[5]

2.1. Technische Restriktionen

Man unterscheidet zwischen Ein- und Mehrmaschinenproblemen, wobei bei Mehrmaschinenproblemen die Anordnung der Maschinen seriell oder parallel sein kann. Außerdem wird noch nach Anzahl der Produktionsstufen unterschieden, wobei diese Arbeit sich auf Modelle mit einer Produktionsstufe beschränkt.

Die Verfügbarkeit der Ressourcen, insbesondere Maschinen und Personal, stellt eine weitere technische Restriktion dar. Die Kapazitäten der Maschinen sind kurzfristig nicht erweiterbar; bzgl. des Personals kann eine kurzfristige Kapazitätserhöhung z.B. durch Überstunden oder Springer geschehen.

Betrachtet man in der Planung keine Zusammenhänge zwischen dem zu planenden Produkt und eventuell in Beziehung stehenden Vor- oder Folgeprodukten, wird die Erzeugnisstruktur als einstufig bezeichnet. Im Gegensatz dazu wird die Erzeugnisstruktur, bei der Vorgänger-Nachfolger-Beziehungen in die Planung mit einbezogen werden, mehrstufige Erzeugnisstruktur genannt.

Eine weitere technische Restriktion ist die Art der Rüstvorgänge, die beim Wechsel auf ein Los aus einer anderen Produktfamilie anfallen. Die Maßnahmen für die Umrüstungen sind unabhängig von der Größe der Lose und verursachen Rüstkosten bzw. Rüstzeiten. Liegen reihenfolgeabhängige Umrüstkosten vor, so sind die Rüstkosten abhängig von der Art des zuvor aufgelegten Loses. Hier kann außerdem der Fall auftreten, dass die Dreiecksungleichung verletzt wird; d.h. dass die Summe der Rüstkosten der Produktfolge c-d-e kleiner sind als die Rüstkosten der Produktfolge c-e. Außerdem ist zu unterscheiden ob eine Produktionslinie in einer Periode ohne Produktion für die Herstellung des zuletzt aufgelegten Produktes gerüstet bleibt („conservation of setup-state“), oder der Rüstzustand verloren geht („loss of setup-state“) und die Produktionslinie in einen neutralen Zustand übergeht.

Zeiträume, in denen eine Maschine nichts produziert, heißen Stillstandzeiten. Man unterscheidet zwischen exogenen Stillständen, die aufgrund von Umwelteinflüssen entstehen können, und endogenen Stillständen, die sich als Entscheidungsgrößen des Modells ergeben können.

2.2. Modellierungstechnische Annahmen

Da sich sowohl der innere Zustand des zu modellierenden Systems und die externen Umwelteinflüsse, die Einfluss auf das System haben, mit der Zeit ändern, ist zwischen der Innendynamik (die endogenen Zustandsänderungen des Systemvariablen) und der Außendynamik (die exogenen Zustandsänderungen der Umwelt) des Systems zu unterscheiden. Die Zustandsänderungen des Systems können dabei entweder sprunghaft oder kontinuierlich ablaufen; entsprechend werden zur Modellierung diskrete oder kontinuierliche Variablen herangezogen, wobei zur Vereinfachung des Modells kontinuierliche Zustandsänderungen oft ebenfalls als diskrete Änderungen des Systems modelliert werden. Die Ausprägung der durch die möglichen Zeitpunkte der Zustandsänderungen definierten exogenen / endogenen Zeitstruktur kann also zur Unterscheidung von Modellen benutzt werden.

Bei der exogenen Zeitstruktur spricht man von einem (diskreten) exogenen Außen-Zeitraster, wenn (diskrete) Veränderungen des Umweltzustandes nur zu endlich vielen (fest vorgegebenen, diskreten) Zeitpunkten auftreten können^[6]. Existiert kein festes Außenraster, können also die exogenen Zustandsänderungen zu jedem beliebigem Zeitpunkt eintreten, so ist dies eine freie Terminierung, bei der man dann zwischen kontinuierlicher und diskreter Änderung der Zustände (z.B. der Nachfrage nach einem Produkt) unterscheidet.

Man bezeichnet die endogene Zeitstruktur als frei terminierbar, wenn Änderungen der Systemvariablen zu jedem beliebigem Zeitpunkt auftreten können und somit unabhängig von der exogenen Zeitstruktur sind. Wenn im Gegensatz dazu die Änderungen der Systemvariablen nur an Rasterpunkten des Außenrasters auftreten dürfen, wird die endogene Zeitstruktur als fixiert an das Außenraster bezeichnet. Des Weiteren besteht die Möglichkeit zusätzlich zum Außenraster noch ein diskretes Innen-Zeitraster anzugeben, welches zur Beschreibung der endogenen Zustandsänderungen des Systems dient und eine feinere Unterteilung des Außenrasters darstellt. Auch beim Innenraster können die endogenen Zustandsänderungen dann wieder frei gegenüber dem Innenraster oder am Innenraster fixiert sein^[7].

Je nach Länge der Zeitintervalle für ein Raster unterscheidet man zwischen small-time-bucket-Modellen (Intervalle von kurzer Dauer, z.B. Stunden, Arbeitstag) und large-time-bucket-Modellen (Intervalle von längerer Dauer, z.B. Wochen, Monate).

Weitere wichtige Eigenschaften der Modelle bei Vorliegen eines Zeitrasters sind die Maximalzahl der Lose die pro Periode aufgelegt werden können, und die Maximalzahl an endogenen Zustandsänderungen, die in einem time-bucket auftreten können. Beide können, je nach Modell, fest vorgegeben oder frei variierbar sein. Sind nur wenige Zustandsänderungen innerhalb eine time-buckets erlaubt (bzw. ist die Maximalzahl an möglichen Losen während der Periode sehr gering), so spricht man von Mikroperioden; ist dies nicht der Fall, so wird das time-bucket als Makroperiode bezeichnet.

Weitere modellierungstechnische Merkmale neben der Zeitstruktur sind der Planungshorizont der Modelle (unendlicher Planungshorizont bei stabilem Umweltzustand, endlicher bei Existenz eines Außenrasters), die Verfügbarkeit von Daten (hier werden oft stochastische Daten wie z.B. die Kundennachfrage als deterministisch angenommen), sowie der Servicegrad (der bei der Losgrößenplanung und deterministischer Nachfrage üblicherweise als 100 Prozent vorgegeben wird).

[...]

^[1] Die andere Möglichkeit wäre über einen hohen Servicegrad. Das Erreichen eines hohen Servicegrades und die damit einher gehende Problematik von Sicherheitsbeständen bei der Lagerhaltung fällt allerdings eher in den Bereich der Lagerhaltungspolitik und wird deswegen in dieser Arbeit nicht weiter verfolgt.

^[2] Für eine ausführliche Beschreibung des kapazitätsorientiertem hierarchischen PPS-Konzepts siehe Drexl, Fleischmann, et al. (1994).

^[3] Im Folgenden werden die beiden Begriffe „Produktionslinie“ und „Maschine“ synonym verwendet.

^[4] Vgl. Meyr (1999), S. 4.

^[5] Für weiter führende Erläuterungen siehe z.B. Meyr (1999).

^[6] Vgl. Meyr (1999)

^[7] Da das Innenraster eine feinere Unterteilung des Außenrasters darstellt, bedeutet freie Terminierung bzw. Fixierung gegenüber dem Innenraster somit ebenso freie Terminierung bzw. Fixierung bzgl. des Außenrasters.