Seite   

Inhaltsverzeichnis

Abbildungsverzeichnis   3

Tabellenverzeichnis. 4   

Abk  ürzungsverzeichnis  5

1.  Einleitung  6

2.  Strukturmerkmale von Modellen  7

2.1.  Technische Restriktionen.  7

2.2.  Modellierungstechnische Annahmen.  8

2.3.  Losgröße  10

2.4.  Zielkriterien.  10

3.  Modelle zur simultanen Losgrößen- und Reihenfolgeplanung.  11

3.1.  PLSP.  11

3.2.  GLSP  14

3.2.1.  Modellformulierung  14

3.2.2.  Einordnung.  16

3.2.3.  Das PLSP als Spezialfall des GLSP  17

3.2.4.  Das GLSP mit Rüstzeiten (GLSPST)  18

4.  Lösungsverfahren für das GLSPST.  19

4.1.  Benötigte Verfahren und Modelle zur Lösung des GLSPST.  19

4.1.1.  Erweiterung des GLSPST zum GLSPST’  19

4.1.2.  Fixierung des Rüstmusters und GLSPST’ FIX  20

4.1.3.  Formulierung des GLSPST’ FIX als Netzwerkflussproblem.  21

4.1.4.  Das duale Problem zu NFP Primal  24

4.1.5.  Konstruktion einer neue n dual zulässigen Lösung.  24

4.1.6.  Die Metaheuristiken TA und SA.  25

4.2.  Kombination von dualer Reoptimierung mit Metaheuristiken  26

5.  Zusammenfassung und Ausblick  30

Literaturverzeichnis.   32

2

Abbildungsverzeichnis

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

Abbildung 2: Threshold Accepting mit dualer Reoptimierung für die aktuelle

Tabellenverzeichnis   

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

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

4

Abkürzungsverzeichnis

GLSP

GSLPCS

GLSPPL

GLSPST

GLSPST’

GSLPST’ FIX GLSPST’ mit fixiertem Rüstmuster

LP

LS

MIP

NFP

PLSP

PPS

SA

TA

5

1. Einleitung

Möchte sich ein Anbieter eines Standardproduktes von seinen Wettbewerbern abheben, so ist eine Möglichkeit dazu über den Preis des Produktes ¹ . 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 ² 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 stehe n 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 ³ 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 m an 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

¹ 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.

² Für eine ausführliche Beschreibung des kapazitätsorientiertem hierarchischen PPS-Konzepts siehe Drexl,

Fleischmann, et al. (1994).

³ Im Folgenden werden die beiden Begriffe „Produktionslinie“ und „Maschine“ synonym verwendet.

6

erfüllt werden und die Linienkapazität nicht überschritten werden muss?“ ⁴ . 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.

⁴ Vgl. Meyr (1999), S. 4.

⁵ Für weiter führende Erläuterungen siehe z.B. Meyr (1999).

7

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

8