Simultane Losgrößen- und Reihenfolgeplanung unter Berücksichtigung von mehrstufigen Produktionsverfahren und Kapazitätsrestriktionen

Inhaltsverzeichnis

ABBILDUNGSVERZEICHNIS

TABELLENVERZEICHNIS

ABKÜRZUNGSVERZEICHNIS

SYMBOLVERZEICHNIS

1 EINLEITUNG UND GANG DER UNTERSUCHUNG
1.1 PROBLEMSTELLUNG
1.2 ZIELSETZUNG UND GANG DER UNTERSUCHUNG

2 EINORDNUNG DER THEMATIK IN DIE PRODUKTIONSPLANUNG

3 ANALYSE SIMULTANER LOSGRÖßEN- UND REIHENFOLGEPLANUNGSMODELLE
3.1 GRUNDLAGEN DER LOSGRÖßEN- UND REIHENFOLGEPLANUNG
3.2 ANALYSE DER SIMULTANEN GRUNDMODELLE UNTER KAPAZITÄTSRESTRIKTIONEN
3.2.1 Das Economic Lot Scheduling Problem
3.2.2 Das Discrete Lot Sizing and Scheduling Problem
3.2.3 Das Continuous Setup Lot Sizing Problem
3.2.4 Das Proportional Lot Sizing and Scheduling Problem
3.2.5 Das Capacitated Lot Sizing Problem
3.2.5.1 Das Grundmodell des Capacitated Lot Sizing Problem
3.2.5.2 Erweiterung des CLSP um reihenfolgeabhängige Rüstkosten
3.2.6 Das General Lot Sizing and Scheduling Problem und mögliche Erweiterungen
3.3 ANALYSE DER MEHRSTUFIGEN MODELLE UNTER KAPAZITÄTSRESTRIKTIONEN
3.3.1 Grundlagen der mehrstufigen Produktionsverfahren
3.3.2 Das Multi-Level Capacitated Lot Sizing Problem
3.3.3 Das General Lot Sizing and Scheduling Problem for multiple Production Stages
3.3.4 Das Multi-Level General Lot Sizing Problem

4 ERWEITERUNGEN DES REFERENZMODELLS UM AUSGEWÄHLTE SACHVERHALTE
4.1 ÜBERTRAGUNG VON RÜSTZUSTÄNDEN AUF FOLGEPERIODEN (SETUP-CARRY-OVER)
4.2 BERÜCKSICHTIGUNG POSITIVER TRANSPORTZEITEN
4.3 PRODUKTCHARAKTERISTIKA: BESCHRÄNKTE LEBENSDAUER DER PRODUKTE BZW. DETERIORATION

5 LÖSUNGSANSÄTZE FÜR DIE MODELLE
5.1 KLASSIFIKATION VON LÖSUNGSANSÄTZEN
5.2 HEURISTIKEN DER MATHEMATISCHEN PROGRAMMIERUNG
5.2.1 Branch&Bound-Verfahren
5.2.2 Reformulierungen
5.2.3 Gültige Ungleichungen
5.2.4 Weitere ausgewählte Verfahren der mathematischen Programmierung
5.3 LAGRANGE HEURISTIKEN
5.4 DEKOMPOSITION UND AGGREGATION
5.5 META-HEURISTIKEN 59 Simultane Losgrößen- und Reihenfolgeplanung: Analyse, Lösungswege und Erweiterungen Seite II
5.6 GREEDY-VERFAHREN
5.7 HYBRIDE META-HEURISTIKEN
5.7.1 Grundlagen der Hybridisierung
5.7.2 Modellierung der mathematischen Programmierung in Form von gültigen Ungleichungen
5.7.3 Memetischer Algorithmus
5.8 FAZIT FÜR DIE LÖSUNGSANSÄTZE 75 6 MODELLIERUNG AUSGEWÄHLTER PROBLEME MIT AMPL / CPLEX

6.1 GRUNDLEGENDES ZU DER MODELLIERUNG MIT AMPL UND BEISPIELDATEN
6.2 ANALYSE EINSTUFIGER MODELLE
6.3 ANALYSE MEHRSTUFIGER MODELLE
6.4 ANALYSE ERWEITERTER MODELLE
6.5 FAZIT AUS DER MODELLIERUNG DER AUSGEWÄHLTEN PROBLEME MIT AMPL / CPLEX

7 SCHLUSSBETRACHTUNG

ANHANG

LITERATURVERZEICHNIS

Abbildungsverzeichnis

Abbildung 1: Kostenübersicht bei der Losgrößenberechnung

Abbildung 2: Gozintograph-Darstellungen für unterschiedliche Erzeugnisstrukturen

Abbildung 3: Klassifikation der Modelle bezüglich des Planungshorizonts

Abbildung 4: Zweistufige Zeitstruktur des MLGLSPMM für Maschine m

Abbildung 5: Klassifikation von Lösungsansätzen

Abbildung 6: Pseudocode für den memetischen Algorithmus

Abbildung 7: Darstellung der Populationsstrukur

Abbildung 8: Optimale Lösung für das DLSP mit einem ZF von 147,5 GE

Abbildung 9: Optimale Lösung für das CSLP mit einem ZF von 92,5 GE

Abbildung 10: Optimale Lösung für das PLSP mit Rüstzeiten mit einem ZF von 72,5 GE

Abbildung 11: Optimale Lösung für das CLSP mit einem ZF von 122,5 GE

Abbildung 12: Optimale Lösung für das CLSPL mit einem ZF von 72,5 GE

Abbildung 13: Optimale Lösung für das GLSPCS mit einem ZF von 47,5 GE

Abbildung 14: Erzeugnisstruktur für die Modellierung der mehrstufigen Modelle

Abbildung 15: Optimale Lösung für das MLCLSP mit einem ZF von 164 GE

Abbildung 16: Optimale Lösung für das MLCLSPL mit einem ZF von 85 GE

Abbildung 17: Optimale Lösung für das CLSP_perishability mit einem ZF von 122,5 GE

Abbildung 18: Optimale Lösung für das CLSP_deterioration mit einem ZF von 245 GE 83 Simultane Losgrößen- und Reihenfolgeplanung: Analyse, Lösungswege und Erweiterungen Seite IV

Tabellenverzeichnis

Tabelle 1: Beispieldaten für die einstufige Modellierung

Tabelle 2: Zusätzliche Beispieldaten für das GLSPCS

Tabelle 3: Zusätzliche Beispieldaten für die mehrstufigen Modelle Simultane Losgrößen- und Reihenfolgeplanung: Analyse, Lösungswege und Erweiterungen Seite

Abkürzungsverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

1 Einleitung und Gang der Untersuchung

1.1 Problemstellung

Die Entscheidungen, die im Rahmen der operativen Losgrößen- und Reihenfolgeplanung getroffen werden, sind mitunter die wichtigsten im Produktionsprozess, da sich aus Fehlentscheidungen schwerwiegende Konsequenzen für das gesamte Unternehmen ergeben können. So kann ein zu früh terminiertes Produkt beispielsweise zu hohen Lagerhaltungskosten und damit zu hohen Kapitalbindungskosten, ein zu spät terminiertes Produkt zu verspäteten Lieferungen und somit zu hohen Strafkosten führen.

Schon die Entscheidung hinsichtlich der Losgrößenproblematik, wann, wo, wie und welche Produkte zu welchen Kosten hergestellt werden müssen, um die bestehende bekannte und/oder anonyme Nachfrage zu befriedigen, ist schwierig. Dies wird umso schwieriger, wenn auch noch die Reihenfolgeplanung der Produktionsaufträge auf mehr als einer kapazitierten Ressource einbezogen wird.

In den Produktionsplanungssystemen der Praxis wird seit Jahrzehnten das Material Requirements Planning (MRP) oder das Manufacture Resource Planning (MRP II) verwendet. Hierbei handelt es sich um Systeme, welche die einzelnen Planungsschritte der Produktions- planung sukzessive ausführen, wobei die Kapazität erst sehr spät in die Planung einbezogen wird. Der aus dieser Planung resultierende Produktionsplan kann durch die Sukzessivplanung mit sehr hohen Kosten verbunden sein und ist aufgrund der Annahme von unbeschränkten Kapazitäten häufig nicht realisierbar. Daher wird versucht, die einzelnen Planungsschritte simultan zu planen, so dass sich ein realisierbarer und kostenminimaler Produktionsplan ergibt.

Dennoch bilden Simultanplanungen nur begrenzte Alternativen, die zwar theoretisch einen gültigen Produktionsplan erstellen könnten, in der Praxis aber an der Berechenbarkeit der Pro- bleme scheitert, da es sich in der Regel um Problemstellungen handelt, die nicht mehr mit akzeptablem Zeitaufwand optimal gelöst werden können. Zwar ist heute leistungsfähige Software verfügbar, die auf Methoden, wie dem Branch&Bound und dessen Unterarten, wie z.B. dem Branch&Cut basieren, und welche zusammen mit der gestiegenen Rechenkapazität Probleminstanzen lösen kann, die vor ein paar Jahren noch unlösbar gewesen wären, dennoch sind die in der Praxis vorherrschenden Problemgrößen immer noch nicht durchführbar.

Aus diesem Grund konzentriert sich die Forschung auf die Entwicklung von heuristischen Verfahren und Reformulierungen der Modelle, mit denen es möglich ist, den Lösungsraum der Problemstellungen zu begrenzen und das Intervall, in dem die optimale Lösung liegen sollte, einzugrenzen, so dass zumindest gute Lösungen mit einem akzeptablen Zeitaufwand generiert werden können.

1.2 Zielsetzung und Gang der Untersuchung

Ziel dieser Diplomarbeit ist es, diskrete¹ Modelle der simultanen, kapazitierten Losgrößen- und Reihenfolgeplanung darzustellen und auf ihre Prämissen zu analysieren, mögliche Lö- sungswege aufzuzeigen und diese Modelle um weitere Restriktionen zu erweitern. Weder die aufgezeigten Modelle und ihre Erweiterungen noch die Lösungswege oder die dazugehörigen Literaturangaben erheben den Anspruch der Vollständigkeit. Vielmehr soll ein Überblick über wesentliche Modelle verschafft und gezeigt werden, in welchem Bereich mögliche Erweite- rungen angesetzt werden können und wie es möglich sein kann, gute Lösungen auch für grö- ßere Probleminstanzen zu erhalten.

Dazu wird zunächst in Kapitel 2 eine Einordnung der Losgrößen- und Reihenfolgeplanung in die operative Produktionsplanung vorgenommen und erläutert, in welche sukzessiven Phasen sich diese untergliedern lässt.

In Kapitel 3 werden die Modelle der simultanen Losgrößen- und Reihenfolgeplanung unter Beachtung von Kapazitätsrestriktionen analysiert. Ausgehend von ausgewählten Klassifika- tionsmerkmalen der Modelle wird hier auf unterschiedliche Erzeugnisstrukturen der Produkte eingegangen und die Modelle mit endlichem Planungshorizont und diskreten Zeitintervallen hinsichtlich der relativen Länge der Zeitperioden in „Small Bucket“- und „Big Bucket“- Probleme eingeordnet. Für die Analyse der Grundmodelle der einstufigen Losgrößen- und Reihenfolgeplanung werden die einzelnen Probleme modelliert, deren Prämissen kurz aufge- zeigt und Vor- und Nachteile sowie erste Erweiterungen und Lösungsansätze anhand von Li- teraturangaben aufgezeigt.

Mehrstufige Modelle sind gleichwohl komplizierter als die einstufigen Modelle, da sie zusätz- lich Interdependenzen hinsichtlich der Erzeugnisstruktur, des Zeitablaufs und der Ressour- cenbelegung berücksichtigen müssen. Ausgehend von diesen Voraussetzungen werden aus-gewählte mehrstufige Modelle definiert sowie in Bezug auf Prämissen, erster möglicher Erweiterungen und Lösungsansätze anhand von Literaturangaben analysiert.

In Kapitel 4 wird das Capacitated Lot Sizing Problem als Referenzmodell um die Sachverhalte der Rüstvorgangsübertragung, der Transportzeitenintegration sowie der Lebensdauer von Produkten erweitert. Besonders interessant im Hinblick auf die Reduzierung von Rüstkosten und damit auf die Gesamtkosten der Produktion ist die Übertragung von Rüstzuständen auf Folgeperioden. Hier wird gefordert, dass bei Produktion desselben Produkts über Periodengrenzen hinweg nicht neu gerüstet werden muss.

Im Zeitalter der Globalisierung und des Outsourcing stellt die Berücksichtigung von positiven Transportzeiten für ein Unternehmen mit Produktionsstätten an unterschiedlichen geografischen Orten ein realistisches Szenario dar, da sich eine mangelnde Koordination von Produktions- und Transportplanung in beachtlichen Kosten für das Unternehmen auswirken kann. Die Modellierung erfolgt hier unter Berücksichtigung von unterschiedlichen Produktionsstätten und Transportarten.

Einige Produkte unterliegen hinsichtlich ihrer Lebensdauer zeitlichen Restriktionen, denen in der Modellierung der Produktionsmengen und Lagerhaltung Rechnung getragen werden muss. So haben z.B. Lebensmittel ein Mindesthaltbarkeitsdatum, nach dessen Ablauf diese Produkte entsorgt werden müssen, und Fashion Ware unterliegt einer stetigen Wertminderung, so dass sich im Hinblick auf die Produktionsmengen und der entscheidungsrelevanten Kosten interessante Ergebnisse zeigen.

In Kapitel 5 sollen mögliche Lösungsansätze aufgezeigt werden, wobei der Fokus auf die Verfahren der mathematischen Programmierung, auf die Meta-Heuristiken und die hybriden Verfahren gesetzt wird. Hier werden die einzelnen Ansätze kurz allgemein dargestellt und anhand von ausgewählten Literaturangaben näher erläutert. Im Rahmen der hybriden Verfahren wird versucht, einen Lösungsansatz, der aus der Modellierung von gültigen Ungleichungen und einem memetischen Algorithmus besteht, ausführlich darzustellen.

In Kapitel 6 werden einige der betrachteten Modelle mit AMPL in der Studentenversion und dem optionalen Solver CPLEX 11.2.0 für kleine Probleminstanzen optimal gelöst und die Ergebnisse auf mögliche Schwächen in den Prämissen der Modelle hin analysiert. Einem Fa- zit aus der Modellierung mit AMPL schließt sich in Kapitel 7 die Schlussbetrachtung an.

2 Einordnung der Thematik in die Produktionsplanung

Zu den Aufgaben der Produktionsplanung gehören die Festlegung der produktionswirtschaft- lichen Ziele und die Umsetzung dieser Ziele in Handlungsalternativen für den Produktions- prozess.² Man unterscheidet je nach Fristigkeit zwischen strategischer und operativer Produk- tionsplanung. Die strategische Produktionsplanung gibt für die operative Produktionsplanung den Rahmen des Produktprogramms sowie die verfügbare Kapazität der Ressourcen vor, in- nerhalb deren Grenzen auf der Grundlage von produktpolitischen Entscheidungen die vorlie- gende bzw. erwartete Nachfrage hinsichtlich der Fristigkeit und der Bestellmengen der Pro- dukte zu befriedigen ist.³ Das Ziel der operativen Produktionsplanung ist es, einen gültigen und machbaren Produktionsplan zu finden, der den vorgegebenen Anforderungen gerecht wird und Freigabetermine sowie -mengen für sämtliche Produkte und Produktkomponenten bestimmt.⁴

Die operative Produktionsplanung lässt sich untergliedern in die Phasen der Produktionsprogrammplanung, der Materialbedarfsplanung, der Durchlaufterminierung und Kapazitätsplanung sowie der Produktionssteuerung⁵.⁶

In der Produktionsprogrammplanung werden die Art und Mengen der in den nächsten Perioden zu produzierenden Erzeugnisse festgelegt.⁷ Es werden für absatzbestimmte Erzeugnisse (Endprodukte) kurzfristige Primärbedarfsmengen anhand von Kundenaufträgen und/oder prognostizierter Nachfrage unter Berücksichtigung von Lagerbeständen ermittelt.⁸

Die ermittelten Primärbedarfsmengen gehen in die Materialbedarfsplanung ein. Es wird bestimmt, in welcher Art und Menge sowie zu welchem Bereitstellungstermin die Verbrauchsfaktoren für die Herstellung der Primärbedarfe benötigt werden; das Ziel ist es, den aus der Produktionsprogrammplanung übernommenen Materialbedarf nach Menge und Termin möglichst exakt zu bestimmen.⁹

Dazu werden die für die Primärbedarfe benötigten Sekundär- und gegebenenfalls auch Ter- tiärbedarfe anhand der Erzeugnisstruktur¹⁰ ermittelt. Dies ist allerdings nur notwendig, wenn die Erzeugnisstruktur mehrstufig ist, also Baugruppen und Einzelteile in das Erzeugnis einge- hen. Anhand der sich ergebenden Bedarfsauflösung kann bestimmt werden, welche Mengen der Komponenten in bestimmten Teilperioden produziert (oder bestellt) werden müssen, um den Primärbedarf zu befriedigen.¹¹ Die Bedarfsmengen desselben Einzelteils, Fertigprodukts oder derselben Baugruppe aus unterschiedlichen Perioden können zu Losen bzw. zu einem Produktionsauftrag zusammengefasst werden.¹² Man versteht in diesem Zusammenhang unter Losgröße bzw. Los die Fertigungsmenge, welche geschlossen zwischen zwei Umrüstvorgän- gen, also ohne Unterbrechung, auf einer Maschine produziert wird.¹³ Dies bedeutet, dass Kundenaufträge oder auch anonyme Bedarfe mit unterschiedlichen Fälligkeitsdaten unter an- derem aus Kosten- und/oder Kapazitätsgründen zu einem Produktionsauftrag zusammenge- fasst werden. Die Ermittlung der optimalen Losgröße (oder Bestellmenge) und damit der Pro- duktionsaufträge ist Aufgabe der Losgrößenplanung.

Die Anfänge der Losgrößenbildung sind bei Harris¹⁴ und im deutschen Raum bei Andler¹⁵ zu finden. Die Andler-Formel bzw. Economic Order Quantity (EOQ) Formel stellt den klassischen Ansatz zur Lösung der einstufigen, unkapazitierten Losgrößenproblematik dar. Ein Entscheidungsproblem für die optimale Produktionsmenge ergibt sich, da die entscheidungsrelevanten Kosten einen entgegengesetzten Verlauf haben.¹⁶ Die losfixen Kosten nehmen mit steigender Produktionsmenge ab, während die Lagerhaltungskosten mit steigender Produktionsmenge und damit zur Einlagerungsmenge linear steigen. Daraus lässt sich ablesen, dass die Gesamtkosten einen zunächst fallenden Verlauf haben, jedoch ab Schnittpunkt von Lagerhaltungs- und losfixen Kosten wieder steigen (vgl. Abbildung 1).

Es soll für einen konstanten, kontinuierlichen Periodenbedarf (auch Nachfrage) ) die optima- le Produktionsmenge x* durch Minimierung der Summe aus Lagerhaltungs- und Rüstkosten - diese ergeben die Gesamtkosten - bestimmt werden.¹⁷ Die Lagerhaltungskosten bestehen aus

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1: Kostenübersicht bei der Losgrößenberechnung¹⁸

Die Eindeckzeit T* ist die Dauer, die ein Los ausreicht, um die gegebene Nachfrage zu befriedigen. Sie sagt also aus, in welchen Zeitabständen neue Lose aufgelegt werden und lässt sich aus dem Quotienten x*/d berechnen.

Es handelt sich um eine Formel, die die Losgrößenproblematik unter den oben erwähnten Voraussetzungen optimal löst, jedoch sind die Prämissen, wie z.B. eine zeitinvariante Perio- dennachfrage, unkapazitierte Ressourcen oder ein unendlicher Planungszeitraum, sehr weit- reichend, so dass sich auf Basis der EOQ Formel weitere Modelle entwickelt haben, welche versuchen, z.B. einen endlichen Planungshorizont oder Mehrproduktproduktion einzubezie- hen.¹⁹

In der Terminplanung werden Durchlaufterminierung und Kapazitätsplanung vorgenommen. Dabei werden in der Durchlaufterminierung für jeden Produktionsauftrag, welcher sich aus der Losgrößenplanung ergibt, und jeden Arbeitsgang die Start- und Endtermine auf den Ma- schinen festgelegt, wobei zunächst von unbeschränkten Ressourcenkapazitäten ausgegangen wird.²⁰ In der Kapazitätsplanung werden Kapazitätsangebot und der aus der detaillierten Ter- minplanung ermittelte Kapazitätsbedarf für die Fertigung gegenübergestellt und die ursprüng- lichen Produktionsaufträge müssen aufgrund unzureichender Kapazitäten gegebenenfalls an- gepasst werden.²¹

In der Produktionssteuerung erfolgt die Freigabe der Fertigungsaufträge, wobei die Aufträge den Betriebsmitteln zugeordnet und die Reihenfolgen der Aufträge auf den Ressourcen festge- legt werden müssen.²² Hier wird auf Basis der in der Durchlaufterminierung festgelegten Start- und Endtermine für jeden Arbeitsgang in der Reihenfolgeplanung entschieden, wann und in welcher Reihenfolge die Produktionsaufträge auf den einzelnen Ressourcen gefertigt werden sollen.²³ Dabei müssen die von der Reihenfolgeplanung zu verfolgenden Ziele grund- sätzlich zum obersten Unternehmensziel beitragen,²⁴ welches sich mit Hilfe der Zielsetzung Minimierung der entscheidungsrelevanten Kosten in der Reihenfolgeplanung fortsetzt.²⁵ Aus dieser Zielsetzung haben sich für die Reihenfolgeplanung unterschiedliche zeit- oder men- genbezogene Ersatzziele²⁶ herausgebildet, die in der Regel mittels heuristischer Verfahren gelöst werden.

Das hier aufgezeigte sukzessive Planungsverhalten kann die Aufgaben der Produktionspla- nung für die Praxis nicht befriedigend lösen, da die verfügbaren Ressourcenkapazitäten erst spät in den Planungsphasen erfasst und in die Planung einbezogen werden. Aus diesem Grund haben sich in den letzten Jahren in der Literatur verstärkt Modelle der Produktionsplanung herausgebildet, die mehrere Schritte der hierarchisch aufgebauten, operativen Produktionspla- nung simultan betrachten.

Im kommenden Kapitel 3 der vorliegenden Arbeit werden zunächst unterschiedliche simulta- ne Planungsmodelle mit einstufiger Erzeugnisstruktur und beschränkter Ressourcenkapazität vorgestellt, um diese dann im Verlauf des Kapitels auf mehrstufige Produktionsverfahren zu erweitern.

3 Analyse simultaner Losgrößen- und Reihenfolgepla- nungsmodelle

3.1 Grundlagen der Losgrößen- und Reihenfolgeplanung

Im Allgemeinen werden die Losgrößen sowie die Produktionsreihenfolge im Rahmen der kurzfristigen Planung bestimmt.²⁷ Beide Planungsvorgänge laufen in der Regel sukzessive ab. Dabei erfolgt die Losgrößenbildung in der Materialbedarfsplanung, während die Reihenfolgeplanung in der Produktionssteuerung stattfindet. Durch die nachgelagerte Einbeziehung der Kapazitäten in die sukzessive Planung kann es geschehen, dass bis dato gültige Produktionspläne ungültig werden, da die gegebenen Kapazitäten für die geplante Fertigung nicht ausreichen. Aus diesem Grund ist es sinnvoll, Losgrößen und Auftragsreihenfolge der Produkte simultan unter Berücksichtigung von Ressourcenkapazitäten zu planen.

Es muss zwischen den Modellen zur reinen Losgrößenplanung und den Modellen zur simultanen Losgrößen- und Reihenfolgeplanung unterschieden werden, wobei letztere immer dann erforderlich werden, wenn bei einer Umrüstung der Ressource reihenfolgeabhängige Rüstkosten und -zeiten entstehen, da in diesem Fall reihenfolgeabhängige Rüstkosten sowohl die Auftragsreihenfolge auf den Ressourcen als auch die Losgrößen beeinflussen.²⁸ Kapazitierte Losgrößen- und Reihenfolgemodelle basieren auf der Annahme, dass die Produktionsressourcen (auch Maschinen als Synonym) in ihrer Kapazität beschränkt sind.

Die Klassifikation der Modelle kann hinsichtlich unterschiedlicher Merkmale erfolgen: So werden u.a. die Anzahl der Ressourcen (Ein- oder Mehrmaschinen-Fall), die Erzeugnisstruktur (ein- oder mehrstufig), die Art des Planungshorizonts (unendlich oder endlich) und die Zeitskala (diskret oder kontinuierlich) differenziert.²⁹ Weitere Kriterien können die Anzahl der Produkte, die Maschinenkapazität (kapazitiert oder unkapazitiert) oder die Anzahl der Produktionsstufen sein.³⁰ Zusammenfassend können die Modelle nach zeitlichen, ressourcenoder produkttechnischen Merkmalen klassifiziert werden.³¹

Hinsichtlich der Anzahl der bis zur Fertigstellung des Endprodukts zu durchlaufenden Ar- beitsgänge wird die simultane Losgrößen- und Reihenfolgeplanung in einstufige oder mehr- stufige Modelle unterschieden. Bei den einstufigen Problemen werden nur die Endprodukte betrachtet, während bei mehrstufigen Modellen alle Produkte, Baugruppen sowie Einzelteile einer Erzeugnisstruktur simultan bestimmt werden.³² Bestehende Zusammenhänge zwischen Endprodukten und Baugruppen sowie Einzelteilen bei mehrstufiger Erzeugnisstruktur können grafisch, tabellarisch oder in Matrixform dargestellt werden, wobei eine mögliche grafische Darstellungsform der Gozintograph ist.³³ Ausgangspunkt für die Darstellung der Erzeugnisstruktur ist die in der Materialbedarfsplanung ermittelte Stückliste, die angibt, welche Bauund Einzelteile in welchen Mengen in das Endprodukt eingehen.

Man differenziert die Erzeugnisstrukturen in vier unterschiedliche Grundformen (vgl. Abbildung 2)³⁴: In der linearen Erzeugnisstruktur hat jedes Erzeugnis maximal einen direkten Nachfolger und einen direkten Vorgänger. In der konvergierenden Erzeugnisstruktur besitzt jedes Erzeugnis höchstens einen direkten Nachfolger aber mehrere direkte Vorgänger, während bei der divergierenden Erzeugnisstruktur jedes Produkt höchstens einen direkten Vorgänger aber mehrere direkte Nachfolger haben kann. In der generellen Erzeugnisstruktur kann jedes Produkt mehrere direkte Vorgänger und Nachfolger haben.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2: Gozintograph-Darstellungen für unterschiedliche Erzeugnisstrukturen³⁵

Darüber hinaus werden die hier betrachteten diskreten Modelle mit endlichem Planungshorizont und entsprechend diskreten Zeitintervallen in der Literatur in „Small Bucket“- und „Big Bucket“-Probleme unterteilt.³⁶ Die Unterscheidung in „Small Bucket“- und „Big Bucket“Modelle betrifft die relative Länge der Zeitperioden im Hinblick auf die erwartete Länge des individuellen Produktionsloses.³⁷ „Small Bucket“- Probleme unterteilen den endlichen Planungshorizont in eine größere Anzahl kürzerer Zeitintervalle und unterstellen in der Regel, dass lediglich ein, höchstens aber zwei Produkte pro Periode gefertigt werden können.³⁸ In „Small Bucket“-Modellen kann der Rüstzustand über Periodengrenzen hinweg erhalten werden.³⁹ „Small Bucket“-Modelle planen aus diesem Grund nicht nur die optimalen Losgrößen der Produkte, sondern legen simultan auch die Reihenfolge der Produktionsaufträge fest, da die Zeitintervalle bzw. Perioden sequentiell angeordnet sind.⁴⁰

Der Planungshorizont in „Big Bucket“-Problemen beinhaltet wenige längere Perioden.⁴¹ Dies bedeutet, dass in „Big Bucket“-Modellen die Produktionsvorgänge in der Regel zum Ende einer Periode als abgeschlossen gelten, dass innerhalb der Periode mehrfach gerüstet werden könnte und dass keine Rüstzustände von einer Periode in die darauffolgende übertragen werden.⁴² Es werden also mit Ausnahme der Lagerbestände keine produktionsrelevanten Informationen, wie beispielsweise über den Rüstzustand der Ressource von einer Periode auf eine andere Periode übermittelt. Sofern ein Los eine Periode überdauert, gilt dies dennoch als neues Los, und es muss folglich neu gerüstet werden.

Einen Sonderfall stellt hierbei das General Lot Sizing and Scheduling Problem (GLSP) dar, da es über einen zweistufigen Planungshorizont verfügt. Wenige längere Perioden (Makroperioden) werden in kürzere Teilperioden (Mikroperioden) unterteilt.⁴³ Die Makroperioden verfügen über die Charakteristika der „Big Bucket“-Modelle, während die Mikroperioden die Charakteristika der „Small Bucket“-Modelle haben.⁴⁴

Eine Einordnung der zu betrachtenden, diskreten Modelle in die jeweilige Problematik bietet die folgende Abbildung 3. In Klammern hinter den einzelnen Modellen befinden sich die gängigen Abkürzungen.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3: Klassifikation der Modelle bezüglich des Planungshorizonts⁴⁵

Ziel sämtlicher Modelle der simultanen Losgrößen- und Reihenfolgeplanung ist die Minimie- rung der entscheidungsrelevanten Kosten, zu welchen immer die Lagerhaltungs- und Rüstkos- ten zählen und welche z.B. um produktionsabhängige Kosten beliebig erweitert werden kön- nen.⁴⁶

Für die simultane Losgrößen- und Reihenfolgeplanung unter der Annahme von Kapazitätsrestriktionen und mehrstufigen Produktionsverfahren ist es notwendig, sich zunächst mit der einstufigen Problematik zu beschäftigen, da viele Lösungsverfahren für mehrstufige Losgrößen- und Reihenfolgeprobleme diese in einstufige, unkapazitierte Teilprobleme, so beispielsweise die Dekompensation (vgl. Abschnitt 5.4) zerlegen.

Mit Ausnahme des Capacitated Lot Sizing Problem (CLSP) sowie dessen Erweiterung um Mehrstufigkeit handelt es sich bei den betrachteten Modellen um Modelle der simultanen Losgrößen- und Reihenfolgeplanung.

Im Folgenden werden zunächst die bekanntesten einstufigen Modelle mit einer „Small Bucket“-Zeitstruktur kurz vorgestellt, das CLSP als „Big Bucket“-Modell und das GLSP ausführlicher. Diese beiden Modelle werden im weiteren Verlauf dieses Kapitels auf mehrstufige Erzeugnisstrukturen und Produktionsstufen erweitert.

3.2 Analyse der simultanen Grundmodelle unter Kapazitätsrestrik- tionen

3.2.1 Das Economic Lot Scheduling Problem

Das Economic Lot Scheduling Problem (ELSP) stellt eine Weiterentwicklung der klassischen Losgrößenproblematik dar, die sich aus dem Umstand ergibt, dass die Annahmen des klassi- schen Losgrößenmodells sehr weitreichend und kaum in der Praxis anzutreffen sind.⁴⁷ Da Ressourcen normalerweise mehrere Produkte bearbeiten, müssen die Produktionsreihenfolgen der Lose berücksichtigt werden.⁴⁸ Es handelt sich beim ELSP um ein einstufiges Mehrpro- duktproblem, welches die Kapazität der Ressource einbezieht.⁴⁹ Betrachtet werden in einem unendlichen Fertigungshorizont mehrere Produkte, die auf einer Maschine mit endlicher Pro- duktionsgeschwindigkeit produziert und für die konstante, kontinuierliche Nachfrageraten angenommen werden. Das ELSP ist ein statisches Modell, in welchem unter der Annahme von reihenfolgeunabhängigen Rüstzeiten sowie zeitlich konstanten Rüst- und Lagerkosten die herzustellenden Produkte disponiert werden.⁵⁰ Um Überschneidungen auf der Ressource zu vermeiden, wird für alle Produkte ein einheitlicher Produktionszyklus festgelegt.⁵¹

Da der Bedarf während des Produktionszyklus gedeckt werden muss und jedes Produkt einmal innerhalb des Produktionszyklus produziert werden soll, ergibt sich die optimale Losgröße als Produkt aus Nachfragerate und optimaler Zykluszeit.

Sollen auch mögliche Rüstzeiten berücksichtigt werden, ergibt sich hinsichtlich der Zykluszeit eine Nebenbedingung, die besagt, dass diese ausreichen muss, um sämtliche Rüst- und Produktionsvorgänge durchführen zu können.

Das ELSP ist beliebig erweiterbar, und so können z.B. reihenfolgeabhängige Rüstkosten oder variable Kapazitäten recht einfach integriert werden. Die Prämissen des ELSP, wie z.B. ein unendlicher Planungszeitraum, eine konstante Nachfrage sowie zeitlich konstante Kosten sind in der Regel nur in der Massenproduktion anzutreffen,⁵² so dass sich ausgehend vom ELSP weitere Modelle zur simultanen Losgrößen- und Reihenfolgeplanung für unterschiedlichste Produktionsszenarien herausgebildet haben. Ein Überblick über das ELSP, mögliche Erweite- rungen und Lösungsansätze finden sich bei Elmaghraby (1978) oder bei Hauth/Schneeweiß (1997).

3.2.2 Das Discrete Lot Sizing and Scheduling Problem

Das Discrete Lot Sizing and Scheduling Problem (DLSP) ist ein „Small Bucket“-Modell, wo- bei jedoch die Prämissen der stationären Nachfrage und der unbegrenzten Produktionskapazi- tät aufgehoben werden und von einer dynamischen Nachfrage und einem endlichen Planungs- horizont ausgegangen wird.⁵³ Der Planungshorizont wird in kleine Zeitfenster unterteilt, so dass höchstens ein Produkt innerhalb dieser Periode gefertigt werden kann und dafür die ge- samte Ressourcenkapazität verbraucht („Alles-oder-Nichts“-Annahme) bzw. sofern in einer Periode gerüstet werden muss, wird die komplette Periode für den Rüstvorgang reserviert.⁵⁴ Durch diese Beschränkung auf ein Produkt je Periode werden gleichzeitig auch die Reihen- folgen von Produktionslosen beachtet, da die Perioden sequentiell angeordnet sind.⁵⁵ Ein Los kann also über mehrere Perioden hinweg produziert werden, und es fallen nicht in jeder Peri- ode neue Rüstkosten an, sondern immer nur dann, wenn auch tatsächlich ein neues Los aufgelegt wird.⁵⁶ Anders ausgedrückt, ein Los ist immer ein ganzzahliges Vielfaches einer kompletten Periodenproduktion.⁵⁷ Statt einer kontinuierlichen Produktionsvariablen Z wird vielfach eine Binärvariable ` eingesetzt.⁵⁸ Es wird verlangt, dass die Nachfrage entweder aus Lagerbeständen oder aus der laufenden Produktion befriedigt werden muss.

Um dies modellieren zu können, werden zwei Binärvariablen ` und _ benötigt, die ange- ben, dass die Maschine zu Beginn der Periode für Produkt gerüstet ist (` \ 1; 0 sonst) oder dass die Maschine in einer Periode für ein Produkt umgerüstet wird (_ \ 1; 0 sonst).

Es werden für die Modellierung des DLSP die folgenden Notationen verwendet, die für die gesamte Arbeit durchgängig beibehalten und gegebenenfalls erweitert werden:

Symbolverzeichnis:

Abbildung in dieser Leseprobe nicht enthalten

In den Lagerbilanzgleichungen (1-1) wird verlangt, dass die Nachfrage entweder aus Lagerbeständen oder aus der laufenden Produktion befriedigt werden muss. Die Restriktionen (1-2) bilden die „Alles-oder-Nichts“-Annahme ab. Die Kapazitätsrestriktionen (1-3) stellen sicher, dass höchstens ein Produkt pro Mikroperiode hergestellt werden kann. Die Ungleichungen (1-4) zusammen mit der Zielfunktion sollen bewirken, dass die Variable _ dann den Wert 1 annimmt, wenn in Periode für das Produkt neu gerüstet wird, also nur dann Rüstkosten anfallen, wenn die Ressource umgerüstet wird. Für _ wird lediglich verlangt, dass diese Variable nicht negativ ist (1-6). Dies ergibt sich aus der Kombination der Restriktionen in (1-4) und (1-6) zusammen mit der Zielfunktion.

Dabei hat das DLSP den Vorteil, dass minimale Durchlaufzeiten, wie z.B. Transport- oder Kühlzeiten recht einfach berücksichtigt werden können, da das Modell kurze Zeitspannen betrachtet.⁵⁹ Das DLSP führt zwar eine Reihenfolgeplanung durch, es unterliegt jedoch der Einschränkung einer „Alles-oder-Nichts“-Produktion, wodurch häufig eine unnötige Voraus- produktion stattfindet.⁶⁰

Das DLSP wird im deutschen Raum vor allem von Fleischmann (1990, 1994) behandelt, der ein Lösungsverfahren entwickelt, welches dieses Modell exakt löst und das Grundmodell um reihenfolgeabhängige Rüstkosten erweitert.

Jans/Degraeve (2004) entwickeln für das Modell Rüstzeiten, die kürzer als eine Periode sind. Es werden Fehlmengen wie auch alternative, nicht identische Ressourcen berücksichtigt. Aufgrund der günstigen Modelleigenschaften existieren weiterhin zahlreiche Lösungsansät- ze⁶¹. So ermittelt Fleischmann (1990) durch Lagrange-Relaxation untere Schranken und be- stimmt in jeder Subgradienten-Iteration heuristisch zulässige Lösungen. In seiner Anschluss- arbeit modifiziert Fleischmann (1994) das DLSP mit reihenfolgeabhängigen Rüstkosten mit- tels Reformulierung in ein Travelling Salesman Problem mit Zeitfenstern, welches dann mit- tels Lagrange-Relaxation in kürzeste Wege Probleme mit Zeitfenstern zerlegt und mit dyna- mischer Programmierung exakt gelöst werden.

3.2.3 Das Continuous Setup Lot Sizing Problem

Das Continuous Setup Lot Sizing Problem (CSLP) geht ebenso wie das DLSP von der Einschränkung aus, dass auf der betrachteten Maschine in jeder Periode maximal ein Produkt produziert werden kann.⁶² Jedoch wird die restriktive „Alles-oder-Nichts“-Bedingung (1-2) des DLSP aufgegeben, so dass das CSLP realistischer erscheint, Lose jeder beliebigen Größe zwischen Null und der Ressourcenkapazitätsgrenze produziert werden können (2-2) und dementsprechend durch die Aufrundung auf volle Periodenproduktionen keine Endbestände anfallen.⁶³ Demnach ist das CSLP die Verallgemeinerung des DLSP.⁶⁴

Der einzige Unterschied zum DLSP ist die Aufgabe der „Alles-oder Nichts“-Bedingung (1-2), welche im CLSP unter Anwendung derselben Zielfunktion und der übrigen Restriktionen aus dem DLSP durch folgende Nebenbedingung ersetzt wird:

Abbildung in dieser Leseprobe nicht enthalten

(2-2)

Es wird nicht verlangt, dass die in einer Periode gefertigte Produktsorte bis zum Ende der Periode produziert werden muss. Die sich ergebenden Maschinenstillstandszeiten können frei terminiert werden, so dass Zustandsänderungen nicht mehr fix an ein Zeitraster gekoppelt sind.⁶⁵

Einer der Nachteile des CSLP ist, dass, sofern die Ressource nicht voll ausgelastet wird, die verbleibende Kapazität ungenutzt bleibt,⁶⁶ also Leerstandszeiten entstehen. Diesem Umstand soll das Proportional Lot Sizing and Scheduling Problem Abhilfe schaffen.

3.2.4 Das Proportional Lot Sizing and Scheduling Problem

Das Proportional Lot Sizing and Scheduling Problem (PLSP) basiert auf denselben Annah- men wie das DLSP und das CSLP, jedoch mit dem Unterschied, dass pro Periode (höchstens) einmal gerüstet werden darf, so dass in einer Periode maximal zwei unterschiedliche Produkte hergestellt werden können.⁶⁷ Die im Vergleich zum CSLP verbleibende Kapazität der Ma- schine kann für die Umrüstung der Ressource und Herstellung eines weiteren Produktes ge- nutzt werden, so dass es nicht zu unerwünschten Maschinenstillstandszeiten kommen muss.⁶⁸

Bei der Modellierung des PLSP werden die Zielfunktion sowie die Nebenbedingungen des DLSP übernommen, Kapazitätsrestriktionen (1-2) durch (3-2) ersetzt sowie eine Nebenbedingung eingefügt:

Abbildung in dieser Leseprobe nicht enthalten

(3-2)

Abbildung in dieser Leseprobe nicht enthalten

(3-3)

In den Kapazitätsrestriktionen (3-2) wird sichergestellt, dass die Produktionsvorgänge die verfügbare Kapazität der Ressource nicht übersteigen. Die Restriktionen (3-3) verknüpfen die Produktionsvariablen Z mit den Rüstzustandsvariablen ` , so dass eine Produktion des Produkts in der Periode nur erlaubt ist, wenn für Produkt entweder zu Beginn der Periode oder am Ende der Periode V 1 gerüstet wurde.⁶⁹

Durch Aufgabe der Restriktion, dass lediglich ein Produkt pro Periode gefertigt werden kann, ist das PLSP sowohl dem DLSP als auch dem CSLP überlegen, so dass eine optimale Lösung des PLSP mindestens so gut wie die Lösung eines DLSP oder CSLP ist.⁷⁰ Die Lösungen des DLSP bzw. CSLP stellen also immer die obere Schranke für die Lösung eines PLSP dar.

Für das PLSP gibt es zahlreiche Erweiterungen. So wird das vorgestellte Grundmodell u.a. von Drexl/Haase (1995) um reihenfolgeabhängige Rüstkosten und mehrere Maschinen, von Kimms (1996) um mehrstufige Erzeugnisstrukturen und von Drexl/Kimms (1997) um mehrstufige Erzeugnisstrukturen, mehrere Maschinen, parallele Maschinen, mehrfache Ressourcen und teilweise erneuerbare Ressourcen erweitert.

3.2.5 Das Capacitated Lot Sizing Problem

3.2.5.1 Das Grundmodell des Capacitated Lot Sizing Problem

Das CLSP ist ein Standardmodell zur dynamischen, kapazitierten MehrproduktLosgrößenplanung. Es ist in seiner Grundversion jedoch nicht für die simultane Losgrößenund Reihenfolgeplanung geeignet, so dass diese Grundversion z.B. um reihenfolgeabhängige Rüstkosten oder Übertragung der Rüstzustände erweitert werden sollte, um simultan auch die Reihenfolge einplanen zu können.

Beim CLSP sind mehrere unterschiedliche Produkte auf einer kapazitierten Ressource so einzuplanen, dass die vorgegebene dynamische Nachfrage ) nach den einzelnen Produkten in einer bestimmten Periode ohne Nachlieferungen und unter Einhaltung der Kapazitäts- restriktionen ( erfüllt werden kann. Es sollen die einzelnen Produktionsmengen Z für jede Teilperiode bestimmt werden, so dass die Summe aus Rüst- und Lagerhaltungskosten mini- mal wird.

Für das CLSP ergibt sich dann folgendes Modell:

Symbolverzeichnis:

Abbildung in dieser Leseprobe nicht enthalten

Die Lagerbilanzgleichungen (4-1) besagen, dass der Bedarf nach einem Produkt einer Periode durch die Lagerbestandsmengen zuzüglich des in der betrachteten Periode produzierten Gutes gedeckt werden muss. Zusammen mit den Nichtnegativitätsbedingungen (4-4) wird sichergestellt, dass die Bedarfsdeckung ohne Nachlieferungen erfolgt.⁷¹ Die Kapazitätsrestriktionen (4-2) stellen sicher, dass die maximal verfügbare Maschinenkapazität durch benötigte Produktions- und Rüstzeiten nicht überschritten werden. Die Rüstbedingungen (4-3) sorgen dafür, dass immer dann, wenn produziert wird, die Ressource gerüstet werden muss. Um dies sicherzustellen, muss groß genug sein, um die Losgröße von Produkt in Periode nicht zu begrenzen.⁷² Darüber hinaus ist darauf zu achten, dass zu Beginn der Produktion sowie zum Abschluss der Produktion der betrachteten Produkte das Lager komplett geräumt sein muss (4-5) und es sich bei _ um eine Binärvariable handelt (4-6).

Das CLSP ist, wie bereits oben klassifiziert, ein „Big Bucket“-Modell, welches die Auflage von Losen mehrerer oder aller Produkte innerhalb einer Periode zulässt. Das Modell in seiner Grundversion ist für eine simultane Betrachtung der Losgrößen- und Reihenfolgeplanung nicht geeignet.⁷³ Es wurde jedoch vielfältig erweitert, so dass zumindest partiell Reihenfolge- entscheidungen einbezogen werden können, wie es im Capacitated Lot Sizing Problem with Linked Lot Sizes (vgl. Abschnitt 4.1) oder im Capacitated Lot Sizing Problem with Sequence Dependent Setup Costs der Fall ist.

3.2.5.2 Erweiterung des CLSP um reihenfolgeabhängige Rüstkosten

Das Capacitated Lot Sizing Problem with Sequence Dependent Setup Costs (CLSD, kapazi- tiertes Losgrößenproblem mit reihenfolgeabhängigen Rüstkosten) erstellt im Gegensatz zum CLSP aufgrund von reihenfolgeabhängigen Rüstkosten und -zeiten eine komplette Reihenfol- ge aller in einer Periode zu produzierenden Güter.⁷⁴ Wenn die Ressource Produkte unter- schiedlicher Produktfamilien produziert, kann es sein, dass sich die Rüstkosten zwischen den einzelnen Produkten und Produktgruppen stark unterscheiden.⁷⁵ Um diese reihenfolgeabhän- gigen Rüstkosten und -zeiten zu berechnen, wird vorausgesetzt, dass die Dreiecksungleichung

M H M: W M: hinsichtlich der reihenfolgeabhängigen Rüstkosten (analog bei den Rüstzeiten L ) erfüllt ist. Die Dreiecksungleichung stammt aus der Graphentheorie und besagt, dass die direkte Umrüstung zwischen zwei Produkten % und nicht mehr Aufwand bzw. Kosten verursachen darf als ein Umweg über Produkt r.⁷⁶

Die grundlegenden Prämissen des CLSD sind dieselben wie beim CLSP. Jedoch lässt das CLSD kontinuierliche Losgrößen auch über Periodengrenzen hinweg zu, und der Rüstzustand bleibt bei Stillstand der Maschine erhalten.

Folgende zusätzliche Notation zur Erstellung des Modells wird verwendet:

Symbolverzeichnis:

Abbildung in dieser Leseprobe nicht enthalten

Wie auch im CLSP sollen die entscheidungsrelevanten Kosten minimiert werden. Die Lager- bilanzgleichungen (5-1) ändern sich nicht. Die Kapazitätsrestriktionen (5-2) beziehen statt der reihenfolgeunabhängigen Rüstzeiten nun reihenfolgeabhängige Rüstzeiten ein. Die Produkti- onsbedingungen (5-3) besagen, dass ein Produkt in einer Periode produziert wird, wenn für dieses Produkt in der Periode umgerüstet (_ \ 1> oder der Rüstzustand aus der vorange- gangenen Periode V 1 übernommen wurde (` , g2 \ 1>. Die Gleichungen (5-4) stellen si- cher, dass ein eindeutiger Rüstzustand am Ende einer Periode gegeben ist. Da die Lossequenz noch nicht gebildet wurde, wird diese mittels der Bedingungen (5-5) und (5-6) festgelegt, wo- bei die Ungleichungen (5-6) dafür sorgen, dass Kurzzyklen innerhalb einer Periode verhin- dert werden.⁷⁷ Die Bedingungen in (5-5) beschreiben die Sequenzen der Rüstvorgänge. Dabei erhält die linke Seite der Gleichung den Wert 1, wenn für Produkt r ein Umrüstvorgang in

Periode vorgenommen [Abbildung in dieser Leseprobe nicht enthalten]oder der Rüstzustand in Periode übernommen wird [Abbildung in dieser Leseprobe nicht enthalten]. In diesem Fall muss der Rüstzustand für Produkt r in die kommende Periode W 1 übernommen werden [Abbildung in dieser Leseprobe nicht enthalten] oder die Maschine wird von Produkt r auf Produkt umgerüstet [Abbildung in dieser Leseprobe nicht enthalten] Die Restriktionen (5-7) bis (5-9) beschreiben die Nichtnegativität und die Binärbedingungen.

Gupta/Magnusson (2005) formulieren das CLSD als gemischt-ganzzahliges Programm und entwickeln ein heuristisches Verfahren zur Lösung dieses Problems. Die Idee hinter diesem heuristischen Verfahren ist, dass eine gültige Initiallösung durch die periodenweise Anwen- dung von Rüstzustandsübertragungen generiert wird. Die darauffolgenden Konfigurationen werden in jeder Periode mittels eines Greedy-Verfahrens (vgl. Abschnitt 5.6) in eine Reihen- folge gebracht. Der letzte Schritt des Verfahrens startet mit der letzten Periode und sucht nach ungenutzter Kapazität in vorangegangenen Perioden. Die Rüst- und Lagerhaltungskosten werden solange verglichen, bis herausgefunden wurde, ob die Gesamtkosten durch Verschie- ben der Fertigung der Produkte in eine frühere Periode reduziert werden können.

3.2.6 Das General Lot Sizing and Scheduling Problem und mögliche Er- weiterungen

Das GLSP ist ein Modell, welches eine Verallgemeinerung der oben genannten Grundmodelle ist und diese als Spezialfälle mit zusätzlichen Restriktionen darstellt.⁷⁸ Es verbindet die Vor- teile der „Small Bucket“-Probleme mit den Vorteilen der „Big Bucket“-Probleme, so dass für die Makroperioden die Vorteile des CLSP als „Big Bucket“-Modell und für die Mikroperio- den die Vorteile der Modelle der simultanen Losgrößen- und Reihenfolgeplanung als „Small Bucket“-Modelle gelten.⁷⁹ Hierzu wird der endliche Planungshorizont O (Anzahl der Makro- perioden) in mehrere kürzere Perioden (Mikroperiode) unterteilt, wobei eine Mikroperiode entweder eine Leerperiode⁸⁰, eine reine Produktionsperiode, eine gemischte Produktions- und Umrüstperiode oder eine Leerperiode mit einer Länge von Null Zeiteinheiten (ZE) ist.⁸¹

Die Länge einer Mikroperiode hängt von der in ihr gefertigten Produktionsmenge ab, womit sichergestellt wird, dass eine Abfolge von Mikroperioden, in denen dasselbe Produkt gefertigt wird, ein Los definiert und die Menge, die während dieser Mikroperioden hergestellt wird, die Größe eines Loses darstellt.⁸² Die Mikroperioden legen also nicht nur die Produktreihenfolge, sondern auch die Losgröße fest.⁸³

Das GLSP berücksichtigt reihenfolgeabhängige Rüstkosten M und -zeiten L sowie je nach Wahl der Inputparameter entweder den Fall der Rüstzustandserhaltung (Conservation of Set- up State; GLSPCS)⁸⁴ oder den des Rüstzustandsverlusts (Loss of Setup State; GLSPLS)⁸⁵.⁸⁶ Betrachtet wird eine Ressource mit begrenzter Kapazität ( , für welche Lose in kontinuierli- cher Größe sowie die dazugehörige Fertigungsreihenfolge bestimmt werden sollen; jeder Um- rüstvorgang von einem Zustand % zu einem anderen Zustand verursacht Rüstkosten und ver- ringert die Kapazität der Maschine.

Die im CLSD gemachte Annahme der Dreiecksbedingung hinsichtlich der Rüstzeiten und -kosten wird fallengelassen, da es Produkte gibt, die Reinigungscharakter haben können, so dass die direkte Umrüstung mehr Zeitaufwand oder Kosten verursacht als der Umweg über das Zwischenprodukt.⁸⁷ Hierfür ist die Einfügung von Mindestlosen %D E für Produkte notwendig, um unnötige Umrüstvorgänge und damit eine falsche Bewertung der Rüstkosten zu vermeiden.⁸⁸ Das Ziel ist die Minimierung der entscheidungsrelevanten Kosten für gegebene dynamische Bedarfe mehrerer Produkte.

Meyr (1999) differenziert in seiner Arbeit das GLSPCS und das GLSP mit reihenfolgeabhängigen Rüstzeiten (GLSPST). Da diese Modelle sich lediglich hinsichtlich der Kapazitätsrestriktionen (6-2), also in der Einbeziehung der Rüstzeiten in die Restriktion, unterscheiden, wird hier das GLSPST vorgestellt.

Aus den vorgenannten Annahmen und der Zielformulierung ergeben sich für das GLSP fol- gende Notation und folgendes Grundmodell für die Annahme der Erhaltung des Rüstzustands:

Symbolverzeichnis:

Abbildung in dieser Leseprobe nicht enthalten ⁸⁹

Die Zielfunktion minimiert die entscheidungsrelevanten Kosten. Die Lagerbilanzgleichungen (6-1) stellen sicher, dass die in den Mikroperioden , welche in Summe eine Makroperiode ergeben, hergestellten Produkte zusammen mit dem Lageranfangsbestand (B , g2) abzüglich des Lagerendbestands (B ) den Periodenbedarf decken. Insofern findet hier ebenfalls eine Verknüpfung der Mikroperioden mit der korrespondierenden Makroperiode statt. Die Kapazi- tätsrestriktionen (6-2) basieren auf den Makroperioden , da die auf die Mikroperioden zu verteilende Kapazität eine Entscheidung des Modells darstellt. Die Produktions- und Rüst- zeitkapazitäten aller Mikroperioden, die zu einer Makroperiode gehören, dürfen verfügbare Ressourcenkapazitäten in der Periode nicht übersteigen. Die Restriktionen (6-3) und (6-5) verknüpfen die Produktionsmengen Z* mit den Rüstvariablen `* und stellen sicher, dass der Rüstzustand am Ende jeder Mikroperiode eindeutig ist. Produkt kann nur produziert werden, wenn die Ressource für das entsprechende Produkt einmalig in einer Mikroperiode gerüstet wurde. Die Ungleichungen (6-4) fordern die Einführung einer Mindestlosgröße, die die Ver- meidung von unnötigen Rüstvorgängen sichern soll. Die Restriktionen (6-6) stellen eine Ver- bindung zwischen der Rüstzustands- und den Umrüstvariablen her. Für die Entscheidungsva- riablen werden Nicht-Negativität (6-7) bis (6-9) und Binärbedingungen (6-10) gefordert.

Das GLSP stellt sicher, dass mehrere, frei terminierbare Lose desselben Produkts in einer Makroperiode in beliebiger Größe aufgelegt werden können und bietet deshalb hohe Freiheitsgrade hinsichtlich der Anzahl und Häufigkeit von Losen je Makroperiode und der Größe und Terminierung von Losen.⁹⁰

Das oben erwähnte GLSPLS unterscheidet sich vom GLSPCS nur durch die Kapazitätsrestriktionen (6-2):

Abbildung in dieser Leseprobe nicht enthalten

Die Makroperiodenkapazität ( ist somit voll auszuschöpfen, so dass zur Bedarfsdeckung nicht benötigte Restkapazitäten entweder zum Aufbau von Lagerbeständen genutzt werden oder die Ressource in den produktionsfreien Nullzustand gesetzt wird.⁹¹

Da das GLSP eine Generalisierung für Losgrößen- und Reihenfolgeplanungsmodelle ist, unterscheidet es sich nur durch Hinzufügen zusätzlicher Nebenbedingungen und in Bezug auf die zeitliche Struktur von den oben vorgestellten Modellen.⁹²

So kann beispielsweise das CLSP durch das GLSPLS ausgedrückt werden, indem die Rüst- kosten und -zeiten als reihenfolgeunabhängig definiert werden [Abbildung in dieser Leseprobe nicht enthalten]und[Abbildung in dieser Leseprobe nicht enthalten]; und die Mindestlosgröße vernachlässigt wird [Abbildung in dieser Leseprobe nicht enthalten] Die „Big Bucket“-Zeitstruktur des CLSP kann durch [Abbildung in dieser Leseprobe nicht enthalten] ausgedrückt werden. Da die Prämisse des CLSP ist, dass zu Beginn jeder Makroperiode ein neues Los aufgelegt werden muss, wird eine zusätzliche Rest riktion in Form von [Abbildung in dieser Leseprobe nicht enthalten] eingeführt, wobei die erste Mikroperiode in der Makrope riode bezeichnet.⁹³

Das einstufige GLSPCS selbst erweitert Meyr (1999) neben den oben erwähnten reihenfolgeabhängigen Rüstzeiten (GLSPST)⁹⁴ auch auf parallele Linien (GLSPPL)⁹⁵. Diese parallelen Produktionslinien decken dasselbe Produktionsspektrum ab, müssen aber nicht unbedingt technisch identisch sein.⁹⁶ Damit kann ein Produkt, ähnlich wie im Mehrmaschinenfall, auf mehreren Produktionslinien hergestellt werden.

3.3 Analyse der mehrstufigen Modelle unter Kapazitätsrestriktio- nen

3.3.1 Grundlagen der mehrstufigen Produktionsverfahren

Es wurden als Einstieg in die Problematik die Losgrößen- und Reihenfolgemodelle für einstu- fige Erzeugnisstrukturen unter Berücksichtigung von Kapazitätsbeschränkungen der produzie- renden Ressource betrachtet. In der Praxis sind jedoch mehrstufige und mehrteilige Erzeug- nis- und Prozessstrukturen vorherrschend, wobei vor allem die Produktionsprozessstrukturen zu berücksichtigen sind.⁹⁷

Um in der Praxis eingesetzt werden zu können, ist es notwendig, dass die Modelle der simultanen Losgrößen- und Reihenfolgeplanung für mehrstufige Produktionsverfahren bestimmten Anforderungen, wie beispielsweise die Interdependenzen zwischen den Produktionsstufen, die Minimierung der Vorlaufzeiten der vorgelagerten Zwischenprodukte oder der Durchlaufzeiten der Endprodukte gerecht werden.⁹⁸

In der mehrstufigen Produktion ist es möglich, Produkte mit ein- oder mehrstufiger Erzeug- nisstruktur zu fertigen. Bei einstufiger Erzeugnisstruktur durchläuft der Einsatzstoff bis zur endgültigen Fertigstellung mehrere Arbeitsgänge, während bei mehrstufiger Erzeugnisstruktur mehrere Einzelteile und/oder Baugruppen auf mehreren Ressourcen gefertigt, montiert und in der höchsten Fertigungsstufe zu einem Endprodukt zusammengesetzt werden.⁹⁹ Hier fallen

¹ Diskrete Entscheidungsprobleme zeichnen sich dadurch aus, dass die Menge der möglichen Entscheidungen abzählbar im Zeitverlauf ist.

² Vgl. Kistner (2003), S. 6.

³ Vgl. Neumann (1996), S. 3.

⁴ Vgl. Günther/Tempelmeier (2005), S. 139 f.

⁵ Vgl. Drexl/Kimms (1997), S. 221.

⁶ Einige Autoren gliedern die in der Produktionssteuerung enthaltene Ablaufplanung (auch Reihenfolgepla- nung oder Maschinenbelegungsplanung) aus und nennen dies Feinplanung.

⁷ Vgl. Günther/Tempelmeier (2005), S. 223.

⁸ Vgl. Neumann (1996), S. 7. Vgl. Corsten (2007), S. 234.

⁹ Vgl. Schuh/Roesgen (2006), S. 40 ff. Vgl. Günther/Tempelmeier (2005), S. 175.

¹⁰ Die Erzeugnisstruktur stellt den Zusammenhang zwischen Fertigerzeugnissen sowie eingehenden Baugrup- pen und Einzelteilen her.

¹¹ Vgl. Günther/Tempelmeier (2005), S. 192.

¹² Vgl. Domschke/Scholl (2005), S. 151.

¹³ Vgl. Popp (1992), S. 42.

¹⁴ Vgl. Harris (1915).

¹⁵ Vgl. Andler (1929).

¹⁶ Vgl. Domschke/Scholl (2005), S. 151.

¹⁷ Vgl. Neumann (1996), S. 28.

¹⁸ Darstellung in Anlehnung an Corsten (2007), S. 449.

¹⁹ Vgl. Günther/Tempelmeier (2005), S. 229 ff.

²⁰ Vgl. Corsten (2007), S. 481.

²¹ Vgl. Corsten, a.a.O., S. 485.

²² Vgl. Vahrenkamp (2004), S. 207.

²³ Vgl. Corsten (2007), S. 488.

²⁴ Vgl. Thommen/Achleitner (2006), S. 108.

²⁵ Vgl. Corsten (2007), S. 490.

²⁶ Ersatzziele können z.B. Minimierung der Durchlaufzeiten, der Zykluszeit, der Maschinenstillstandszeiten usw. sein. - Vgl. Hansmann (2006), S. 350.

²⁷ Vgl. Neumann (1997), S. 27.

²⁸ Vgl. Fandel/Stammen-Hegener (2003), S. 27.

²⁹ Vgl. Gicquel et al. (2008), S. 3.

³⁰ Vgl. Fandel/Stammen-Hegener (2005), S. 880.

³¹ Sehr ausführlich zu den Strukturmerkmalen der Modelle, siehe Meyr (1999), S. 45ff., m.w.N.

³² Vgl. Derstroff (1995), S. 20.

³³ Vgl. Tempelmeier (2006), S. 101.

³⁴ In der Abbildung steht der Buchstabe P für Enderzeugnis, B für Baugruppen und E für Einzelteile.

³⁵ Darstellung in Anlehnung an Günther/Tempelmeier (2005), S. 181.

³⁶ Vgl. Eppen/Martin (1987), S. 832.

³⁷ Vgl. Sürie (2005), S. 7f.

³⁸ Vgl. Fleischmann (1994), S. 395, dort auch Mikroperioden genannt.

³⁹ Vgl. Stadtler (2008), S. 212.

⁴⁰ Vgl. Sürie (2005), S. 8.

⁴¹ Vgl. Domschke et al. (1997), S. 133, auch Makroperioden genannt.

⁴² Vgl. Stadtler (2008), S. 212.

⁴³ Vgl. Meyr (2004), S. 589.

⁴⁴ Vgl. Sürie (2005), S. 23f.

⁴⁵ Darstellung in Anlehnung an Fandel/Stammen-Hegener (2005), S. 881.

⁴⁶ Vgl. Fandel/Stammen-Hegener (2005), S. 880.

⁴⁷ Vgl. Elmaghraby (1978), S. 587.

⁴⁸ Vgl. Günther/Tempelmeier (2005), S. 233.

⁴⁹ Vgl. Drexl/Kimms (1997), S. 223.

⁵⁰ Vgl. Domschke/Scholl (2005), S. 158.

⁵¹ Vgl. Günther/Tempelmeier (2005), S. 233.

⁵² Vgl. Popp (1992), S. 73.

⁵³ Vgl. Popp, a.a.O., S.73f.

⁵⁴ Vgl. Gupta/Magnusson (2005), S 728.

⁵⁵ Vgl. Meyr (1999), S. 60.

⁵⁶ Vgl. Drexl/Kimms (1997), S. 225.

⁵⁷ Vgl. Fleischmann (1990), S. 338.

⁵⁸ Z \ =( /& > P ` : Aufgrund der „Alles-oder-Nichts“-Annahme kann die kontinuierliche Produktionsvariab-le durch den von der Rüstvariablen y abhängigen Ausdruck ersetzt werden.

⁵⁹ Vgl. Drexl/Kimms (1997), S. 226.

⁶⁰ Vgl. Meyr (1999), S. 76.

⁶¹ Ausführlich zum DLSP: Meyr (1999), S. 59-63.

⁶² Vgl. Popp (1992), S. 76.

⁶³ Vgl. Gicquel et al. (2008), S. 8f.

⁶⁴ Vgl. Drexl/Haase (1995), S. 75.

⁶⁵ Vgl. Meyr (1999), S. 64.

⁶⁶ Vgl. Drexl/Kimms (1997), S. 226.

⁶⁷ Vgl. Drexl/Haase (1995), S. 74.

⁶⁸ Vgl. Drexl/Kimms (1997), S. 227.

⁶⁹ Vgl. Drexl/Kimms a.a.O, S. 227.

⁷⁰ Vgl. Kimms (1996), S. 87.

⁷¹ Vgl. Popp (1992), S. 75.

⁷² Vgl. Buschkühl et al. (2008), § 2.1, S. 5.

⁷³ Vgl. Meyr (1999), S. 58.

⁷⁴ Vgl. Quadt/Kuhn (2008), S. 70.

⁷⁵ Vgl. Haase (1996), S. 51.

⁷⁶ Vgl. Fleischmann/Meyr (1997), S. 13.

⁷⁷ Dazu ausführlich: Haase (1996), S. 54.

⁷⁸ Vgl. Meyr (1999), S. 77.

⁷⁹ Vgl. Fandel/Stammen-Hegener (2003), S. 28.

⁸⁰ Die Ressource steht still, ist aber für die Produktion gerüstet.

⁸¹ Vgl. Fandel/Stammen-Hegener (2003), S. 30.

⁸² Vgl. Meyr (2002), S. 279.

⁸³ Vgl. Meyr (2000), S. 313.

⁸⁴ Vgl. Fleischmann/Meyr (1997), S. 13.

⁸⁵ Vgl. Fleischmann/Meyr, a.a.O., S. 13.

⁸⁶ Vgl. Meyr (1999), S. 78.

⁸⁷ Vgl. Fleischmann (1994), S. 397.

⁸⁸ Vgl. Fleischmann/Meyr (1997), S. 13.

⁸⁹ Der in Klammern gesetzte, fett markierte Ausdruck ist der Unterschied zwischen dem GLSPCS, in welchem dieser Ausdruck nicht vorhanden ist, und dem GLSPST.

⁹⁰ Vgl. Meyr (1999), S. 81ff.

⁹¹ Vgl. Fleischmann/Meyr (1997), S. 13.

⁹² Vgl. Meyr (1999), S 76ff.

⁹³ Vgl. Fleischmann/Meyr (1997), S. 13.

⁹⁴ Vgl. Meyr (1999), S. 130ff.

⁹⁵ Vgl. Meyr, a.a.O., S. 159ff.

⁹⁶ Vgl. Meyr, a.a.O., S. 159.

⁹⁷ Vgl. Tempelmeier (2006), S. 203.

⁹⁸ Vgl. Fandel/Stammen-Hegener (2005), S. 879.

⁹⁹ Vgl. Fandel et al. (2004), S. 61.