4 Cutting & Packing - Lehrstuhl für Produktion und Logistik

Kapitel 4
Cutting & Packing
Inhalt





4.1 Einleitung/Beispiele
4.2 Typologie & Begriffe
4.3 Eindimensionale Probleme
4.4 Zweidimensionale Probleme
4.5 Dreidimensionale Probleme
(c) Prof. Richard F. Hartl
Transportlogistik
Kapitel 4 / 2
Beispiel 1:
Zuschneiden von Heizungsrohren
Rohre der Länge 9 vorrätig
Es sollen kürzere Rohrstücke der
Längen 2, 3 und 4 (mehrere je Typ)
herausgeschnitten werden
Dabei ist es sinnvoll, „gute“ Schnittmuster
zu finden
Eindimensionales C&P Problem
(c) Prof. Richard F. Hartl
Transportlogistik
Kapitel 4 / 3
Beispiel 2:
Zuschneiden von Platten


Es sollen eine Reihe von kleinen Platten hergestellt
werden (mehrere je Typ)
Es stehen einige Typen von großen Platten zur
Verfügung, aus denen die kleinen Platten geschnitten
werden können.
Zweidimensionales C&P Problem
(c) Prof. Richard F. Hartl
Transportlogistik
Kapitel 4 / 4
Beispiel 3:
Container Beladung

Es sollen eine Reihe von kleinen Boxen in möglichst
wenige Container verladen werden
Dreidimensionales C&P Problem
(c) Prof. Richard F. Hartl
Transportlogistik
Kapitel 4 / 5
Beispiel 4:
Backup auf CDs oder USB Sticks

Eine gegebene Anzahl von Dateien (verschiedene
Größen) soll auf möglichst wenig CDs oder USB Sticks
gesichert werden
Ähnlich wie Beispiel 1
(c) Prof. Richard F. Hartl
Transportlogistik
Kapitel 4 / 6
Beispiel 5:
Rucksackproblem
ein Wanderer will seinen Rucksack packen und kann verschiedene
Dinge mitnehmen (Getränk, Brot, Fernglas, Regenschutz, Kamera,
Handy, Navi ...)
 jedes Teil hat Gewicht und bringt
Nutzen
 bei gegebener Gewichtsbeschränkung (oder Volumens-beschränkung)
für den Rucksack (z.B. 10 kg oder 25
Liter) soll der Nutzen maximiert werden
 Rucksackproblem, „knapsack“-Problem
 ähnlich BSP 1,
aber Nutzen i.a. nicht proportional zu Gewicht

(c) Prof. Richard F. Hartl
Transportlogistik
Kapitel 4 / 7
Beispiel 6:
Kapitalbudget



ein gegebenes Budget soll auf Investitionsprojekte mit
unterschiedlichem internen Zins (bei gleicher Laufzeit)
aufgeteilt werden
Projekte können gleichzeitig realisiert, aber nicht geteilt
werden
Gesamtverzinsung soll maximiert werden
z.B.
Projekt 1:
Projekt 2:
Projekt 3:
Alternativerendite
Gesamtbudget
(c) Prof. Richard F. Hartl
Anfangsinvestition
14 Mio
10 Mio
9 Mio
interner Zinssatz
12 %
11 %
10 %
5%
20 Mio
Transportlogistik
Kapitel 4 / 8
Beispiel 6:
Kapitalbudget – Fortsetzung1
z.B.
Projekt 1:
Projekt 2:
Projekt 3:
Alternativerendite
Gesamtbudget



Zwei mögliche
Lösungen:
Anfangsinvestition
14 Mio
10 Mio
9 Mio
interner Zinssatz
12 %
11 %
10 %
5%
20 Mio
0
Projekt 1
0
Projekt 2
14
10
Projekt 3
20
19 20
Lösung 1: Zinsertrag pro Jahr = 14·12 + 6·5 = 198
Lösung 2: Zinsertrag pro Jahr = 10·11 + 9·10 + 1·5 = 205
(c) Prof. Richard F. Hartl
Transportlogistik
Kapitel 4 / 9
Beispiel 6:
Kapitalbudget – Fortsetzung2



Entspricht Produktionsprogammplanung bei einem
Engpass (Produktion & Logistik 1)
Bei Teilbarkeit 
Produkt DB pro Bearbeitungs- AbsatzhöchstStück
zeit pro Stück
Menge
Reihung nach
relativem DB
j
dj
aj
Aj
(einfach)
1
4
1
200
Unteilbarkeit
2
12
4
75
(nur 0 oder
3
10
2
50
Absatzobergrenze)
4
6
3
40
 np-schweres
5
7
1
100
C&P Problem
(c) Prof. Richard F. Hartl
Transportlogistik
Kapitel 4 / 10
Beispiel 7:
Fliessbandabstimmung

C&P Problem mit Reihenfolgebeschränkungen
Tätigkeit
Beschreibung
Ausführungszeit
Unmittelbar vorhergehende
A
Grundplatte
3
-
B
Achsen
3
A
C
Motor
4
A
D
Getriebe
6
A
E
Räder
8
B
F
Lenkstange
3
C, D
G
Keilriemen
2
D
H
Karosserie
5
E, F
I
Lichtanlage
6
G
J
Scheiben
1
F, H, I
(c) Prof. Richard F. Hartl
Transportlogistik
Kapitel 4 / 11
Inhalt





4.1 Einleitung/Beispiele
4.2 Typologie & Begriffe
4.3 Eindimensionale Probleme
4.4 Zweidimensionale Probleme
4.5 Dreidimensionale Probleme
(c) Prof. Richard F. Hartl
Transportlogistik
Kapitel 4 / 12
4.2 Typologie



Wie gezeigt, lassen sich viele inhaltlich verschiedene
Problemstellungen der BWL als C&P-Probleme
formulieren. Es ist daher sinnvoll, eine allgemeine
Einteilung (Typologie) dieser Probleme vorzunehmen;
siehe: Dyckhoff, 1990, A Typology of C&P problems,
European J. on OR, 44, pp145-159.
Inhaltlich
Dimension
Verlade- oder Beladeprobleme
Anzahl große und kleine Objekte
(c) Prof. Richard F. Hartl
Transportlogistik
Kapitel 4 / 13
Inhaltliche Charakterisierung
C&P im engeren Sinne (räumliche Dimension)


Verschnittprobleme
Verpackungs-, Beladungsprobleme
abstrakte C&P-Probleme (nicht räumliche Dimension)





Gewicht:
Zeit:
Geld:
andere:
Rucksack, vehicle loading
Fließbandabgleich, multiprocesser scheduling
Kapitalbudgetierung
Dateienbackup
 für formale Behandlung und Lösungsmethode nicht wesentlich.
(c) Prof. Richard F. Hartl
Transportlogistik
Kapitel 4 / 14
Dimension







eindimensional 1
zweidimensional 2
dreidimensional 3
…
Objekte sind zwar fast immer dreidimensional,
aber oft sind nur 1 oder 2 Dimensionen relevant
Z.B. wenn nicht gestapelt werden kann.
z.B. Palettenbeladung ist z.B. zumeist
zweidimensional
(c) Prof. Richard F. Hartl
Transportlogistik
Kapitel 4 / 15
Verlade- oder Beladeprobleme




Beladeprobleme:
Alle großen Objekte und eine Auswahl der kleinen
Objekte B
Verladeprobleme:
Alle kleinen Objekte in eine Auswahl der großen Objekte
verpacken V
Ladeprobleme:
Auswahl der kleinen Objekte und Auswahl der großen
Objekte [L]
(Auswahl z.B. nach Wert oder Termin)
(c) Prof. Richard F. Hartl
Transportlogistik
Kapitel 4 / 16
Große und kleine Objekte
Große Objekte



ein Objekt O „one“ (z.B. Rucksackproblem)
identische Objekte I „identical“
verschiedene Objekte D „different“ (20 oder 40 Fuß Container)
Kleine Objekte




wenige Objekte von verschiedenen Formen F „few“
viele Objekte von vielen Formen M „many“
viele Objekte von relativ wenig verschiedenen Formen R
„relatively few“
kongruente (identische) Objekte C „congruent“ (z.B. Paletten
beladen)
 wichtig für die Auswahl der Algorithmen (exakt, Heuristiken)
(c) Prof. Richard F. Hartl
Transportlogistik
Kapitel 4 / 17
Mögliche Typologie
Dimension / Be-Verlade / große Objekte / kleine Objekte
z.B.
Rucksackproblem
Palettenbeladung
klassisches n-dimensionales Verschnittoder Verpackungsproblem
Fließbandabgleich
n-periodiges Kapitalbudgetierungsproblem
"bin-packing"
1/B/O/
2/B/O/C
n/V/I/R
1/V/I/M
1/B/O/
1/V/I/M
 Deckt nicht alles ab  zusätzliche Gliederungsmerkmale
 Oder andere Klassfikation
(c) Prof. Richard F. Hartl
Transportlogistik
Kapitel 4 / 18
Andere Typologien
 z.B. Gerhard Wäscher, Heike Hausner, Holger
Schumann:
An improved typology of cutting and packing problems,
European Journal of Operational Research 183 (2007)
1109–1130.
 Verladeproblme  Input Minimierung
Beladeprobleme  Output Maximierung
…
(c) Prof. Richard F. Hartl
Transportlogistik
Kapitel 4 / 19
Guillotine-Schnitte
Als Schnittmuster kommen in Frage:
 Guillotine-Schnitte z.B. Glas
immer von einem Ende des großen Objekts bis zum
anderen
 verschachtelte Muster erlaubt
 Beschränkung auf Guillotine-Schnitte kann technisch
notwendig sein, auf Grund der einfacheren Handhabung
sinnvoll sein, oder auch nur eine Zweckannahme für die
Optimierung sein.
(c) Prof. Richard F. Hartl
Transportlogistik
Kapitel 4 / 20
Guillotine-Schnitte
1-stufiges Guillotine-Schnittmuster
2-stufiges Guillotine-Schnittmuster
3-stufiges Guillotine-Schnittmuster
verschachteltes Schnittmuster
(c) Prof. Richard F. Hartl
Transportlogistik
Kapitel 4 / 21
Formen

Rechteckig

Allgemeine Formen
(c) Prof. Richard F. Hartl
Transportlogistik
Kapitel 4 / 22
Orientierung



Drehung (z.B. um 900) möglich
Drehung nicht möglich z.B. Holzmaserung, Stoffmuster
Allgemeine Drehung möglich
(c) Prof. Richard F. Hartl
Transportlogistik
Kapitel 4 / 23
Zuordnungsweise
on-line: Stücke müssen sofort verpackt werden
 off-line: simultane Optimierung aller Stücke und dann
Verpackung – Sortierung möglich
Zusammenhang mit statisch/dynamisch
 statisch: alle kleinen Objekte zu Beginn bekannt (off-line)
 dynamisch: kleine Objekte werden nach und nach
bekannt und verfügbar
 on-line ist Extremfall von dynamisch, d.h. immer nur 1
kleines Objekt bekannt, und muss sofort verpackt
werden

(c) Prof. Richard F. Hartl
Transportlogistik
Kapitel 4 / 24
Inhalt





4.1 Einleitung/Beispiele
4.2 Typologie & Begriffe
4.3 Eindimensionale Probleme
4.4 Zweidimensionale Probleme
4.5 Dreidimensionale Probleme
(c) Prof. Richard F. Hartl
Transportlogistik
Kapitel 4 / 25
4.3.1 Eindimensionale Probleme: ONLINE



Wir betrachten den Fall 1/V/I/M (in der Literatur oft als
"Bin-packing" bezeichnet), wo also viele kleine Objekte
in möglichst wenige identische große Objekte eingepackt
werden sollen.
Es sei keine Zeit, aufwendige Berechnungen
anzustellen; die Teile müssen sofort On-Line verpackt
werden.
Die einfachsten bekannten Heuristiken sind



NF (next-fit)
FF (first-fit)
BF (best-fit)
(c) Prof. Richard F. Hartl
Transportlogistik
Kapitel 4 / 26
4.3.1.1 NF (next-fit)


Man ordne das kleine Objekt in das nächste große Objekt, das frei
ist. Wenn also im aktuellen großen Objekt kein Platz mehr ist, wird
ein neues großes Objekt begonnen und die zuvor bepackten großen
Objekte werden nicht weiter betrachtet.
BSP1: große Objekte Länge 8, kleine Objekte Länge 5, 2, 3, 2, 1, 3,
großes Objekt 1:
5
2
5
großes Objekt 2:
3
2
3
großes Objekt 3:
3
3
(c) Prof. Richard F. Hartl
Transportlogistik
7
8
1
5
usw.
6
8
8
Kapitel 4 / 27
4.3.1.2 FF (first-fit)


Man ordne das kleine Objekt in das erste große Objekt ein, in das
es noch hineinpasst. Alle bisherigen großen Objekte kommen also
in Betracht. Nur wenn das kleine Objekt nirgends mehr hineinpasst,
wird ein neues großes Objekt begonnen.
BSP1: große Objekte Länge 8, kleine Objekte Länge 5, 2, 3, 2, 1, 3,
großes Objekt 1:
5
2
59
großes Objekt 2:
3
2
3
(c) Prof. Richard F. Hartl
Transportlogistik
1
7
8
3
5
8
Kapitel 4 / 28
4.3.1.3 BF (best-fit)



man ordne das kleine Objekt in jenes große Objekt ein, wo dann der
kleinste Restraum bleibt. Im Falle von Nichteindeutigkeit wähle man
das erste solche große Objekt.
BSP2: große Objekte Länge 8, kleine Objekte Länge 5, 6, 4, 2, 3, 3
Lösung NF
großes Objekt 1:
5
5
großes Objekt 2:
großes Objekt 3:
großes Objekt 3:
6
4
4
3
3
Transportlogistik
6
8
6
8
6
8
2
3
(c) Prof. Richard F. Hartl
8
Kapitel 4 / 29
4.3.1.3 BF (best-fit)



man ordne das kleine Objekt in jenes große Objekt ein, wo dann der
kleinste Restraum bleibt. Im Falle von Nichteindeutigkeit wähle man
das erste solche große Objekt.
BSP2: große Objekte Länge 8, kleine Objekte Länge 5, 6, 4, 2, 3, 3
Lösung FF großes Objekt 1:
5
2
5
großes Objekt 2:
7
6
6
großes Objekt 3:
4
7
8
3
3
(c) Prof. Richard F. Hartl
8
3
4
großes Objekt 3:
8
Transportlogistik
8
Kapitel 4 / 30
4.3.1.3 BF (best-fit)



man ordne das kleine Objekt in jenes große Objekt ein, wo dann der
kleinste Restraum bleibt. Im Falle von Nichteindeutigkeit wähle man
das erste solche große Objekt.
BSP2: große Objekte Länge 8, kleine Objekte Länge 5, 6, 4, 2, 3, 3
Lösung BF großes Objekt 1:
5
3
5
großes Objekt 2:
8
6
2
6
großes Objekt 3:
4
3
4
(c) Prof. Richard F. Hartl
Transportlogistik
8
7
8
Kapitel 4 / 31
4.3.1.4 Online Algorithmen Komplexität



NF  wächst linear mit Anzahl der kleinen Objekte
FF  wächst quadratisch
(es sei denn, man hält nur ein fixe Maximalzahl an großen Objekten
offen  dann linear
BF  wächst ebenfalls quadratisch
(es sei denn, man hält nur ein fixe Maximalzahl an großen Objekten
offen  dann linear

Meist ist BF die beste und NF die schlechteste Heuristik

Die Effizienz kann gesteigert werden, indem man die kleinen
Objekte zuvor sortiert  Offline Algorithmen
(c) Prof. Richard F. Hartl
Transportlogistik
Kapitel 4 / 32
4.3.2 Eindimensionale Probleme: OFFLINE



Wir betrachten wieder den Fall 1/V/I/M, also das
klassische "Bin-packing" problem, wo also viele kleine
Objekte in möglichst wenige identische große Objekte
eingepackt werden sollen.
Nun sei es möglich, aufwendigere Berechnungen
anzustellen; die Teile müssen nicht sofort On-Line
verpackt werden  sortieren möglich
Die einfachsten bekannten Heuristiken sind



NFD (next-fit decreasing)
FFD (first-fit decreasing)
BFD (best-fit decreasing)
(c) Prof. Richard F. Hartl
Transportlogistik
Kapitel 4 / 33
Eindimensionale Probleme: OFFLINE




Im Falle von NFD bringt das sortieren nicht viel, da die
Lücken später nicht mehr mit kleinen Objekten gefüllt
werden. Es ist ja immer nur ein großes Objekt offen.
Wir lösen daher mit FFD (first-fit decreasing) und BFD
(best-fit decreasing) die obigen Beispiele
BSP1: große Objekte Länge 8, kleine Objekte
Länge 5, 2, 3, 2, 1, 3  5, 3, 3, 2, 2, 1
BSP2: große Objekte Länge 8, kleine Objekte
Länge 5, 6, 4, 2, 3, 3  6, 5, 4, 3, 3, 2
(c) Prof. Richard F. Hartl
Transportlogistik
Kapitel 4 / 34
BSP1: OFFLINE


BSP1: große Objekte Länge 8,
kleine Objekte sortiert 5, 3, 3, 2, 2, 1
Wir lösen mit FFD und BFD
großes Objekt 1:
5
3
5
großes Objekt 2:
3
2
3

8
2
5
1
7
8
In beiden Fällen (zufällig) die optimale Lösung
(c) Prof. Richard F. Hartl
Transportlogistik
Kapitel 4 / 35
BSP2: OFFLINE


BSP2: große Objekte Länge 8,
kleine Objekte sortiert 6, 5, 4, 3, 3, 2
Wir lösen mit FFD und BFD
großes Objekt 1:
6
2
6
großes Objekt 2:
großes Objekt 3:
5
3
5
3
4
4

8
8
7
8
In beiden Fällen (zufällig) die optimale Lösung
(c) Prof. Richard F. Hartl
Transportlogistik
Kapitel 4 / 36
Theoretische Resultate




1. Im Gegensatz zu Heuristiken gibt es für
Approximationsalgorithmen „worst case" Abschätzungen
So kann z.B. für FFD die folgende "worst case" Abschätzung
gezeigt werden:
[Anzahl bins mit FFD]  [optimale Anzahl bins] + 4
2. Wenn die Länge der großen Objekte steigt, so kann die
Anzahl der benötigten Bins nicht steigen
Dies gilt für die optimale Lösung, nicht aber für Heuristiken
oder Approximationsalgorithmen; siehe folgendes Beispiel.
(c) Prof. Richard F. Hartl
Transportlogistik
Kapitel 4 / 37
Gegenbeispiel Anzahl Bins - 60


bei größerer Länge L benötigt FFD mehr große Objekte:
kleine Objekte der Längen
44, 24, 24, 22, 21, 17, 8, 8, 6, 6.
Großes Objekt der Länge 60
44
8
24
22


24
21
8
6
17
6
60
60
60
Bei "Länge" 60 kommt man mit 3 großen Objekten aus.
Diese Lösung ergibt sich bei FFD
(c) Prof. Richard F. Hartl
Transportlogistik
Kapitel 4 / 38
Gegenbeispiel Anzahl Bins – 61


Kleine Objekte der Längen
44, 24, 24, 22, 21, 17, 8, 8, 6, 6.
Großes Objekt der Länge 61
44
17
24
22
24
21
6


8
8
61
61
6
61
61
Bei "Länge" 61 benötigen FFD & BFD 4 große Objekte
Optimale Lösung wäre jene die bei L = 60 herauskam.
(c) Prof. Richard F. Hartl
Transportlogistik
Kapitel 4 / 39
Weitere Lösungsverfahren

Weitere Lösungsverfahren für das Bin-Packing Problem:

Greedy-Heuristik: Löse eine Reihe von Knapsackproblemen,
also jedes große Objekt wird so gut wie möglich befüllt, dann
geht man über zum nächsten Bin (obiges Gegenbeispiel 60-61)



Knapsackprobleme exakt lösbar über dynamisch Optimierung,
Branch & Bound, MIP, oder heuristisch durch Sortierung nach
Nutzen/Gewichtseinkeit (gleiche Idee wie relativer Deckungsbeitrag)
Exakt: Generiere „alle möglichen“ Schnittmuster aus den kleinen
Objekten und wähle dann die beste Kombination mittels MIP aus
(Set covering)
Dabei ist es nicht nötig, alle Schnittmuster zu generieren,
sonderen es werden schrittweise neue Muster generiert
(Spaltengenerierung, column generation)
(c) Prof. Richard F. Hartl
Transportlogistik
Kapitel 4 / 40
Inhalt





4.1 Einleitung/Beispiele
4.2 Typologie & Begriffe
4.3 Eindimensionale Probleme
4.4 Zweidimensionale Probleme
4.5 Dreidimensionale Probleme
(c) Prof. Richard F. Hartl
Transportlogistik
Kapitel 4 / 41
4.4 Zweidimensionale Probleme




Bei zweidimensionalen Problemen haben die kleinen
Objekte nicht nur Länge i sondern auch eine Höhe hi
Ebenso haben die großen Objekte eine Länge L und
eine Höhe H.
Ein einfacherer Fall ist das s.g. „Strip packing“ Problem,
wo nur die Länge L gegeben ist, und ALLE kleinen
Objekte zu verpacken sind, wobei die Gesamthöhe des
“großen Streifens“ zu minimieren ist
Auch 1,5-dimensionales Problem genannt
(c) Prof. Richard F. Hartl
Transportlogistik
Kapitel 4 / 42
4.4.1 ONLINE „Strip packing“ Problem


Ein Niveau-Algorithmus (level algorithm) packt die
kleinen Objekte so, daß mehrere nebeneinander gepackt
werden und die größte Höhe eines dieser Objekte das
Niveau ergibt, wo die nächsten Objekte eingepackt
werden.
Der einfachste Algorithmus ist der der NFL (next fit level)
Algorithmus, in dem die kleinen Objekte in der
Reihenfolge eingepackt werden, in der sie ankommen.
Passt ein kleines Objekt nicht mehr in ein „Level“, so
wird dieses Level geschlossen und ein neues eröffnet.
(c) Prof. Richard F. Hartl
Transportlogistik
Kapitel 4 / 43
Beispiel NFL für Strip Packing





Einfachster ONLINE
Algorithmus NFL
Zunächst wird Level 1 befüllt mit
kl. Objekten 1, 2 und 3.
Objekt 4 hat horizontal keinen
Platz mehr  Level 1
geschlossen (Höhe durch das
höchste Objekt, nämlich Obj. 2
bestimmt), und Level 2 eröffnet
Objekte 4 und 5 in Level 2 (Höhe
durch Objekt 4 bestimmt)
Etc.
(c) Prof. Richard F. Hartl
Transportlogistik
usw.
i= 6
i= 7
i= 8
i= 9
i= 4
i= 5
i= 1
i= 2
i= 3
Kapitel 4 / 44
FFL und BFL für Strip Packing



Deutlich besser sind die Level Algorithmen FFL und BFL, die
immer alle Level offen halten und die Lücken später füllen
können
FFL (first fit level): jedes kleine Objekt wird in das unterste
Level eingepackt, wo es mit Breite i und Höhe hi noch
hineinpaßt. Dabei ist die Höhe des obersten Levels nicht
beschränkt (als ONLINE Algorithmen können die Höhen der
unteren Levels aber nicht mehr verändert werden). Wenn kl.
Obj. nirgends mehr hineinpasst  neues Level beginnen.
BFL (best fit level): wie FFL, nur wird jedes kleine Objekt in
jenes Level eingepackt, wo es am besten passt, wo also der
verbleibende horizontale Restplatz minimal ist.
(c) Prof. Richard F. Hartl
Transportlogistik
Kapitel 4 / 45
Beispiel FFL und BFL für Strip Packing
L=8
kleine Obj. i  hi :
1  8,
5  4,
3  3,
NFL
4  7,
2  3,
1  2,
23
und 4  2.
(c) Prof. Richard F. Hartl
2
4
3
3
2
2 1
3
2
2
2
7
7
3
3
8
4
4
FFL
und
BFL
3
2
4 1
3
8
4
4
3
1
Transportlogistik
5
1
Kapitel54 / 46
2
4.4.2 OFFLINE „Strip packing“ Problem


In vorigen Beispiel sah man, dass BFL (bzw.
auch FFL) zwar den Platz horizontal recht gut
ausnutzen kann, aber vertikal viel Platz
verschwendet wird, weil sehr unterschiedlich
hohe Teile in einem Level angeordnet sind.
Wie in § 4.3.2 kann auch hier aus dem on-lineAlgorithmus ein off-line-Algorithmus gemacht
werden, indem man die kleinen Objekte
zunächst nach abnehmender Höhe sortiert. So
erhält man den BFDH (best fit decreasing
height) Algorithmus.
3
2
2
7
3
Transportlogistik
2
4 1
3
8
4
3
1
(c) Prof. Richard F. Hartl
4
5
2
Kapitel 4 / 47
Beispiel BFDH für Strip Packing
L=8
kleine Obj.:
1  8,
3
2
5  4,
2
7
3  3,
4  7,
FFL
2  3,
und
3
1  2,
BFL
3
23
8
und 4  2.
kleine Obj.
nach Höhe
sortiert
(sekundär
nach Länge):
4
2
4 1
4
3
(c) Prof. Richard F. Hartl
1
5
3
1  8,
2
BFDH
2
4  7,
4
5  4,
3  3,
2  3,
8
7
2  3,
42
und 1  2.
Transportlogistik
2
1
4
3
2
2 1
5
3
Kapitel 4 / 48
4
3
ONLINE „Strip packing“ - Shelf



Auch im Rahmen von Online Algorithmen kann der Platz
vertikal besser ausgenutzt werden, z.B. durch Shelf (Regal)Algorithmen.
Wenn über die Dimensionen der kleinen Objekte zumindest
eine Wahrscheinlichkeitsverteilung bekannt ist, dann kann
man auch optimale Regalhöhen angeben
Im einfachsten Fall sind die Höhen der kleinen Objekte
gleichverteilt zwischen 0 und M. Dann ist es sinnvoll (optimal),
äquidistante „Regalhöhen“ zu definieren, also gleich große
Intervalle, die insgesamt [0,M] ergeben, also z.B.
0, M ,  M , 2M , ...,  M K  2 , M K  1,  M K  1 , M
 K   K K 


K
K  
K
(c) Prof. Richard F. Hartl
Transportlogistik
Kapitel 4 / 49
Beispiel ONLINE „Strip packing“ - Shelf
L=8
kleine Obj.:
1  8,
3
2
5  4,
2
7
3  3,
4  7,
FFL
2  3,
und
3
1  2,
BFL
3
23
8
und 4  2.
Maximale
Höhe M=8
und K=4
Intervalle
[0, 2],
(2, 4],
(4, 6],
(6, 8]:
4
2
4 1
FFS
2 2
1
3
(0, 2]
4
3
2
(2, 4]
2
4
3
5
(2, 4]
3
8
7
(6, 8]
4
3
(c) Prof. Richard F. Hartl
1
5
Transportlogistik
2
1
4
Kapitel 4 / 50
4.4.3 Strip packing  2d Bin packing

1.
2.

Wenn man eine gute Heuristik (z.B. BFDH oder BFS) zur
Lösung des 1,5 dimensionales Problems hat (Strip
packing), kann man leicht daraus eine Heuristik für das
2d Bin packing Problem machen:
Ordne alle kleinen Objekte in Streifen
Löse ein eindimensionales Bin Packing für die Höhe
wobei die gebildeten Streifen die kleinen Objekte sind
Wenn in Schritt 1 die BFDH Heuristik gewählt wird und in
Schritt 2 die FFD Heuristik, nennt man diese 2d Bin
packing Heuristik auch Hybrid First-Fit (HFF)
(c) Prof. Richard F. Hartl
Transportlogistik
Kapitel 4 / 51
Beispiel für Hybrid First-Fit (HFF)

Siehe http://cgi.csc.liv.ac.uk/~epa/surveyhtml.html
Schritt 2
Schritt 1
(c) Prof. Richard F. Hartl
Transportlogistik
Kapitel 4 / 52
4.4.4 Bottom-Left (BL) Algorithmus




Meist wird zunächst nach fallender Breite sortiert, es ist
also dann ein OFFLINE Algorithmus.
Ferner wird nun von der Annahme abgegangen, dass es
ein Guillotine Muster sein muss. Man versucht also die
Lücken noch besser zu füllen und keine Ebenen/Regale
zu bauen → Lösungen sehen ”unordentlicher” aus
Das nächste kl. Objekt wird so tief unten wie möglich
platziert, und dann so weit links wie möglich.
Kann als Strip packing oder auch als 2d Bin packing
Algorithmus verwendet werden
(c) Prof. Richard F. Hartl
Transportlogistik
Kapitel 4 / 53
Beispiel für Bottom-Left (BL)
4
5
7
3
3
2
4
2
8
2
4
3
3
1
(c) Prof. Richard F. Hartl
2
1
Transportlogistik
Kapitel 4 / 54
Vergleich BL - BFDH
4
5
7
3
8
3
2
3
2
2
2
4
4
8
7
2
12
4
3
3
1
3
2
3
3
4
1
5
2
8
7
2
2
1
4
4
4
3
3
(c) Prof. Richard F. Hartl
2
2 1
Transportlogistik
5
3
1
4
Kapitel
3 4 / 55
Mögliche Einfügepositionen



Bei BL
Bei BLF
„bottom
left fill“
Weitere
Punkte
8
7
12
3
1
3
2
2
2
4
4
4
3
(c) Prof. Richard F. Hartl
5
Transportlogistik
3
Kapitel 4 / 56
Weitere Bespiele

Aus: E. K. Burke, G. Kendall, G. Whitwell:
A New Placement Heuristic for the Orthogonal Stock-Cutting Problem,
Operations Research 52 (4, July) , pp. 655–67, 2004
(c) Prof. Richard F. Hartl
Transportlogistik
Kapitel 4 / 57
Weitere Bespiele

Aus: E. K. Burke, G. Kendall, G. Whitwell:
A New Placement Heuristic for the Orthogonal Stock-Cutting Problem,
Operations Research 52 (4, July) , pp. 655–67, 2004
(c) Prof. Richard F. Hartl
Transportlogistik
Kapitel 4 / 58
4.4.5 Touching Perimeter Heuristic

Zunächst wie BL:



Meist wird zunächst nach fallender Breite sortiert, es ist also
dann ein OFFLINE Algorithmus.
Ferner wird nun von der Annahme abgegangen, dass es ein
Guillotine Muster sein muss. Man versucht also die Lücken noch
besser zu füllen und keine Ebenen/Regale zu bauen →
Lösungen sehen ”unordentlicher” aus
Das nächste kl. Objekt wird dort platziert, wo
Berührung mit anderen Objekten oder dem Rand so
groß wie möglich ist. Wenn nicht eindeutig, BL

Kann als Strip packing oder auch als 2d Bin packing Algorithmus
verwendet werden
(c) Prof. Richard F. Hartl
Transportlogistik
Kapitel 4 / 59
Beispiel für Touching Perimeter
4
5
7
3
3
2
4
2
8
2
4
3
3
1
(c) Prof. Richard F. Hartl
2
1
Transportlogistik
Kapitel 4 / 60
Beispiel für Touching Perimeter
4
5
7
3
3
2
2
8
2
4
8
4
7
2
4
3
3
1
2
1
4
(c) Prof. Richard F. Hartl
2 1
3
1
3
2
4
2
3
Transportlogistik
5
3
Kapitel 4 / 61
4.4.6 Best Fit Heuristik

Die kleinen Objekte werden nicht in vorsortierter
Reihenfolge eingefügt, sondern es wird in jeden Schritt
das am besten passendste Objekt gesucht und so tief
wie möglich eingefügt:




Suche tiefste Lücke, füge folgendes kleines Objekt ein
Das höchste, das die Breite der Lücke völlig ausfüllt
Wenn nicht möglich, wähle das breiteste, das Platz hat
(links, höchster Nachbar, niedrigster Nachbar)
Wenn kein Objekt hineinpasst
 schliesse/lösche die Lücke
(c) Prof. Richard F. Hartl
Transportlogistik
Kapitel 4 / 62
4.4.6 Best Fit Heuristik

links, höchster Nachbar, niedrigster Nachbar:

Aus: E. K. Burke, G. Kendall, G. Whitwell:
A New Placement Heuristic for the Orthogonal StockCutting Problem,
Operations Research 52 (4, July) , pp. 655–67, 2004
(c) Prof. Richard F. Hartl
Transportlogistik
Kapitel 4 / 63

Download Report