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.
Otto-von-Guericke-Universität Magdeburg
- Fakultät für Wirtschaftswissenschaft -
Lehrstuhl für Betriebswirtschaftslehre,
insbes. Management Science
Diplomarbeit
Die Berücksichtigung von Reststücken in unterschiedlichen
Modellierungsansätzen für das Cutting Stock Problem
von:
Matthias Lange
Abgabe: 29.02.2008
- 1 -
I Inhaltsverzeichnis
I
Inhaltsverzeichnis 1
II Abbildungsverzeichnis
3
4
8
... 10
... 12
... 13
... 17
g... 18
lierung ... 24
uster... 27
R (nach Stadtler) ... 32
... 36
... 37
III Tabellenverzeichnis 3
IV Symbolverzeichnis
V
Abkürzungsverzeichnis 7
1
Einleitung
2
Grundlagen und Voraussetzungen
10
2.1 Problemstellung ...
2.2 Problemanalyse... 12
2.2.1 Voraussetzungen ...
2.2.2 Typologische Einordnung des Problems ... 13
2.2.3 Verschnittbetrachtung ...
2.2.4 Zielstellung... 16
2.3 Beispiel für das MSSCSP+R ...
3
Complete-Cut Ansatz
18
3.1 Schnittmuster- und Kostenbetrachtun
3.2 Complete-Cut Modellierung für MSSCSP+R ... 22
3.3 Beispiel für die Complete-Cut Model
4
One-Cut Ansatz
27
4.1 Voraussetzungen und One-Cut Schnittm
4.2 One-Cut Modellierung (nach Dyckhoff) ... 29
4.3 One-Cut Modellierung für MSSCSP+
4.4 Reduktionsregeln für den One-Cut Ansatz... 35
4.4.1 Auftragsregel (nach Dyckhoff) ...
4.4.2 Längenregel (nach Stadtler) ... 36
4.4.3 Schnittregel (nach Stadtler) ...
4.5 Beispiel für die One-Cut Modellierung ... 38
- 2 -
5
Bin-Packing Ansatz
40
SP+R ... 42
47
... 47
+R ... 51
ung der Bogenmenge ... 52
erung... 57
61
... 63
ahlige MSSCSP+R ... 65
... 66
ahren ... 69
... 72
... 72
5.1 Bin-Packing Terminologie... 40
5.2 Bin-Packing Modellierung für MSSC
5.3 Beispiel für die Bin-Packing Modellierung ... 44
6
Graphentheoretischer Ansatz
6.1 Arc-Flow Modellierung für mehrere Inputlängen (nach Valério de Carvalho)... 47
6.1.1 Bildung des Graphen ...
6.1.2 Kriterien zur Reduzierung der Bogenmenge... 49
6.2 Arc-Flow Modellierung für MSSCSP
6.2.1 Notwendigkeit der alternativen Modellierung ... 51
6.2.2 Bildung des Graphen und Reduzier
6.2.3 Betrachtung der Verschnittbögen... 54
6.2.4 Kostenbetrachtung und IP-Formuli
6.3 Beispiel für die Arc-Flow Modellierung ... 59
7
Vergleich der Modellgrößen
8
Lösungsansätze für das MSSCSP+R
63
8.1 Exakte Verfahren ...
8.2 Lösungsverfahren für das relaxierte MSSCSP+R ... 63
8.3 Heuristische Verfahren für das ganzz
8.3.1 Item-orientierte Lösungsansätze... 66
8.3.1.1 Konstruktionsheuristiken ...
8.3.1.2 Verfahren von Gontijo Rocha et al. ... 68
8.3.1.3 CUT als sequenzielles heuristisches Verf
8.3.1.4 C-CUT als Kombination aus Branch-and-Bound und SHP ... 71
8.3.2 IP-orientierte Lösungsansätze ...
8.3.2.1 Hybridalgorithmus ... 72
8.3.2.2 Residualheuristiken ...
9
Zusammenfassung und Ausblick
75
- 3 -
Literaturverzeichnis 77
rvalho (Beispiel)...48
alério de Carvalho (Beispiel) ...51
mit Quelle und Senke (Beispiel) ...54
L
(2)
(Beispiel) ...19
piel)...28
Reduktion (Beispiel)...38
stellung (Bin-Packing Ansatz)...46
...61
II Abbildungsverzeichnis
Abbildung 1 Modifiziertes Zuschnittproblem ...11
Abbildung 2 Graph nach Valério de Ca
Abbildung 3 Zyklen im Graph nach Valério de Carvalho (Beispiel) ...49
Abbildung 4 Reduzierter Graph nach V
Abbildung 5 Verschnitt im Graph nach Valério de Carvalho (Beispiel)...52
Abbildung 6 Reduzierter Gesamtgraph
Abbildung 7 Verschnittbetrachtung am Teilgraphen (Beispiel) ...57
III Tabellenverzeichnis
Tabelle 1 Schnittmuster für Inputlänge L
(1)
(Beispiel) ...19
Tabelle 2 Schnittmuster für Inputlänge
Tabelle 3 Beispielinstanz in Tableaudarstellung (Complete-Cut Ansatz) ...26
Tabelle 4 One-Cut Schnittmuster (Beis
Tabelle 5 Anwendung der Auftragsregel auf One-Cuts (Beispiel)...36
Tabelle 6 One-Cut Schnittmuster nach
Tabelle 7 Beispielinstanz in Tableaudarstellung (One-Cut Ansatz) ...39
Tabelle 8 Beispielinstanz in Tableaudar
Tabelle 9 Beispielinstanz in Tableaudarstellung (Arc-Flow Ansatz) ...60
Tabelle 10 Anzahl der Variablen ...
Tabelle 11 Anzahl der Nebenbedingungen...62
- 4 -
IV Symbolverzeichnis
A
Matrix
1
aller Schnittmuster
Matrix der Schnittmuster für Inputlänge L
(k)
(k
A
(
.
k
)
)
j
a
Schnittmuster j für Inputlänge L
(k)
mit
( )
( )
( )
.
1
,...,
T
k
k
k
j
j
mj
a
a
a
( )
.
k
Anzahl von Nachfragelänge in Schnittmuster
(k
ij
a
)
i
l
j
a
für Inputlänge L
(k)
B
Anzahl der Items
Bedarfsvektor
b
i
b
C
ab
C
h
C
abf
c
h
c
konst
c
(
C
(k
C
(k
2
Bedarf an Nachfragelänge
Gesamtverschnittkosten
Gesamtabfallkosten
Gesamthandlingkosten der Reststücke
Abfallkosten pro Längeneinheit
Handlingkosten pro Längeneinheit des Reststückes
Konstante Kosten pro Reststück
Kosten für Bin
j
Vektor der Schnittmusterkosten für Inputlänge
L
(k)
i
l
f
and
and
)
j
)
)
j
C
d
E
N
E
T
E
Kosten von Schnittmuster
j für Inputlänge L
(k)
Vektor von Simplexmultiplikatoren
Bogenmenge
Menge der Nachfragebögen
Menge der Verschnittbögen
Z
E
E
(k
E
(k
N
E
(k
T
E
Menge der Bögen zur Zurücksetzung
Reduzierte Bogenmenge
Bogenmenge für Inputlänge
L
(k)
Menge der Nachfragebögen für Inputlänge
L
(k)
Menge der Verschnittbögen für Inputlänge
L
(k)
)
)
)
1
Elemente einer Matrix werden im Folgenden mit dem zugehörigen Kleinbuchstaben sowie dem Indexpaar
aus Zeile und Spalte bezeichnet.
2
Der Begriff Vektor bezeichnet in dieser Arbeit Spaltenvektoren.
- 5 -
( )
k
E
Reduzierte Bogenmenge für Inputlänge
L
(k)
Bogenmenge des Gesamtgraphen
Reduzierte Bogenmenge des Gesamtgraphen
E
E
i
l
f
Anzahl der Nachfragelängen
l
i
, die als erster Teil eines One-Cuts entstehen
Graph
Graph für Inputlänge
L
(k)
Gesamtgraph
G
(k
G
G
)
L
Länge der Inputrollen
Länge von Inputrolle
k
Vektor der Nachfragelängen
Länge von Nachfragerolle
i
Anzahl verschiedener Nachfragelängen
Gesamtanzahl der Schnittmuster
Anzahl der Schnittmuster für Inputlänge
L
(k)
Anzahl verschiedener Inputlängen
Verbindungsmatrix
Element der Verbindungsmatrix (Zuordnung von Muster
j zu Inputrolle k)
Minimale Länge der Reststücke
Maximale Länge der Reststücke
Anzahl der Bins
Vorratsvektor
Vorrat an Inputrollen der Länge
L
(k)
(k
L
l
i
l
m
n
k
n
p
Q
kj
q
mi
r
ma
r
S
s
(k
s
(
)
n
x
)
)
j
T
t
(k
Verbleibende Kapazität von Bin
j
Verschnittlänge
)
j
t
( )
max
k
ma
u
V
(k
V
V
Länge des Verschnitts von Inputrolle
k bei Schnitt nach Muster j
Maximale Länge des Verschnitts bei Inputlänge
L
(k)
Maximale Länge für Abfall
Knotenmenge
Knotenmenge für Inputlänge
L
(k)
Knotenmenge des Gesamtgraphen
t
)
)
x
( j
W
Kapazität von Bin
j
- 6 -
i
w
Gewicht von Item
i
( )
k
x
Vektor der Musterverwendung für Inputlänge
L
(k)
( )
k
j
x
Häufigkeit der Verwendung von Schnittmuster
( )
.
k
j
a
,
d e
x
Häufigkeit der Verwendung des Bogens von
d nach e
( )
,
k
d e
x
Häufigkeit der Verwendung des Bogens von
d nach e für Inputlänge L
(k)
j
y
Binärvariable (Nutzung von Bin
j )
,
y
Häufigkeit von One-Cut
,
Anzahl der benutzten Inputlängen
L
(k)
Binärvariable (Zuordnung von Item
i zu Bin
( )
k
z
ij
z
j )
,
One-Cut mit
,
Inputlänge eines One-Cuts
Nachfragelänge eines One-Cuts
Zwischenlänge eines One-Cuts
prod
Produktive
Zwischenlänge
Künstliche
Quelle
Anzahl der aus dem Lager entnommenen Inputlängen L
(k)
( )
k
Anzahl verschiedener Nachfragelängen je Inputlänge
Anzahl des Verschnitts der Länge
t
t
( )
k
t
Anzahl des Verschnitts der Länge t bei Inputlängen L
(k)
Indikatorfunktion
Künstliche
Senke
Faktor (Handlingkosten je Längeneinheit / Abfallkosten je Längeneinheit)
Menge der Nachfragelängen, d. h.
1
,
,
m
l
l
Koeffizientenmatrix im One-Cut Modell
Menge der Permutationslängen
Menge der Inputlängen, d. h.
(1)
(
,
,
p
L
L
)
Menge aller Zwischenlängen
- 7 -
V Abkürzungsverzeichnis
CSP
Cutting Stock Problem
FFD
First Fit Decreasing
IP
Ganzzahliges Programm (Integer Program)
LP
Lineares Programm (Linear Program)
MSSCSP
Multiple Stock-Size Cutting Stock Problem
MSSCSP+R
Multiple Stock-Size Cutting Stock Problem mit Reststückbildung
RCSP
Residual Cutting Stock Problem
SHP
Sequenzielle heuristische Prozedur
SSSCSP
Single Stock-Size Cutting Stock Problem
1D Eindimensional
- 8 -
1
Einleitung
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
3
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
4
.
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.
3
Vgl. Terno / Lindemann / Scheithauer (1987), S. 14.
4
Vgl. Dyckhoff / Gehring (1982), S. 193.
- 9 -
Im zweiten Kapitel wird zur Einführung die Problemstellung dargelegt sowie das
betrachtete Problem näher analysiert. In den nächsten vier Kapiteln werden verschiedene
Modellierungsansätze für Zuschnittprobleme vorgestellt und modifiziert. Den Anfang
macht hierbei die Complete-Cut Formulierung. Die Betrachtung des One-Cut Modells
schließt sich in Kapitel 4 an. Eng verwandt mit den Zuschnittproblemen ist das
Bin-Packing Problem
5
. Diese Analogie führt zu dem im fünften Kapitel untersuchten
Modell. In Kapitel 6 wird der graphentheoretische Ansatz betrachtet und auf die Eignung
für die Differenzierung des Verschnitts hin untersucht. Die vorgestellten Modelle werden
im siebten Kapitel beispielhaft auf Grundlage der jeweiligen Modellgröße verglichen.
Anschließend werden in Kapitel 8 verschiedene Lösungsansätze vorgestellt. In Kapitel 9
wird ein Fazit gezogen, um zusammenfassend darzulegen, wie Reststücke in
Zuschnittproblemen geeignet modelliert werden können, welche Lösungsansätze sich für
dieses modifizierte Zuschnittproblem ergeben und an welchen Stellen noch
Forschungsbedarf besteht.
5
Siehe auch Gau (1997), S. 21f.
- 10 -
2
Grundlagen und Voraussetzungen
2.1
Problemstellung
Das Standardproblem eindimensionalen Zuschneidens beschreibt den Zuschnitt einer
Standardlänge
in mehrere Nachfragelängen, die in gegebenen Quantitäten hergestellt
werden müssen
L
6
. Hierbei ist die Anzahl der benutzten Standardlängen zu minimieren,
wobei deren Verfügbarkeit nicht beschränkt ist
7
. Der hier zu betrachtende Zuschnittprozess
geht über das Standardproblem eindimensionalen Zuschneidens hinaus. Es wird zwar
weiterhin nur eine Dimension betrachtet, die in dieser Arbeit ohne Beschränkung der
Allgemeinheit als Länge bezeichnet wird, allerdings kommt es sowohl auf der Input- als
auch auf der Outputseite des Zuschnittprozesses zu Modifizierungen. Als Input sind
sowohl schwach heterogene Standardlängen, die in großen Mengen auf Lager sind,
als auch Reststücke aus vorherigen Zuschnittprozessen möglich. Diese Reststücke sind
meist nur in geringen Stückzahlen vorhanden und bilden zusammen mit den
Standardlängen die sogenannten Inputlängen
, deren jeweiliger Vorrat mit
angegeben wird. Diese Inputlängen werden nun in der Längendimension zerschnitten, um
die schwach heterogenen Nachfragelängen zu erhalten, die am Ende des
Schnittprozesses in gegebenen Quantitäten
vorliegen müssen. Sowohl für die Input- als
auch für die Nachfragelängen werden nur natürliche Zahlen betrachtet, da die in der Praxis
gängigen Werte rational sind und somit durch geeignete Standardisierung für alle Längen
Ganzzahligkeit erreicht werden kann
( )
k
L
i
l
( )
k
s
i
b
8
.
Als Output erhaltene Längen, die nicht der Befriedigung der Nachfrage dienen, werden im
Folgenden als Verschnitt bezeichnet
9
. Hierbei kann es sich sowohl um Nachfragelängen,
die in größerer Stückzahl als benötigt erzeugt werden, als auch um andere Längen handeln.
Insbesondere können auch Inputlängen als Output einer größeren Inputlänge entstehen.
Der Verschnitt wird nun anders als beim Standardproblem nicht automatisch als Abfall
entsorgt, sondern kann auch als Reststück gelagert und in späteren Zuschnittprozessen
wieder als Inputmaterial genutzt werden
10
. Hierzu muss der Verschnitt eine bestimmte
6
Vgl. Gau (1997), S. 8.
7
Vgl. ebd.
8
Vgl. Dyckhoff (1981), S. 1095f.
9
Siehe auch Koch / König / Wäscher (2007), S. 3.
10
Vgl. Koch / König / Wäscher (2007), S. 3.
- 11 -
vorgegebene Länge besitzen, die die Aufbewahrung sinnvoll erscheinen lässt. Wenn der
Verschnitt hingegen zu kurz ist, wird er als Abfall betrachtet. Durch diese Differenzierung
des Verschnitts kommt es in der Praxis bei der Betrachtung mehrerer Zuschnittprozesse zu
einer geringeren Anzahl an eingesetzten Standardlängen und somit zu
Kostenersparnissen
11
.
Dieses spezielle Zuschnittproblem, das in Abbildung 1 grafisch dargestellt ist, muss näher
analysiert werden, um schließlich vier verschiedene Modellierungsansätze vorstellen zu
können: das klassische Modell mit Schnittmustern, ein alternatives Modell mit One-Cut
Schnittmustern, die Bin-Packing Formulierung sowie das graphentheoretische Konzept
von Valério de Carvalho.
L
(p-1)
Abbildung 1 Modifiziertes Zuschnittproblem
11
Siehe auch Koch / König / Wäscher (2007), S. 2.
Nachfragelängen:
(schwach heterogen)
Zuschnitt-
prozess
Länge l
1
l
2
l
3
l
m
Inputlängen: (schwach heterogene Standardlängen + stark heterogene Reststücke)
Länge L
(1)
Länge L
(2)
L
(p)
Reststücke
Abfall
Verschnitt:
- 12 -
2.2
Problemanalyse
2.2.1
Voraussetzungen
Wie schon beschrieben werden in dieser Arbeit nur eindimensionale (kurz 1D) Probleme
betrachtet. Daher wird dies im Folgenden nicht mehr erwähnt und der Vorsatz 1D
vernachlässigt. Eine wichtige Voraussetzung für den Zuschnittprozess ist das
Vorhandensein von hinreichend vielen Standardlängen im Lager, sodass mindestens eine
zulässige Lösung existiert, die als Output alle Nachfragelängen in den erforderlichen
Quantitäten zur Verfügung stellt. Des Weiteren seien die Input- und Nachfragelängen
jeweils verschieden und absteigend sortiert, d. h.
1
2
(
)
(
)
1
2
1
2
und
[2.1]
k
k
i
i
L
L
k
k
l
l
i
i
1
2
i
.
Außerdem liegt keine Nachfragelänge bereits als Input vor:
( )
1,
, 1,
,
[2.2]
k
L
l
k
p
i
m
.
Anderenfalls könnte diese spezifische Länge vor Beginn des Zuschnitts zur
Bedarfsbefriedigung verwendet und aus der Betrachtung des Zuschnittprozesses
ausgenommen werden. Weiterhin sei die Lagermöglichkeit für Reststücke hinreichend
groß, sodass es keine Beschränkung bezüglich deren Anzahl oder Länge gibt. Für die
maximal zulässige Länge von Reststücken
gilt somit
max
r
max
r
. Die minimal
erforderliche Länge, die ein Verschnitt haben muss, um als Reststück betrachtet zu werden,
sei mit
bezeichnet. Diese wird häufig so gewählt, dass sie der kleinsten
Nachfragelänge entspricht
min
r
12
, d. h.
. Dadurch wird sichergestellt, dass die
eingelagerten Reststücke auch in nachfolgenden Betrachtungen verwendet werden können,
sei es direkt zur Bedarfsbefriedigung oder auch als Input für weitere Zuschnittprozesse.
Würde hierbei ein Wert gewählt werden, der kleiner als die kleinste Nachfragelänge ist,
könnten Reststücke eingelagert werden, die in folgenden Zuschnittprozessen nutzlos
wären
min
1,
mi
i
r
,
n
i
m
l
13
. Jede Inputlänge muss auch mindestens so lang wie das kleinstmögliche Reststück
sein, da sie sonst nicht in den Vorrat aufgenommen worden wäre:
.
Am Anfang des Zuschnittprozesses werden Standardlängen und Reststücke aus vorherigen
Prozessen gleichermaßen behandelt und gemeinsam als Inputlängen betrachtet.
min
( )
1, ,
min
k
k
p
r
L
12
Siehe auch Gau (1997), S. 12.
13
Vgl. Trkman / Gradisar (2007), S. 294.
- 13 -
2.2.2
Typologische Einordnung des Problems
Die geschilderte Problemstellung gehört in der Klasse der Zuschnitt- und Packprobleme zu
den Cutting Stock Problemen. Bei einem Cutting Stock Problem muss eine schwach
heterogene Auswahl an kleinen Objekten (hier: Nachfragelängen) vollständig einer
Auswahl von großen Objekten (hier: Inputlängen) von minimalem Wert, minimaler Anzahl
oder minimaler Gesamtgröße zugeordnet werden (Inputminimierung)
14
. Dabei ist die
Längenausdehnung der großen Objekte in allen Dimensionen fixiert
15
. Die Auswahl an
großen Objekten kann in dieser Kategorie homogen, schwach oder stark heterogen sein.
Bei der in 2.1 dargestellten Problemstellung kann die Menge der Inputlängen nicht
eindeutig klassifiziert werden, weil neben den schwach heterogenen Standardlängen auch
stark heterogene Reststücke aus vorherigen Zuschnittprozessen berücksichtigt werden.
Nach der Typologie von Wäscher, Haußner und Schumann handelt es sich hierbei
dementsprechend um eine Mischform zwischen
Multiple Stock-Size Cutting Stock Problem
(MSSCSP)
16
und Residual Cutting Stock Problem (RCSP)
17
. Allerdings liegt hier eine
Erweiterung vor, da es in der betrachteten Problemstellung zu einer Differenzierung des
Verschnitts kommt, die eine Reststückbildung ermöglicht. Weil angenommen werden
kann, dass die schwach heterogenen Standardlängen den Großteil der Inputlängen
ausmachen und der Einfluss der Reststücke aus vorherigen Zuschnittprozessen relativ
gering ist, wird das Problem im Folgenden als Multiple Stock-Size Cutting Stock Problem
mit Reststückbildung (MSSCSP+R) bezeichnet
18
.
2.2.3
Verschnittbetrachtung
Ein wichtiger Aspekt beim hier betrachteten Zuschnittproblem ist die Differenzierung der
ungenutzten Teile der Inputlängen. Der Verschnitt kann, wie schon erwähnt, sowohl als
Abfall betrachtet als auch als Reststück für spätere Zuschnittprozesse eingelagert werden.
Diese Überlegung macht allerdings nur Sinn, wenn die Abfallkosten im Vergleich zu den
Kosten der Reststücke relativ hoch sind
19
. Die Ersparnis durch die Benutzung von
Reststücken in späteren Zuschnittprozessen muss die zusätzlichen Kosten eben dieser
aufwiegen. Falls die durch die Reststückbildung entstehenden Kosten größer als die
Materialkosten sind, kann hingegen auf die Differenzierung des Verschnitts verzichtet und
14
Vgl. Wäscher / Haußner / Schumann (2007), S. 1117f.
15
Vgl. Wäscher / Haußner / Schumann (2007), S. 1118.
16
Siehe auch Wäscher / Haußner / Schumann (2007), S. 1124.
17
Siehe auch Wäscher / Haußner / Schumann (2007), S. 1124.
18
Auf den Hinweis zur Mischform wird im Namen verzichtet.
19
Vgl. Trkman / Gradisar (2007), S. 292.
- 14 -
auf die gängigen eindimensionalen Zuschnittprobleme mit homogenen (Single Stock-Size
Cutting Stock Problem
20
, kurz SSSCSP) oder schwach heterogenen Inputlängen (Multiple
Stock-Size Cutting Stock Problem
21
, kurz MSSCSP) zurückgegriffen werden.
Im hier relevanten Problem gibt es nun verschiedene Möglichkeiten des Verschnitts für
eine Inputlänge: Entweder die Inputrolle wird vollständig genutzt und in Nachfragelängen
zerteilt oder es entsteht neben den Nachfragelängen noch ein gewisser Teil ungenutzter
Inputlänge, der als Verschnitt bezeichnet wird. Dieser wird, je nach Länge, als Abfall oder
als Reststück betrachtet. Sei die Länge des Verschnitts einer Inputlänge. Dann ergeben
sich folgende drei Möglichkeiten:
t
max
min
max
( )
0
( )
0
[2.3]
( )
a
t
b
t
u
c
r
t
r
.
Hierbei beschreibt (a) den Fall der vollständigen Nutzung der Inputrolle, d. h. es entsteht
kein Verschnitt bzw. er hat die Länge 0. In Fall (b) wird der Verschnitt als Abfall
eingestuft. Dies geschieht, wenn er größer als 0 und kleiner als die maximal zulässige
Länge für Abfall
ist. Wenn die Verschnittlänge t zwischen
und
also der
minimal bzw. maximal zulässigen Länge für Reststücke liegt, wird der Verschnitt als
Reststück betrachtet und am Ende des laufenden Zuschnittprozesses eingelagert, um später
wieder genutzt zu werden. Diesen Fall beschreibt (c).
max
u
min
r
max
r
Je nach Wahl der Parameter
,
und
ergeben sich gewisse
Verschnitteigenschaften. Wie schon erwähnt wird bei diesem Problem angenommen,
dass ein hinreichend großes Lager vorliegt
max
u
min
r
max
r
r
22
somit gilt hier
max
. Für die Wahl von
und
ergeben sich drei Fälle:
max
u
min
r
max
min
max
min
max
min
( )
( )
[2.4]
( )
i
u
r
ii
u
r
iii
u
r
.
Bei Fall (i) darf der Abfall höchstens eine Länge von
haben, die Reststücklänge muss
jedoch mindestens
betragen. Folglich wäre eine Verschnittlänge im Intervall
max
u
min
r
max
min
,
u
r
unerwünscht und solche Zuschnittvarianten der Inputlängen wären vom
20
Siehe auch Wäscher / Haußner / Schumann (2007), S. 1123f.
21
Siehe auch Wäscher / Haußner / Schumann (2007), S. 1124.
22
Siehe auch Kapitel 2.2.1.
- 15 -
Zuschnittprozess ausgenommen. Wird
größer als
gewählt (Fall (ii)), kann
Verschnitt mit einer Länge im Intervall
max
u
min
r
min
max
,
r
u
min
[2.5
r
t
sowohl als Abfall als auch als
Reststück betrachtet werden. Hier muss abgewogen werden, ob die Kosten der erneuten
Nutzung eines Reststücks die Abfallkosten übersteigen und gegebenenfalls auch ein
mögliches Reststück als Abfall entsorgt werden
23
. Der dritte Fall schließt keine
Verschnittlängen aus und lässt eine eindeutige Differenzierung zwischen Abfall und
Reststücken zu, wenn [2.3] geeignet modifiziert wird. Dies ist nötig, falls die
Verschnittlänge genau
beträgt. Möglichkeit (b) wird daher nun in
geändert. In dieser Arbeit wird nur der dritte Fall betrachtet d. h.
.
Aus diesem Grund wird im Folgenden auch auf den Parameter
verzichtet.
Die Möglichkeiten der Verschnittlänge sind nun:
max
min
t
u
r
t
( )
( )
( )
a
t
c
r
max
0
t
u
max
min
u
r
max
u
min
0
b
t
0
]
n
1,
m
k
r
.
In Fall (a) fällt kein Verschnitt an, in (b) wird der entstandene Verschnitt als Abfall
betrachtet und in (c) erfüllt die Länge des Verschnitts die Anforderungen an ein Reststück
und kann somit eingelagert werden.
Für den Parameter
gilt, wie in Kapitel
min
r
r
2.2.1 beschrieben, folgende Bedingung
24
:
mi
1,
,
min
m
i
i
m
l
l
( )
,
in
p
L
( )
6]
k
p
[2.
L
.
Nach Trkman und Gradisar gibt es keine statistisch signifikante Verbindung zwischen der
Wahl von
und den Gesamtkosten des Zuschnittprozesses
min
r
min
r
25
. Die Wahl eines höheren
würde einerseits Nachteile für den aktuellen Zuschnittprozess haben, da mehr Abfall
entsteht, auf der anderen Seite gleicht die erhöhte durchschnittliche Inputlänge in
folgenden Zuschnittprozessen dies wieder aus
26
. Somit kann
nahezu beliebig
zwischen der minimalen Nachfragelänge und der minimalen Inputlänge gewählt werden.
min
23
Siehe auch Trkman / Gradisar (2007), S. 297.
24
Siehe auch Kapitel 2.2.1.
25
Vgl. Trkman / Gradisar (2007), S. 299.
26
Vgl. ebd.
Ende der Leseprobe aus 80 Seiten
- nach oben
- Arbeit zitieren
- Matthias Lange (Autor:in), 2008, Die Berücksichtigung von Reststücken in unterschiedlichen Modellierungsansätzen für das Cutting Stock Problem, München, GRIN Verlag, https://www.grin.com/document/92090
Blick ins Buch
-
-
-
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen.