Losgrößenplanung. Implementierung des MLULSP Modells mithilfe von Xpress


Seminararbeit, 2013

30 Seiten, Note: 2


Leseprobe


Inhaltsverzeichnis

Tabellenverzeichnis

Abbildungsverzeichnis

Abkürzungsverzeichnis

1 Einführung
1.1 Losgrößenprobleme

2 Anwendung
2.1 Modellformulierung
2.2 Auswertung
2.3 Vergleich der Testinstanzen

3 Lösungsmethoden für das MLULS Problem
3.1 Problemstellung
3.2 Lösungsmethoden
3.2.1 Variable Neighborhood Search
3.2.2 Setup shifting rule
3.2.3 weitere Lösungsmethoden

4 Zusammenfassung

Literaturverzeichnis

Tabellenverzeichnis

Tabelle 1: Ergebnisse der Testinstanz 1 (Quelle: eigene Darstellung)

Tabelle 2: Ergebnisse der Testinstanz 2 (Quelle: eigene Darstellung)

Tabelle 3: Ergebnisse der Testinstanz 3 (Quelle: eigene Darstellung)

Tabelle 4: Ergebnisse der Testinstanz 4 (Quelle: eigene Darstellung)

Tabelle 5: Ergebnisse der Testinstanz 5 (Quelle: eigene Darstellung)

Tabelle 6: Ergebnisse der Testinstanz 7 (Quelle: eigene Darstellung)

Tabelle 7: Ergebnisse der Testinstanz 8 (Quelle: eigene Darstellung)

Tabelle 8: Ergebnisse der Testinstanz 9 (Quelle: eigene Darstellung)

Tabelle 9: Ergebnisse der Testinstanz 10 (Quelle: eigene Darstellung)

Abbildungsverzeichnis

Abbildung 1: Klassifizierung von Losgrößenmodellen5

Abbildung 2: Grundformen der Erzeugnisstrukturen8

Abbildung 3: Gesamtkosten der zehn Testinstanzen (Quelle: eigene Darstellung)

Abbildung 4: Gesamtkosten- & Rüstkostenvergleich (Quelle: eigene Darstellung)

Abbildung 5: Klassifizierung von Lösungsansätzen für dynamische Losgrößenprobleme5

Abbildung 6: Schritte des VNS Basisschemas (Quelle: Xiao et al., 2010)

Abbildung 7: setup shifting process for items’ interdependencies (Quelle: eigene Darstellung)

Abbildung 8: Vorgehensweise beim Rüstem mittels setup shifting rule

Abkürzungsverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

1 Einführung

Die vorliegende Seminararbeit hat zum Ziel, dem Leser im Bereich des Produktion und Logistikmanagements praxisrelevante Beispiele mit Unterstützung von theoretischem Input darzustellen.

Nach einer kurzen theoretischen Einleitung in die Thematik der Losgrößenplanung, erfolgt im zweiten Schritt die Implementierung des MLULSP Modells mithilfe von Xpress. Weiteres wird das Modell mittels der 10 beigepackten Testinstanzen getestet. Daraufhin werden die Einzel- und Gesamtergebnisse ausgewertet und analysiert.

Die Software FICOTM Xpress ist eine weltweit führende Modellierungs- und Optimierungssoftware, welche im Entscheidungsmanagement eingesetzt wird um unterschiedliche Optimierungsaufgaben mit optimalen Lösungen, den spezifischen Anforderungen entsprechend, zu generieren. Die Modellformulierung erfolgt mittels der Programmiersprache Xpress Mosel. Für die Lösung und Optimierung von linearen, integer, quadratischen und nicht-linearen Problemen wird der Xpress Optimizer eingesetzt11.

Im dritten Schritt soll durch die Abhandlung der zu diesem Thema bestehenden Literatur „ variable neighborhood search based approach for uncapacitated multilevel lot-sizing problems“ von Xiao, Y., Kaku, I., Zhao, Q., Zhang, R., (2010) ein konzeptioneller Überblick geschafft werden und die zugrunde liegenden Methoden und Lösungswege für das MLULS Modell anschaulich erläutert werden.

Abschließend werden im letzten Kapitel das Fazit und die wesentlichen Punkte dieser Arbeit präsentiert.

1.1 Losgrößenprobleme

Die Einleitung in die Thematik dieser Seminararbeit, erfolgt in einer kurzen Darstellung der Losgrößenprobleme.

Das klassische Losgrößenproblem stammt von Harris und wird als EOQ bzw. AndlerModell bezeichnet. Dieses ist das älteste und zählt zu den bekanntesten Modellen der klassischen Losgrößenplanung. Es dient heute nur mehr zur Veranschaulichung bzw. zum Verständnis der Grundlage anderer Modelle, da eine exakt passende Situation in der Praxis/Realität meist nicht gegeben ist7.

Zu Beginn soll die folgende Grafik die Klassifizierung der Losgrößenmodelle deutlich veranschaulicht

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1: Klassifizierung von Losgrößenmodellen5

Losgrößenmodelle können bezüglich des Informationsgrades, der Produkte, der Maschinen und der Zeitstruktur klassifiziert werden. Auf der obersten Ebene kann man zwischen stochastischen und deterministischen Losgrößenmodellen unterscheiden. Während bei stochastischen Modellen eine Unsicherheit in Hinblick auf Nachfrage und Kapazität miteinbezogen werden, werden bei den deterministischen Modellen jegliche Modellparameter als bekannt angenommen. In der nächsten Ebene wird eine Unterteilung bezüglich der Zeitstruktur vorgenommen. Dabei handelt es sich um eine Unterscheidung zwischen statischen und dynamischen Losgrößenproblemen.

Die statischen Modelle gehen dabei von einem unendlichen Planungszeitraum aus und betrachten den Bedarfsverlauf eines Produktes als gleichbleibend. Dadurch unterstellt wird ein unbegrenzt fortsetzender Betriebsablauf. Diese sind unkapazitiert und einstufig. Im Gegensatz dazu, sind die dynamischen Modelle dadurch gekennzeichnet, dass diese ein endliches Planungsintervall aufweisen und dass es sich um zeitlich, veränderliche Bedarfe handelt. Bei dynamischen Losgrößenproblemen werden einige Parameter zeitlichen Schwankungen ausgesetzt. Die Nachfrage wird hier in der Regel als schwankend angesetzt. In diesem Modell wird eine Unterteilung in T diskrete Planungsperioden vorgenommen, da ein endlicher Planungshorizont unterstellt wird. Dadurch ist eine Losauflage nur in diskreten Zeitpunkten möglich. Weiteres kann, bezogen auf die Produktanzahl, zwischen Einprodukt- und Mehrprodukt-Losgrößenprobleme unterschieden werden. Die Mehrprodukt-Losgrößenprobleme können wiederum, in weiterer Folge, in einstufig und mehrstufig differenziert werden. Wenn zwischen Vorgänger- und Nachfolgerprodukten keine Abhängigkeit existiert, dann handelt es sich um eine einstufige Erzeugnisstruktur. In diesem Fall betrachtet man nur die (End-) Produkte auf einer Fertigungsstufe. Im Gegensatz dazu, liegt ein mehrstufiges Losgrößenproblem vor, wenn die Vorgänger und Nachfolger berücksichtig werden 5.

Der Typ der Erzeugnisstruktur spielt einen wichtigen maßgeblichen Einflussfaktor bezüglich des Komplexitätsgrades, aus diesem Grund wird hier kurz darauf eingegangen. Die Mehrstufigkeit der Erzeugnisstruktur verursacht Interdependenzen zwischen Vor- und Nachfolgerprodukten, welche für die Losgrößenbestimmung im Hinblick auf die Abwägung der Lagerkostenzuwächse gegenüber den Rüstkosteneinsparungen, von großer Bedeutung sind. In Abbildung 2 werden die vier verschiedenen Typen der Erzeugnisstrukturen dargestellt.

Maximal einen direkten Nachfolger und Vorgänger besitzt ein Produkt einer linearen Erzeugnisstruktur. Die konvergierende Erzeugnisstruktur ist dadurch gekennzeichnet, dass es maximal einen direkten Nachfolger gibt, aber mehrere Vorgänger. Die divergierende Erzeugnisstruktur hat im Gegensatz zum vorherigen mehrere Nachfolger, aber einen direkten Vorgänger. Die generelle Erzeugnisstruktur vereint mehrere Merkmale von den oben genannten8.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2: Grundformen der Erzeugnisstrukturen8

Hinsichtlich der eingesetzten Ressourcen im Produktionsprozess kann man beim mehrstufigen Losgrößenproblem weiteres zwischen Einmaschinen- und Mehrmaschinenproblemen unterscheiden. Aus dem Kontext heraus, kann man erahnen worum es sich dabei handelt. Bei den Mehrmaschinen kann eine weitere Differenzierung zwischen Modellen mit Kapazitätsbeschränkungen und ohne Kapazitätsbeschränkungen erfolgen5.

Bei der Losgrößenplanung wird die Minimierung der anfallenden Kosten angestrebt. Dabei kann man zwischen Rüstkosten, Lagerhaltungskosten, Produktionskosten und Überstundenkosten unterscheiden. Grundsätzlich wird das Ziel verfolgt, bei Losgrößenplanungen einen optimalen Kompromiss zwischen Rüst- und Lagerkosten zu schaffen. In dieser Arbeit sind die ersten drei angeführten Kosten relevant weshalb nachstehend kurz darauf eingegangen wird.

Rüstkosten sollen entscheidungstheoretisch bei der Losgrößenplanung den Charakter von Opportunitätskosten annehmen und den entgangenen Nutzen, der mit einem Rüstvorgang verbunden ist, quantifizieren8.

Weiteres kann man Rüstkosten, als jene Kosten definieren, die bei der Durchführung der Umrüstung von Produktionsanlangen anfallen9.

Unter Lagerhaltungskosten versteht man Kosten, die anfallen damit das Material im Lager gehalten werden kann. Sie dienen zur Zeitüberbrückung von Lagergütern, Vorund Nachbereitung und Durchführung des Lagerprozesses und anfallenden Kosten der Bereithaltung und -stellung von Lagerkapazität. In vielen logistischen Entscheidungsproblemen, so auch in der Losgrößenplanung, stellen die Lagerkosten eine zentrale Erfolgsvariable dar10.

Einstufiges unkapazitiertes Losgrößenmodell (SLULSP)

Um das MLULSP besser zu verstehen, wird vorher das einstufige unkapazitierte Losgrößenmodell beschrieben. Dieses Modell bildet die Grundlage für viele weitere dynamische Mehrprodukt-Losgrößenprobleme. Das SLULSP basiert auf folgenden Annahmen:

- Planungszeitraum von T Perioden - Nettobedarfsmenge dt bekannt - Betrachtung liegt auf einem Produkt
- Beschaffungs- bzw. Produktionszeit werden vernachlässigt
- Anfangs- und Endbestand im Lager sind gleich null
- Maschine (Ressource) mit unbeschränkter Kapazität
- Wartezeiten ausgeschlossen
- Jede Produktionslosauflage verursacht Rüstkosten
- Fehlmengen nicht erlaubt
- variable Produktionskosten können berücksichtigt werden

Weiter unten wird angeführt wo der Unterschied zwischen dem SLULSP und MLULSP liegt.

2 Anwendung

2.1 Modellformulierung

Dieser Teil der Arbeit beschäftigt sich mit der Implementierung und der Lösung eines mulit-level uncapacitated lot-sizing problem (MLULSP) mit Hilfe von Xpress. Ferner wird dieses Modell auch als I&L Modell (Inventory and lot-size model) abgekürzt. Die angeführten Parameter sowie die mathematischen Modelle wurden aus dem Paper von Jacobs, F. R. und Khumawala, B. M (1982): „Multi-level lot sizing in material requirements planning: an empirical investigation“ entommen.

Überblick der verwendeten Variablen:

Abbildung in dieser Leseprobe nicht enthalten

Zielfunktion:

Abbildung in dieser Leseprobe nicht enthalten

Nebenbedingungen:

Abbildung in dieser Leseprobe nicht enthalten

Die Zielfunktion hat zur Aufgabe, sowohl die Summe aller Lagerhaltungskosten und Produktionskosten, als auch die Rüstkosten zu minimieren.

Die Nebenbedingung (2) stellt die Lagergleichgewichtsbeschränkung dar. Weiteres veranschaulicht Nebenbedingung (3), dass nur dann produziert werden darf, wenn gerüstet wird. Zuallerletzt bildet die Nebenbedingung (4) die Nichtnegativität.

Der Unterschied zur einstufigen unkapazitierten Losgrößenplanung liegt in der Nebenbedingung (2). Beim SLULSP muss die Lagerbilanzgleichung gleich der Nachfrage sein. Beim MLULSP handelt es sich dabei um die Lagergleichgewichtsbeschränkung, die gleich dem Lagerendbestand sein soll.

2.2 Auswertung

In diesem Kapitel werden die Auswertungen, die auf Basis der oben angeführten Modellformulierungen in Xpress eingegeben wurden, dargestellt. Durch die Eingabe der beigelegten zehn Testinstanzen gelangte man zur optimalen Lösung, was die Gesamtkosten darstellt. Die untere Grafik (Abbildung 1) zeigt die Gesamtkosten aller Testinstanzen. Die Entscheidungsvariablen, die daraus resultierten, sind zum einen die Binärvariable Yit, Xit und Iit die beschreibt, ob ein Rüstvorgang auftritt oder nicht. Bei den anderen zwei Variablen handelt es sich zum einen, um die Losgröße von Produkt i in Periode t (Xit) und zum anderen, um den Lagerbestand (Iit) von Produkt i in Periode t.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3: Gesamtkosten der zehn Testinstanzen (Quelle: eigene Darstellung)

Die Ergebnisse, der hier angeführten Testinstanzen, basieren alle auf folgenden Parameterwerten

- Planungszeitraum T=4

- Anzahl der Produkte N=10

Die Zielfunktion, welche die wenigsten Kosten aufweist, stammt aus zwei Testinstanzen. Dabei handelt es sich um Testinstanz 1 (G0141111) und um Testinstanz 6 (G0141211). Diese zwei haben mit Abstand die minimalsten Kosten, mit 2.180. Was auf die Rüstkosten zurückzuführen ist. Im nächsten Kapitel kann man erkennen, dass diese beiden Instanzen für jedes Produkt und in jeder Periode gerüstet werden. Die höchsten Kosten wiederum spiegeln sich in der Testinstanz 8 wider. Die zweithöchsten Kosten, wie man in der obigen Abbildung erkennen kann, bringt die Instanz 3, mit 15.530, mit sich. Die Instanzen 4, 5, 7 und 10 weißen ein ähnliches Bild auf. Die Gesamtkosten hierbei liegen zwischen 8.148 und 10.466.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4: Gesamtkosten- & Rüstkostenvergleich (Quelle: eigene Darstellung)

Die obenstehende Abbildung zeigt die Gesamtkosten im Vergleich zu den Rüstkosten. Da in den Testinstanzen 1 und 6 die gleichen Daten vorkommen, ist es auch nicht überraschend, dass diese Instanzen auch die gleichen Werte hervorrufen. In diesen beiden Testinstanzen wird in jeder Periode und für jedes Produkt gerüstet. Dies ist auch der Grund warum hier die Gesamtkosten gleich den Rüstkosten sind. Testinstanz 8 zeigt mit Abschnitt die höchsten Gesamt- und Rüstkosten. Die Differenz zwischen den beiden Werten sind jeweils die Lagerkosten.

2.3 Vergleich der Testinstanzen

Testinstanz 1/Testinstanz 6

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 1: Ergebnisse der Testinstanz 1 (Quelle: eigene Darstellung)

Da die Testinstanzen 1 und 6 die gleichen Daten hervorbringen, wurden sie auch hier zusammengefasst. Diese Testinstanzen weisen, wie schon oben erwähnt, die minimalsten Gesamtkosten auf. Hier kann man erkennen, dass in jeder Periode für jedes Produkt gerüstet wird. die Lagerendbestand beträgt überall 0. Weiteres weist diese Instanz in allen Perioden und bei allen Produkten eine Losgröße auf.

Testinstanz 2

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 2: Ergebnisse der Testinstanz 2 (Quelle: eigene Darstellung)

Diese Testinstanz zeigt, dass jeweils in der ersten und dritten Periode für jedes Produkt gerüstet wird. Die optimalen Kosten verlaufen sich hier auf 6678. Zum Verständnis wird die binäre variable Y aus der Tabelle 2 erklärt. Y (1,t) zeigt wann das Produkt 1 gerüstet wird. Dabei nimmt Y den Wert 1 an wenn gerüstet wird, sonst 0. Die vier Werte in der eckigen Klammer stellen jeweils die Perioden dar. Wie schon erwähnt wird hier in Periode 1 und 3 gerüstet. Losgrößen fahlen hier für jedes Produkt unterschiedlich aus. Für X (1,t) kommen Losgrößen in Periode 1 und 3 vor

Testinstanz 3

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 3: Ergebnisse der Testinstanz 3 (Quelle: eigene Darstellung)

Hier wird mit Abstand am wenigsten gerüstet. Losgrößen fallen jeweils nur in der ersten Periode bei jedem Produkt auf. Der Lagerbestand ist hier ab dem fünften Produkt gleich null. Die optimalen Kosten belaufen sich hier auf 15530, was auf die hohen Rüstkosten zurückzuführen ist.

Die weiteren Instanzen werden hier nicht weiter beschrieben. Sie sind zwar in der Arbeit inkludiert, aber es würde den Umfang der Arbeit sprengen, wenn auf jede einzelne näher eingegangen wird.

Testinstanz 4

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 4: Ergebnisse der Testinstanz 4 (Quelle: eigene Darstellung)

Testinstanz 5

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 5: Ergebnisse der Testinstanz 5 (Quelle: eigene Darstellung)

Testinstanz 7

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 6: Ergebnisse der Testinstanz 7 (Quelle: eigene Darstellung)

Testinstanz 8

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 7: Ergebnisse der Testinstanz 8 (Quelle: eigene Darstellung)

Testinstanz 9

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 8: Ergebnisse der Testinstanz 9 (Quelle: eigene Darstellung)

Testinstanz 10

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 9: Ergebnisse der Testinstanz 10 (Quelle: eigene Darstellung)

3 Lösungsmethoden für das MLULS Problem

3.1 Problemstellung

Die nachstehend beschriebene Problemstellung des MLULSP basiert auf der Publikation von Xiao, Y., Kaku, I., Zhao, Q., Zhang, R. „ variable neighborhood search based approach for uncapacitated multilevel lot-sizing problems“ und wird in diesem Teil der Arbeit tiefergehend behandelt Einführend in die Thematik, hat die Materialbedarfsplanung zur Aufgabe, die für die Produktion benötigen Ressourcen nach Art und Menge zu bestimmen und fristgerecht bereitzustellen. In diesem Zusammenhang existieren unterschiedliche Vorgehensweisen und Planungsverfahren. In weiterer Folge werden für die Produktion Losgrößen bestimmt. Eine klassische und etablierte Losgrößenregel ist die lot-for-lot rule. Darüber hinaus bestehen in der Literatur noch zahlreiche einstufige Losgrößenregeln3. Diese Regeln werden wiederum bei Losgrößenproblemen und Heuristiken, Verfahren um umfassende Optimierungsprobleme zu lösen, eingesetzt 12. Eines von vielen Losgrößenproblemen ist das multi-level lot-sizing problem (MLLS).

Das MLLS Problem eines der bedeutendsten und gängigsten Produktionsprogrammprobleme in der Materialbedarfsplanung und befasst sich mit der Bestimmung der Losgrößen über einen bestimmten Planungszeitraum. Darüber hinaus ist das MLLS Problem ein Optimierungsproblem, welches grundsätzlich in zwei verschiedenen Kategorien eingeteilt werden kann. Die Kategorisierung erfolgt nach Produktstrukturen und Kapazitätsstrukturen. Produktstrukturen können beispielsweise in einstufige-, serielle-, fertigungs- und allgemeine Systeme und Kapazitätsstrukturen in einstufige und mehrstufige Losgrößenprobleme eingeteilt werden. Diese können wiederum kapazitierte oder unkapazitierte Ressourcen aufweisen. Insofern liegt der wesentliche Unterschied zwischen dem MLLS und dem unkapazitertem MLLS Problem in der Verfügbarkeit der Ressourcen.

Dennoch wird das MLULSP weitgehend in der Praxis genützt, da bei der Implementierung von kapazitierten mehrstufigen Losgrößenproblemen den Unternehmen die benötigten Daten nicht einwandfrei zur Verfügung stehen oder diese schwer zu sammeln sind6. Dem ungeachtet, wird in all den oben genannten Modellen das ökonomische Ziel verfolgt, die Gesamtkosten zu minimieren und zugleich angenommen, dass die Nachfrage genau ausgewiesen ist4.

3.2 Lösungsmethoden

Um Optimierungs- oder Losgrößenprobleme zu lösen werden grundsätzlich Algorithmen herangezogen1. Algorithmen sind genau definierte Rechen- und Handlungsvorschriften die zur Lösung eines Problems angewendet werden. Weiteres existieren zahlreiche Metaheuristikten, die zur Lösung von Optimierungsproblemen beitragen. Dabei wird für ein nicht spezifisches, sprich beliebiges Optimierungsproblem in einem Suchprozess schrittweise nach einer verbesserten Lösung gesucht. Bedeutende Metaheuristikten sind beispielsweise der Ameinsenalgorithmus, Evolutionäre Algorithmen, das Simulated Annealing, die Tabusuche und das Variable Neighborhood Search12.

In nachfolgender Abbildung werden die verschiedenen Lösungsmethoden der verschiedenen Arten von kapazitierten Losgrößenproblemen nach Buschkühl et al. (2008) dargestellt. Dabei werden die algorithmischen Lösungsansätze in fünf Hauptgruppen, diese wiederum in Subgruppen, unterteilt. Zur Lösung der oben beschriebenen Problemstellung ist allein die vierte Kategorie relevant, in der metaheuristische Lösungsansätze dargestellt werden. Dazu zählt das Nachbarschaftssuchverfahren als auch das populationsbasierte Verfahren5. Eine weitere Möglichkeit um unkapazitierte Losgrößenprobleme zu lösen, wäre die zweite Kategorie, die Lagrange-Heuristiken8, auf welche später kurz eingegangen wird.

In diesem Zusammenhang wird bei der Ausarbeitung dieser Arbeit der variable neighborhood search (VNS) Algorithmus verwendet, um das unkapazitierte MLLS Problem zu lösen6. Dieser wird anschließend mittels der Optimierungssoftware Xpress implementiert.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 5: Klassifizierung von Lösungsansätzen für dynamische Losgrößenprobleme5

Abgesehen von der Theorie, sind für den Einsatz in der Praxis jene Modelle und Verfahren der Losgrößenplanung bedeutend, die dynamische Bedarfsverläufe, mehrstufige Produktionsprozesse und begrenzte Produktionskapazitäten aufweisen. Entsprechend der fortschrittlich entwickelten Technologie werden heutzutage zunehmend Verfahren auf Basis der mathematischen Programmierung eingesetzt. Dies hat zum Vorteil, dass Modelformulierungen mit einer hohen Flexibilität verbunden sind und zuverlässige Lösungen liefern5.

3.2.1 Variable Neighborhood Search

Variable Neighborhood Search, ein Rahmenwerk zur Bildung von Heuristiken, wurde erstmals von N. Mladenovic und P. Hansen im Jahre 1997 initiiert. VNS ist somit eine auf lokaler Suche basierende Metaheuristik und dient zur Lösung von kombinatorischen Optimierungsproblemen. Dabei stehen, wie in Abbildung 5 abgebildet, mehrere Varianten mit unterschiedlichen Erweiterungen zur Lösungsfindung zur Verfügung14. Aufgrund der unterschiedlichen Varianten des VNS wird anschließend das basic variable neighborhood search (BVNS) genauer erklärt. Worauf auch alle anderen Erweiterungen basieren.

Ein wesentlicher Grundbestandteil für das Lösen des VNS Basisschema sind die Nachbarschaften. Diese müssen zu Beginn für die Suche definiert werden (Nk, k=1,͙ kmax). Danach wird im ersten Schritt eine Startlösung x0 mittels lokaler Suche und eine Abbruchsbedingung festgelegt6. Eine Abbruchsbedingung kann auf Grund der Erreichung der maximalen Bearbeitungszeit, der maximalen Anzahl von Iterationen oder der maximalen Anzahl von Iterationen zwischen zwei Verbesserungen bestimmt werden13.

Im zweiten Schritt muss aus der oben erstellen Nachbarschaft eine neue zufällige Lösung gefunden werden. Dieser Schritt wird als shaking bezeichnet. Anschließend wird versucht, diese Lösung mittels lokaler Suche zu einem lokalen Optimum zu führen13. Dabei liegt im Vordergrund, mehrere Nachbarschaften bei der Optimierung zu durchsuchen. Wird das Minimum einer Nachbarschaft gefunden, sprich die aktuelle Lösung ist besser als die vorherige Lösung, wird von dort aus mit der kleinsten Nachbarschaft weitergesucht. Falls dies nicht der Fall ist, wird die nächstgrößere Nachbarschaft verwendet. Dieser Vorgang wird so lange fortgesetzt , bis keine bessere Lösung in den definierten Nachbarschaften gefunden werden kann. Das heißt, eine optimale Lösung ist gefunden6.

In nachfolgender Abbildung werden die einzelnen Schritte des basic variable neighborhood search ausführlich erklärt.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 6: Schritte des VNS Basisschemas (Quelle: Xiao et al., 2010)

Das Grundmotiv des variable neighborhood search ist es, mehrere Nachbarschaften bei der Optimierung einzusetzen. Dabei wurden die folgenden drei Beobachtungen über Nachbarschaften erhoben:

1. „ein lokales Minimum einer Nachbarschaft ist nicht sogleich ein lokales Minimum einer anderen Nachbarschaft“
2. „ein globales Minimum ist ein lokales Minimum für alle möglichen Nachbarschaften“
3. sofern ein lokales Minimum gefunden wurde, liegt es einer oder mehreren Nachbarschaften nahe

Die dritte Beobachtung, welche sogar empirisch belegt wurde besagt, dass lokale Optima Teile der Optimallösung enthalten. Die Schwierigkeit liegt somit darin, jene Teile der Lösung herauszufinden, die auch in der Optimallösung vorkommen14.

Darüber hinaus, wie bereits oben erwähnt, stehen mehrere Varianten mit unterschiedlichen Erweiterungen zur Lösungsfindung zur Verfügung. Diese sind variable neighborhood descent (VND), eine deterministische Form des VNS, variable depth search (VDS), reduced variable neighborhood search (RVNS), variable neighborhood decomposition (VNDS) und skewed variable neighborhood search (SVNS). Die Anwendung dieser Varianten wird durch die Veränderung des VNS Basisschemas ermöglicht. Zudem müssen zwei Aspekte bei dieser Modifikation berücksichtigt werden. Der erste Aspekt betrifft die Nachbarschaftsstruktur, die je nach Problem verändert werden soll und der zweite Aspekt bezieht sich auf die Nachbarschaftssuchstrategie, welche bessere Ergebnisse in der Umgebung finden soll6.

3.2.2 Setup shifting rule

Abgesehen von den oben genannten Varianten, welche die Sucheffizienz versuchen zu verbessern, besteht daneben die Möglichkeit, der Anwendung einer setup shifting rule. Dabei spielt im konkreten Falle, bei der mehrstufigen Mehrproduktproduktion, die gegenseitige Produktabhängigkeit eine wichtige Rolle. Diese Abhängigkeit bezieht sich auf das Vorgänger- und Nachfolgerprodukt, welche beim Rüstvorgang der Maschinen berücksichtigt werden müssen. Daher, bevor ein Produkt im Produktionsprozess gerüstet wird, werden dessen Vorgänger kontrolliert.6.

Der setup shifting Prozess erfolgt im Allgemeinen bei Produktstrukturen in Abhängigkeit zu den einzelnen Produkten und Produktkomponenten wie folgt. „Sofern das Rüsten des Produktes 1 in Periode t aufgehoben wurde, das Vorgängerprodukt bereits gerüstet wurde, dieses jedoch keine Nachfrage in Periode t-li aufweisen kann, dann wird der Rüstvorgang für das ursprüngliche Produkt in die erste darauffolgende Periode mit positiver Nachfrage versetzt“6. Sofern in weiterer Folge eine Periode keine Nachfrage aufweisen kann, wird der komplette Rüstvorgang storniert. Dieser Prozess wird in folgender eigenerstellter Abbildung erläutert.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 7: setup shifting process for items’ interdependencies

Ebenfalls kann die setup shifting rule bei einer mehrstufigen Mehrproduktproduktion angewendet werden. Diese Vorgehensweise wird in nachstehender Abbildung dargestellt und veranschaulicht den Produktionsprozess von drei Produkten auf mehreren Produktionsstufen. Der Produktionsverlauf beginnt bei Produkt 3 und endet bei Produkt 1, welches sogleich das Produktionsende und das Endprodukt darstellt. „Folglich ist Artikel 2 der Vorgänger von Artikel 1 und Artikel 3 der Vorgänger von Artikel 2“. [6-

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 8: Vorgehensweise beim Rüstem mittels setup shifting rule

Angenommen, ein Rüstvorgang wird für ein Produkt (3-2-1) aus einer Produktionsstufe in einer bestimmten Periode storniert. Dieser Maßnahme entsprechend, können negative Folgen für das produzierende Unternehmen auftreten. Weiteres besteht die Möglichkeit, dass das Nachfolgeprodukt von dieser Handlung betroffen ist, da Nachfrage für das Produkt besteht, jedoch zuvor nicht gerüstet wurde und dementsprechend auch nichts hergestellt werden kann. Dadurch können sich die totalen Rüst- aber auch die Lagerhaltungskosten erhöhen. Aus diesem Grunde wurde, wie oben bereits erklärt, die setup shifting rule entwickelt und zum Einsatz empfohlen um den Folgen zu entweichen.

3.2.3 weitere Lösungsmethoden

Darüber hinaus bestehen noch spezifischere Varianten des VNS Algorithmus. Demzufolge werden in der Literatur die move at first improvement (MAFI) und die move at best improvement (MABI) Methode angeführt6. Die MAFI Methode verfolgt das Ziel, nach einer zulässigen Lösung sofort nach einer besseren Lösung zu suchen. Dagegen wird bei der MABI Methode eine zulässige Lösung nur dann ersetzt, wenn nach lokaler Suche eine bessere Lösung gefunden wurde. Letztlich liefert die MAFI Vorgehensweise bessere Lösungen als die MABI Vorgehensweise, da effizienter nach Lösungen gesucht wird.

4 Zusammenfassung

Das Ziel der Seminararbeit bestand darin das unkapazitierte mehrstufige Losgrößenproblemen (MLLP) zu beschreiben. Aus diesem Grund wurde zu Beginn der Arbeit ein allgemeiner Überlick zu den Losgrößenproblemen dargestellt, um zu erkennen in welcher Kategorie sich das zu beschreibende Losgrößenproblem befindet. Um auf das mehrstufige unkapazietierte Problem zu kommen, wurden kurz die wichtigsten Parameter des SLULSP beschrieben.

Im nächsten Kapitel wurde das mathematische Modell angeführt, welches für die Eingabe im Xpress relevant ist. Die Auswertung der Testinstanzen hat uns gezeigt, dass die Testinstanz 1 und die Testinstanz 6 die minimalsten Kosten aufweisen, und somit auch die optimalste Lösung zeigen. Mit Abstand die höchsten Kosten, wies die Testinstanz 8 auf, was vor allem auf die hohen Rüstkosten zurückzuführen ist. In dieser Instanz wurde jeweils in den Perioden 1 und 3 gerüstet, weiteres gab es hier mit Ausnahme vom Produkt 6, bei jedem andern Produkt einen Lagerendbestand in zumindest einer von den vier Perioden.

Der letzte Teil der Arbeit beschäftigte sich mit Lösungsmethoden zum MLLP. Dabei wurde das Hauptaugenmerk auf das Paper von Xiao, Y., Kaku, I., Zhao, Q., Zhang, R „ variable neighborhood search based approach for uncapacitated multilevel lot-sizing problems“ gesetzt. Bei den zwei angeführten Lösungsmethoden handelte es sich um das variable Neighborhood Search und die Setup shiftig rule. Das VNS ist eine auf lokaler Suche basierende Metaheuristik, die zur Lösung von kombinatorischen Optimierungsproblemen dient.

Um das unkapazitierte mehrstufige Problem zu lösen wurden noch weiter Lösungsvorschläge, wie das Verfahren von Heinrich und NIPPA Verfahren, kurz vorgestellt. Aufgabe dieser Seminararbeit war es, dem Leser im Bereich des Produktions- und Logistikmanagements ein praxisrelevantes Beispiel mit Unterstützung von theoretischem Input darzustellen

Literaturverzeichnis

[1] Han, Y., Tang, J., Kaku, I., Mua, L. (2009): Solving uncapacitated multilevel lot-sizing problems using a particle swarm optimization with flexible inertial weight; Computers and Mathematics with Applications 57, p. 1748-1755

[2] Hartl, R., (2012): Variable Neighborhood Search; Enzyklopädie der Wirtschaftsinformatik Online-Lexikon, Oldenbourg Wissenschaftsverlag Kurbel, K., Becker, J., Gronau, N., Sinz. E., Suhl, L. (Hrsg.) (2012): Homepage: http://www.enzyklopaedie-der-wirtschaftsinformatik.de/wi-enzyklopaedie, 20.11.2013

[3] Jacobs, F. R., Khumawala B. M. (1982): Mulit-level lot sizing in material requirements planning: an empirical investigation; Comput. & Ops Res. Vol. 9 (2), 139- 144

[4] Loparic, M., Pochet, Y., Wolsey, L. A. (2000): The uncapacitated lot-sizing problem with sales andnsafety stocks, Mathematical Programming, Vol. 89 (3), p. 487-504

[5] Sahling, F. (2009): Mehrstufige Losgrößenplanung bei Kapazitätsrestriktionen, Produktion und Logistik, 1. Auflage, Wiesbaden: Gabler, GWV Fachverlage GmbH

[6] Xiao, Y., Kaku, I., Zhao, Q., Zhang, R. (2010): A variable neighborhood search based approach for uncapacitated mulilevel lot-sizing problems; Computers & Industrial Engineering, 60 (2011), 218-227

[7] Schulte, G. (2009): Unternehmensübergreifende Produktionsplanung, Koordinations in Unternehmensnetzwerken mit Hilfe variabler Optimierungszentren, Dissertation Dresden: Technische Universität Dresden

[8] Tempelmeir, H. (2008): Material-Logistik, Modelle und Algorithmen für die Produktionsplanung und -steuerung in Advanced Planning-Systemen, 7. Auflage, Köln: Springer Verlag

[9] Weber, J (2012): Stichwort Rüstkosten, Gabler Wirtschaftslexikon - Das Wissen der Experten, Wiesbaden: Springer Gabler Verlag URL: http://wirtschaftslexikon.gabler.de/Archiv/13489/ruestkosten-v4.html (dl 30. November 2012)

[10] Weber, J (2012): Stichwort Lagerhaltungskosten, Gabler Wirtschaftslexikon - Das Wissen der Experten, Wiesbaden: Springer Gabler Verlag URL: http://wirtschaftslexikon.gabler.de/Archiv/13489/ruestkosten-v4.html (dl 30. November 2012)

[11] URL: http://www.fico.com/en/FIResourcesLibrary/FICO_Xpress_Optimization_Suite_2574 PS.pdf#page=3&zoom=auto,0,366 (dl 01.12.2013)

[12] URL: http://www.enzyklopaedie-der-wirtschaftsinformatik.de/wi-enzyklopaedie (dl 19.12.2013)

[13] Hansen, P., Mladenovic, N., (2001): Variable neighborhood search: Principles and applications, European Journal of Operational Research, Vol 130, p.449-467

[14] Hansen, P., Mladenovic, N., (2005): Variable Neighborhood Search; in: Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques, Chapter 8, (Hrsg.): Springer Science+Business Media, LLC, p. 211-238

Ende der Leseprobe aus 30 Seiten

Details

Titel
Losgrößenplanung. Implementierung des MLULSP Modells mithilfe von Xpress
Hochschule
Johannes Kepler Universität Linz
Note
2
Autor
Jahr
2013
Seiten
30
Katalognummer
V314506
ISBN (eBook)
9783668187412
ISBN (Buch)
9783668187429
Dateigröße
1258 KB
Sprache
Deutsch
Schlagworte
losgrößenplanung, implementierung, mlulsp, modells, xpress
Arbeit zitieren
Sandra Tomasevic (Autor:in), 2013, Losgrößenplanung. Implementierung des MLULSP Modells mithilfe von Xpress, München, GRIN Verlag, https://www.grin.com/document/314506

Kommentare

  • Noch keine Kommentare.
Blick ins Buch
Titel: Losgrößenplanung. Implementierung des MLULSP Modells mithilfe von Xpress



Ihre Arbeit hochladen

Ihre Hausarbeit / Abschlussarbeit:

- Publikation als eBook und Buch
- Hohes Honorar auf die Verkäufe
- Für Sie komplett kostenlos – mit ISBN
- Es dauert nur 5 Minuten
- Jede Arbeit findet Leser

Kostenlos Autor werden