Zuschnittprobleme beschreiben die Zerteilung gewisser Standardlängen in eine bestimmte Menge von nachgefragten Rollen verschiedener Längen. Hierbei sollen möglichst wenige der Standardrollen benutzt werden, um die Materialkosten zu minimieren.
Dieses Problem tritt in der Praxis häufig auf – z. B. beim Zuschnitt von Metall, Holz oder Papier – und ist damit relevant für viele Industriebereiche. Falls der Produktionsablauf mit der Planung des Zuschnitts zu komplex wird, stößt der entsprechende Disponent an seine Grenzen und benötigt die Hilfe von mathematischen Optimierungsmodellen .
Es kann jedoch auch bei kleineren Probleminstanzen sinnvoll sein, auf diese zurückzugreifen. Die Darstellung der Zuschnittprobleme kann zum einen durch Modellierungen erfolgen, die die verschiedenen Möglichkeiten der Zerteilung einer Standardlänge betrachten, zum anderen auch durch die Untersuchung verwandter Probleme.
Eine entscheidende Bedeutung bei Zuschnittproblemen hat der ungenutzte Teil von zerschnittenen Standardlängen – der Verschnitt. Bei vielen Untersuchungen wird eine Minimierung des Verschnitts angestrebt, da dieser als nicht verwertbar angesehen wird und den regulierbaren Teil der Materialkosten darstellt. Doch nicht immer ist diese Zielstellung realitätsnah. Wenn ein Lager für die Standardlängen zur Verfügung steht, liegt die nähere Untersuchung des Verschnitts nahe, da auch dieser möglicherweise eingelagert und in späteren Zuschnittprozessen wieder eingesetzt werden kann. Diese speziellen Verschnittlängen werden als Reststücke bezeichnet und die Betrachtung dieser bildet die Grundlage der vorliegenden Arbeit. Die Reststücke erhöhen die Komplexität der Probleme an zwei Stellen: Zum einen sind diese neben den Standardlängen zu Beginn eines Prozesses verfügbar und können gegebenenfalls weiter zerschnitten werden, zum anderen muss der beim Zuschnitt entstehende Verschnitt differenziert werden, da dieser nicht mehr automatisch Abfall darstellt. Somit kommt es sowohl auf Input- als auch auf Outputseite des Zuschnittprozesses zu Modifizierungen. Für die Darstellung von Zuschnittproblemen sind unterschiedliche Modellierungsansätze entwickelt worden, die für die Berücksichtigung von Reststücken in der vorliegenden Arbeit untersucht und teilweise geeignet angepasst werden müssen.
Inhaltsverzeichnis
1 Einleitung
2 Grundlagen und Voraussetzungen
2.1 Problemstellung
2.2 Problemanalyse
2.2.1 Voraussetzungen
2.2.2 Typologische Einordnung des Problems
2.2.3 Verschnittbetrachtung
2.2.4 Zielstellung
2.3 Beispiel für das MSSCSP+R
3 Complete-Cut Ansatz
3.1 Schnittmuster- und Kostenbetrachtung
3.2 Complete-Cut Modellierung für MSSCSP+R
3.3 Beispiel für die Complete-Cut Modellierung
4 One-Cut Ansatz
4.1 Voraussetzungen und One-Cut Schnittmuster
4.2 One-Cut Modellierung (nach Dyckhoff)
4.3 One-Cut Modellierung für MSSCSP+R (nach Stadtler)
4.4 Reduktionsregeln für den One-Cut Ansatz
4.4.1 Auftragsregel (nach Dyckhoff)
4.4.2 Längenregel (nach Stadtler)
4.4.3 Schnittregel (nach Stadtler)
4.5 Beispiel für die One-Cut Modellierung
5 Bin-Packing Ansatz
5.1 Bin-Packing Terminologie
5.2 Bin-Packing Modellierung für MSSCSP+R
5.3 Beispiel für die Bin-Packing Modellierung
6 Graphentheoretischer Ansatz
6.1 Arc-Flow Modellierung für mehrere Inputlängen (nach Valério de Carvalho)
6.1.1 Bildung des Graphen
6.1.2 Kriterien zur Reduzierung der Bogenmenge
6.2 Arc-Flow Modellierung für MSSCSP+R
6.2.1 Notwendigkeit der alternativen Modellierung
6.2.2 Bildung des Graphen und Reduzierung der Bogenmenge
6.2.3 Betrachtung der Verschnittbögen
6.2.4 Kostenbetrachtung und IP-Formulierung
6.3 Beispiel für die Arc-Flow Modellierung
7 Vergleich der Modellgrößen
8 Lösungsansätze für das MSSCSP+R
8.1 Exakte Verfahren
8.2 Lösungsverfahren für das relaxierte MSSCSP+R
8.3 Heuristische Verfahren für das ganzzahlige MSSCSP+R
8.3.1 Item-orientierte Lösungsansätze
8.3.1.1 Konstruktionsheuristiken
8.3.1.2 Verfahren von Gontijo Rocha et al.
8.3.1.3 CUT als sequenzielles heuristisches Verfahren
8.3.1.4 C-CUT als Kombination aus Branch-and-Bound und SHP
8.3.2 IP-orientierte Lösungsansätze
8.3.2.1 Hybridalgorithmus
8.3.2.2 Residualheuristiken
9 Zusammenfassung und Ausblick
Zielsetzung & Themen
Diese Diplomarbeit befasst sich mit der mathematischen Modellierung und Optimierung von eindimensionalen Zuschnittproblemen, bei denen neben Standardlängen auch Reststücke aus vorangegangenen Prozessen als Input dienen. Das zentrale Ziel ist die Minimierung der gesamten Verschnittkosten durch eine differenzierte Behandlung von Abfall und wiederverwendbarem Verschnitt.
- Analyse und Modifikation verschiedener Modellierungsansätze (Complete-Cut, One-Cut, Bin-Packing, Graphentheoretisch)
- Differenzierung zwischen Abfall und Reststücken zur Kostenoptimierung
- Vergleich der Modellgrößen und Lösungsansätze für das Multiple Stock-Size Cutting Stock Problem mit Reststückbildung (MSSCSP+R)
- Untersuchung exakter und heuristischer Lösungsverfahren unter Berücksichtigung der neuen Kostenstruktur
Auszug aus dem Buch
Die Berücksichtigung von Reststücken in unterschiedlichen Modellierungsansätzen für das Cutting Stock Problem
Zuschnittprobleme beschreiben die Zerteilung gewisser Standardlängen in eine bestimmte Menge von nachgefragten Rollen verschiedener Längen. Hierbei sollen möglichst wenige der Standardrollen benutzt werden, um die Materialkosten zu minimieren. Dieses Problem tritt in der Praxis häufig auf – z. B. beim Zuschnitt von Metall, Holz oder Papier – und ist damit relevant für viele Industriebereiche. Falls der Produktionsablauf mit der Planung des Zuschnitts zu komplex wird, stößt der entsprechende Disponent an seine Grenzen und benötigt die Hilfe von mathematischen Optimierungsmodellen.
Eine entscheidende Bedeutung bei Zuschnittproblemen hat der ungenutzte Teil von zerschnittenen Standardlängen – der Verschnitt. Bei vielen Untersuchungen wird eine Minimierung des Verschnitts angestrebt, da dieser als nicht verwertbar angesehen wird und den regulierbaren Teil der Materialkosten darstellt. Doch nicht immer ist diese Zielstellung realitätsnah. Wenn ein Lager für die Standardlängen zur Verfügung steht, liegt die nähere Untersuchung des Verschnitts nahe, da auch dieser möglicherweise eingelagert und in späteren Zuschnittprozessen wieder eingesetzt werden kann. Diese speziellen Verschnittlängen werden als Reststücke bezeichnet und die Betrachtung dieser bildet die Grundlage der vorliegenden Arbeit.
Zusammenfassung der Kapitel
1 Einleitung: Einführung in das Zuschnittproblem und die spezielle Herausforderung durch Reststückbildung sowie Überblick über die Arbeit.
2 Grundlagen und Voraussetzungen: Definition des MSSCSP+R, Analyse der Problemvoraussetzungen und Festlegung der Kostenparameter.
3 Complete-Cut Ansatz: Erläuterung der klassischen schnittmusterorientierten Modellierung und deren Anpassung für das MSSCSP+R.
4 One-Cut Ansatz: Vorstellung des sukzessiven Zuschnittmodells nach Dyckhoff und dessen Weiterentwicklung durch Stadtler.
5 Bin-Packing Ansatz: Herleitung der Äquivalenz zum Bin-Packing Problem und Formulierung für das MSSCSP+R.
6 Graphentheoretischer Ansatz: Untersuchung der Arc-Flow Formulierung nach Valério de Carvalho und ihre notwendige Modifikation für das betrachtete Problem.
7 Vergleich der Modellgrößen: Gegenüberstellung der Anzahl an Variablen und Nebenbedingungen für die verschiedenen Modellansätze.
8 Lösungsansätze für das MSSCSP+R: Detaillierte Betrachtung exakter und heuristischer Methoden zur Lösung des ganzzahligen sowie relaxierten Problems.
9 Zusammenfassung und Ausblick: Resümee der Ergebnisse und Diskussion möglicher zukünftiger Forschungsrichtungen.
Schlüsselwörter
MSSCSP+R, Zuschnittproblem, Reststückbildung, Verschnittkosten, Cutting Stock Problem, Optimierungsmodell, One-Cut Ansatz, Complete-Cut Ansatz, Bin-Packing, Arc-Flow, Spaltengenerierung, Modellgröße, Heuristik, Materialkosten, lineare Optimierung.
Häufig gestellte Fragen
Worum geht es in der Arbeit grundsätzlich?
Die Arbeit beschäftigt sich mit der mathematischen Modellierung des eindimensionalen Zuschnittproblems, erweitert um die Möglichkeit, Verschnitt als wiederverwendbare Reststücke zu lagern.
Was sind die zentralen Themenfelder?
Zentrale Themen sind die mathematische Modellierung, die Differenzierung von Verschnitt in Abfall und Reststücke sowie der Vergleich verschiedener Ansätze wie Complete-Cut, One-Cut, Bin-Packing und Graphentheorie.
Was ist das primäre Ziel oder die Forschungsfrage?
Das primäre Ziel ist es, das klassische Zuschnittproblem so zu erweitern und zu modellieren, dass Reststückbildung und deren Kosten bei der Planung explizit berücksichtigt werden, um die Materialkosten zu minimieren.
Welche wissenschaftliche Methode wird verwendet?
Es werden verschiedene Ansätze der mathematischen Optimierung (Integer Programming) und graphbasierte Formulierungen analysiert, verglichen und für das Problem modifiziert.
Was wird im Hauptteil behandelt?
Der Hauptteil behandelt die detaillierte Darstellung der vier Modellierungsansätze, deren Reduktionsregeln, die Analyse ihrer Modellgröße sowie verschiedene exakte und heuristische Lösungsverfahren.
Welche Schlüsselwörter charakterisieren die Arbeit?
Die Arbeit lässt sich primär durch Begriffe wie MSSCSP+R, Reststückbildung, Verschnittkosten, Cutting Stock Problem, One-Cut Modell und mathematische Optimierung charakterisieren.
Warum wird beim MSSCSP+R der Arc-Flow-Ansatz als besonders komplex angesehen?
Weil bei diesem Ansatz genutzte Verschnittbögen im Graphen nicht eindeutig einer spezifischen Inputlänge zugeordnet werden können, was eine Anpassung der Modellierung erforderlich macht.
Inwiefern unterscheiden sich die Heuristiken FFDL und GreedyL von ihren Grundformen?
Sie werden speziell modifiziert, um Reststücke zu berücksichtigen, indem sie den Verschnitt analysieren und nur Schnittmuster akzeptieren, deren Verschnitt entweder lang genug für eine Lagerung oder vernachlässigbar kurz ist.
- Quote paper
- Matthias Lange (Author), 2008, Die Berücksichtigung von Reststücken in unterschiedlichen Modellierungsansätzen für das Cutting Stock Problem, Munich, GRIN Verlag, https://www.grin.com/document/92090
