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
- Einleitung
- Grundlagen und Voraussetzungen
- Problemstellung
- Problemanalyse
- Voraussetzungen
- Typologische Einordnung des Problems
- Verschnittbetrachtung
- Zielstellung
- Beispiel für das MSSCSP+R
- Complete-Cut Ansatz
- Schnittmuster- und Kostenbetrachtung
- Complete-Cut Modellierung für MSSCSP+R
- Beispiel für die Complete-Cut Modellierung
- One-Cut Ansatz
- Voraussetzungen und One-Cut Schnittmuster
- One-Cut Modellierung (nach Dyckhoff)
- One-Cut Modellierung für MSSCSP+R (nach Stadtler)
- Reduktionsregeln für den One-Cut Ansatz
- Auftragsregel (nach Dyckhoff)
- Längenregel (nach Stadtler)
- Schnittregel (nach Stadtler)
- Beispiel für die One-Cut Modellierung
- Bin-Packing Ansatz
- Bin-Packing Terminologie
- Bin-Packing Modellierung für MSSCSP+R
- Beispiel für die Bin-Packing Modellierung
- Graphentheoretischer Ansatz
- Arc-Flow Modellierung für mehrere Inputlängen (nach Valério de Carvalho)
- Bildung des Graphen
- Kriterien zur Reduzierung der Bogenmenge
- Arc-Flow Modellierung für MSSCSP+R
- Notwendigkeit der alternativen Modellierung
- Bildung des Graphen und Reduzierung der Bogenmenge
- Betrachtung der Verschnittbögen
- Kostenbetrachtung und IP-Formulierung
- Beispiel für die Arc-Flow Modellierung
- Arc-Flow Modellierung für mehrere Inputlängen (nach Valério de Carvalho)
- Vergleich der Modellgrößen
- Lösungsansätze für das MSSCSP+R
- Exakte Verfahren
- Lösungsverfahren für das relaxierte MSSCSP+R
- Heuristische Verfahren für das ganzzahlige MSSCSP+R
- Item-orientierte Lösungsansätze
- Konstruktionsheuristiken
- Verfahren von Gontijo Rocha et al.
- CUT als sequenzielles heuristisches Verfahren
- C-CUT als Kombination aus Branch-and-Bound und SHP
- IP-orientierte Lösungsansätze
- Hybridalgorithmus
- Residualheuristiken
- Item-orientierte Lösungsansätze
Zielsetzung und Themenschwerpunkte
Die vorliegende Diplomarbeit befasst sich mit der Modellierung des Cutting Stock Problems unter Berücksichtigung von Reststücken. Ziel ist es, verschiedene Modellierungsansätze für dieses Problem zu analysieren und zu vergleichen.
- Analyse verschiedener Modellierungsansätze für das Cutting Stock Problem
- Betrachtung der Reststücke als zusätzliche Ressource
- Entwicklung und Vergleich von Lösungsansätzen für das Problem
- Bewertung der Effizienz der verschiedenen Modellierungsansätze
- Identifizierung von Optimierungspotenzialen bei der Berücksichtigung von Reststücken
Zusammenfassung der Kapitel
- Kapitel 1: Einleitung
- Kapitel 2: Grundlagen und Voraussetzungen - Definition des Problems, Analyse der Voraussetzungen, Einordnung in die Literatur und Formulierung der Zielstellung.
- Kapitel 3: Complete-Cut Ansatz - Beschreibung des Ansatzes, Modellierung und Beispiel.
- Kapitel 4: One-Cut Ansatz - Vorstellung der Voraussetzungen, Modellierung nach Dyckhoff und Stadtler, Reduktionsregeln und Beispiel.
- Kapitel 5: Bin-Packing Ansatz - Erklärung der Terminologie, Modellierung und Beispiel.
- Kapitel 6: Graphentheoretischer Ansatz - Arc-Flow Modellierung nach Valério de Carvalho, Bildung des Graphen und Reduzierung der Bogenmenge, Anpassung für das MSSCSP+R, Kostenbetrachtung und IP-Formulierung sowie Beispiel.
- Kapitel 7: Vergleich der Modellgrößen - Analyse der Größe und Komplexität der verschiedenen Ansätze.
- Kapitel 8: Lösungsansätze für das MSSCSP+R - Überblick über exakte und heuristische Verfahren.
Schlüsselwörter
Cutting Stock Problem, Reststücke, Modellierungsansätze, Complete-Cut, One-Cut, Bin-Packing, Graphentheoretischer Ansatz, Arc-Flow, Lösungsansätze, Heuristiken, Optimierung.
- Citation du texte
- Matthias Lange (Auteur), 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
