Die Berücksichtigung von Reststücken in unterschiedlichen Modellierungsansätzen für das Cutting Stock Problem

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

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.