EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
Optimieren von Schnittplanen
Adrian Loy
30. Juli, 2015
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
Inhaltsverzeichnis
1 Einfuhrung
2 Beweis der NP-Vollstandigkeit
3 ILP
4 HeuristikDefinitionenAlgorithmusKonflikteTestergebnisse
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
Worum geht es?
Wir wollen moglichst effizient Druckbogen zerschneidenDazu verwenden wir nur Guillotinen-Schnitte
Die Anzahl der verwendeten Schnitte soll minimiert werden
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
Worum geht es?
Wir wollen moglichst effizient Druckbogen zerschneidenDazu verwenden wir nur Guillotinen-SchnitteDie Anzahl der verwendeten Schnitte soll minimiert werden
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
Worum geht es?
Wir wollen moglichst effizient Druckbogen zerschneidenDazu verwenden wir nur Guillotinen-SchnitteDie Anzahl der verwendeten Schnitte soll minimiert werden
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
Beispiel: Druckbogen
AB2-1
AB3-1
AB4-1
AD2-1
AP-1
AP-2
AR-1
AR-2
AS-1
AS-2
AU-1AU-2 AV-1AV-2 AW-1AW-2
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
Einsparen von Schnitten
a b c a c
Wir sprechen von Schnittelementen, Schnittkanten undBlocken
Schnittkanten konnen gemeinsam geschnitten werden, wennsie in unterschiedlichen Blocken liegen und mit gleichemAbstand geschnitten werden konnen
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
Einsparen von Schnitten
a b c a c
Wir sprechen von Schnittelementen, Schnittkanten undBlockenSchnittkanten konnen gemeinsam geschnitten werden, wennsie in unterschiedlichen Blocken liegen und mit gleichemAbstand geschnitten werden konnen
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
Einsparen von Schnitten
a b c a c
Wir sprechen von Schnittelementen, Schnittkanten undBlockenSchnittkanten konnen gemeinsam geschnitten werden, wennsie in unterschiedlichen Blocken liegen und mit gleichemAbstand geschnitten werden konnen
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
Einsparen von Schnitten
a b c a c
Wir sprechen von Schnittelementen, Schnittkanten undBlockenSchnittkanten konnen gemeinsam geschnitten werden, wennsie in unterschiedlichen Blocken liegen und mit gleichemAbstand geschnitten werden konnen
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
Vertex Cover
gegeben: Ungerichteter Graph G = (V , E )
gesucht: Minimale Teilmenge von Knoten V ′ ⊆ V , sodassjede Kante von G einen Knoten aus V ′ enthalt
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
Konstruieren von TeilstreifenWir konstruieren fur jede Kante ei = {vj , vk} einen Teilstreifen:
ci
djdk
Die Kante wird durch eine Schnittkanten im Bogen reprasentiertDie reprasentativen Schnittkanten lassen sich mit genau zwei
moglichen Distanzen schneidenJedem Knoten wird eine eindeutige Distanz zugewiesenDiese reprasentieren die Endknoten der Kante
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
Konstruieren von TeilstreifenWir konstruieren fur jede Kante ei = {vj , vk} einen Teilstreifen:
ci
djdk
Die Kante wird durch eine Schnittkanten im Bogen reprasentiert
Die reprasentativen Schnittkanten lassen sich mit genau zweimoglichen Distanzen schneiden
Jedem Knoten wird eine eindeutige Distanz zugewiesenDiese reprasentieren die Endknoten der Kante
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
Konstruieren von TeilstreifenWir konstruieren fur jede Kante ei = {vj , vk} einen Teilstreifen:
ci
djdk
Die Kante wird durch eine Schnittkanten im Bogen reprasentiertDie reprasentativen Schnittkanten lassen sich mit genau zwei
moglichen Distanzen schneiden
Jedem Knoten wird eine eindeutige Distanz zugewiesenDiese reprasentieren die Endknoten der Kante
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
Konstruieren von TeilstreifenWir konstruieren fur jede Kante ei = {vj , vk} einen Teilstreifen:
ci
djdk
Die Kante wird durch eine Schnittkanten im Bogen reprasentiertDie reprasentativen Schnittkanten lassen sich mit genau zwei
moglichen Distanzen schneidenJedem Knoten wird eine eindeutige Distanz zugewiesen
Diese reprasentieren die Endknoten der Kante
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
Konstruieren von TeilstreifenWir konstruieren fur jede Kante ei = {vj , vk} einen Teilstreifen:
ci
djdk
Die Kante wird durch eine Schnittkanten im Bogen reprasentiertDie reprasentativen Schnittkanten lassen sich mit genau zwei
moglichen Distanzen schneidenJedem Knoten wird eine eindeutige Distanz zugewiesenDiese reprasentieren die Endknoten der Kante
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
Konstruieren von TeilstreifenWir konstruieren fur jede Kante ei = {vj , vk} einen Teilstreifen:
ci
djdk
Die Kante wird durch eine Schnittkanten im Bogen reprasentiertDie reprasentativen Schnittkanten lassen sich mit genau zwei
moglichen Distanzen schneidenJedem Knoten wird eine eindeutige Distanz zugewiesenDiese reprasentieren die Endknoten der Kante
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
Konstruieren von BogenAufbau des gesamten Bogens. Ein Knoten vi im Graphen wirddurch den Abstand di = (n + i)n2 reprasentiert.
ci
n4
cj
2n3 + 2n2 ≤ x ≤ 4n3
3m
n4 − 4n3 ≤Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
Reduktion
Bei diesen Abstanden konnen reprasentative Kanten nur mitanderen reprasentativen Kanten gemeinsam geschnittenwerdenEin Schnittplan mit minimaler Anzahl an Schnitten benotigtauch fur die reprasentativen Schnittkanten moglichst wenigSchnitte
Die dafur gewahlten Abstande entsprechen dann einerminimalen Anzahl an Knoten, welche alle Kanten abdecken→ Das Finden von optimalen Schnittplanen ist einNP-vollstandiges Problem!
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
Reduktion
Bei diesen Abstanden konnen reprasentative Kanten nur mitanderen reprasentativen Kanten gemeinsam geschnittenwerdenEin Schnittplan mit minimaler Anzahl an Schnitten benotigtauch fur die reprasentativen Schnittkanten moglichst wenigSchnitteDie dafur gewahlten Abstande entsprechen dann einerminimalen Anzahl an Knoten, welche alle Kanten abdecken
→ Das Finden von optimalen Schnittplanen ist einNP-vollstandiges Problem!
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
Reduktion
Bei diesen Abstanden konnen reprasentative Kanten nur mitanderen reprasentativen Kanten gemeinsam geschnittenwerdenEin Schnittplan mit minimaler Anzahl an Schnitten benotigtauch fur die reprasentativen Schnittkanten moglichst wenigSchnitteDie dafur gewahlten Abstande entsprechen dann einerminimalen Anzahl an Knoten, welche alle Kanten abdecken→ Das Finden von optimalen Schnittplanen ist einNP-vollstandiges Problem!
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
Reduktion
Bei diesen Abstanden konnen reprasentative Kanten nur mitanderen reprasentativen Kanten gemeinsam geschnittenwerdenEin Schnittplan mit minimaler Anzahl an Schnitten benotigtauch fur die reprasentativen Schnittkanten moglichst wenigSchnitteDie dafur gewahlten Abstande entsprechen dann einerminimalen Anzahl an Knoten, welche alle Kanten abdecken→ Das Finden von optimalen Schnittplanen ist einNP-vollstandiges Problem!
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
DefinitionenAlgorithmusKonflikteTestergebnisse
Uberdeckungsfreie Nachbarn
Zwei Elemente sind uberdeckungsfrei benachbart, wenn gilt:Das kleinstmogliche, beide uberdeckende Rechteck uberlapptmit keinem anderen Element
A B
C D
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
DefinitionenAlgorithmusKonflikteTestergebnisse
Uberdeckungsfreie Nachbarn
Zwei Elemente sind uberdeckungsfrei benachbart, wenn gilt:Das kleinstmogliche, beide uberdeckende Rechteck uberlapptmit keinem anderen Element
A B
C D
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
DefinitionenAlgorithmusKonflikteTestergebnisse
SchnittdistanzenFalls zwei Elemente einen Block bilden, gibt es vier moglicheSchnittdistanzen:
A
B
d1d2
d3d4
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
DefinitionenAlgorithmusKonflikteTestergebnisse
Algorithmus: Vorgehensweise
A C
B D
E F G
4 4
1 2 2
1
2
2
A
B
C
D
E F G
1
4
2
4
2
2 2
Kanten verlaufen zwischen uberdeckungsfreien NachbarnKantengewichte stehen fur mogliche Distanzen
Verschmelze iterativ ElementeFuge jeweils die Schnitte hinzu, die diese Verschmelzungumkehren
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
DefinitionenAlgorithmusKonflikteTestergebnisse
Algorithmus: Vorgehensweise
A C
B D
E F G
4 4
1 2 2
1
2
2
A
B
C
D
E F G
1
4
2
4
2
2 2
Kanten verlaufen zwischen uberdeckungsfreien NachbarnKantengewichte stehen fur mogliche DistanzenVerschmelze iterativ Elemente
Fuge jeweils die Schnitte hinzu, die diese Verschmelzungumkehren
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
DefinitionenAlgorithmusKonflikteTestergebnisse
Algorithmus: Vorgehensweise
A C
B D
E F G
4 4
1 2 2
1
2
2
A
B
C
D
E F G
1
4
2
4
2
2 2
Kanten verlaufen zwischen uberdeckungsfreien NachbarnKantengewichte stehen fur mogliche DistanzenVerschmelze iterativ ElementeFuge jeweils die Schnitte hinzu, die diese Verschmelzungumkehren
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
DefinitionenAlgorithmusKonflikteTestergebnisse
Algorithmus: Vorgehensweise
A C
B D
E F G
4 4
1 2 2
1
2
2
A
B
C
D
E F G
1
4
2
4
2
2 2
Kanten verlaufen zwischen uberdeckungsfreien NachbarnKantengewichte stehen fur mogliche DistanzenVerschmelze iterativ ElementeFuge jeweils die Schnitte hinzu, die diese Verschmelzungumkehren
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
DefinitionenAlgorithmusKonflikteTestergebnisse
Auswahl der Elemente fur Verschmelzung
A C
B D
E F G
4 4
1 2 2
1
2
2
H
12 1,5
A
B
C
D
E F G
1
4
2
4
2
2 2
H2
2,5
1,5
Versuche Schnitte zu sparen, indem an Kanten mit gleichenKantengewichten verschmolzen wirdDann haben die hinzugefugten Schnitte den gleichen Abstand→ konnen gemeinsam geschnitten werden
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
DefinitionenAlgorithmusKonflikteTestergebnisse
Auswahl der Elemente fur Verschmelzung
A C
B D
E F G
4 4
1 2 2
1
2
2
H
12 1,5
A
B
C
D
E F G
1
4
2
4
2
2 2
H2
2,5
1,5
Versuche Schnitte zu sparen, indem an Kanten mit gleichenKantengewichten verschmolzen wirdDann haben die hinzugefugten Schnitte den gleichen Abstand→ konnen gemeinsam geschnitten werden
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
DefinitionenAlgorithmusKonflikteTestergebnisse
Auswahl der Elemente fur Verschmelzung
A C
B D
E F G
4 4
1 2 2
1
2
2
H
12 1,5
A
B
C
D
E F G
1
4
2
4
2
2 2
H2
2,5
1,5
Versuche Schnitte zu sparen, indem an Kanten mit gleichenKantengewichten verschmolzen wirdDann haben die hinzugefugten Schnitte den gleichen Abstand→ konnen gemeinsam geschnitten werden
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
DefinitionenAlgorithmusKonflikteTestergebnisse
Iteration 1
A C
B D
E F G
4 4
1 2 2
1
2
2
H
12 1,5
A
B
C
D
E F G
1
4
2
4
2
2 2
H2
2,5
1,5
Entferne alle Kanten, die nicht das haufigste Gewicht habenSuche ein großtmogliches Matching, verschmelze entsprechend
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
DefinitionenAlgorithmusKonflikteTestergebnisse
Iteration 1
A C
B D
E F G
4 4
1 2 2
1
2
2
H
12 1,5
A
B
C
D
E F G
1
4
2
4
2
2 2
H2
2,5
1,5
Entferne alle Kanten, die nicht das haufigste Gewicht habenSuche ein großtmogliches Matching, verschmelze entsprechend
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
DefinitionenAlgorithmusKonflikteTestergebnisse
Iteration 1
A C
B D
E F G
4 4
1 2 2
1
2
2
H
12 1,5
A
B
C
D
E F G
1
4
2
4
2
2 2
H2
2,5
1,5
Entferne alle Kanten, die nicht das haufigste Gewicht habenSuche ein großtmogliches Matching, verschmelze entsprechend
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
DefinitionenAlgorithmusKonflikteTestergebnisse
Iteration 2
AB CD
EF GH
4 4
3 4
1
4
AB CD
EF GH
4
3
4
Entferne alle Kanten, die nicht das haufigste Gewicht habenSuche ein großtmogliches Matching, verschmelze entsprechend
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
DefinitionenAlgorithmusKonflikteTestergebnisse
Iteration 3
ABCD
EFGH
8
7
1
4
ABCD
EFGH
1 4
Entferne alle Kanten, die nicht das haufigste Gewicht habenSuche ein großtmogliches Matching, verschmelze entsprechend
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
DefinitionenAlgorithmusKonflikteTestergebnisse
Iteration 4
ABCDEFGH
8
5
Entferne alle Kanten, die nicht das haufigste Gewicht habenSuche ein großtmogliches Matching, verschmelze entsprechend
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
DefinitionenAlgorithmusKonflikteTestergebnisse
B
C
A
D
E
F
G
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
DefinitionenAlgorithmusKonflikteTestergebnisse
BCA
D
E
F
G
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
DefinitionenAlgorithmusKonflikteTestergebnisse
BCEA
D
F
G
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
DefinitionenAlgorithmusKonflikteTestergebnisse
BCE
D
AF
G
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
DefinitionenAlgorithmusKonflikteTestergebnisse
BCEADF
G
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
DefinitionenAlgorithmusKonflikteTestergebnisse
ABCDEF
G
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
DefinitionenAlgorithmusKonflikteTestergebnisse
ABCDEFG
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
DefinitionenAlgorithmusKonflikteTestergebnisse
B
C
A
D
E
F
G
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
DefinitionenAlgorithmusKonflikteTestergebnisse
C
AB
D
E
F
G
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
DefinitionenAlgorithmusKonflikteTestergebnisse
CE
AB
D
F
G
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
DefinitionenAlgorithmusKonflikteTestergebnisse
CE
AB
D
F
G
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
DefinitionenAlgorithmusKonflikteTestergebnisse
CE
AB
D
F
G
ssolve
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
DefinitionenAlgorithmusKonflikteTestergebnisse
CE
B
D
F
G
ssolve
A
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
DefinitionenAlgorithmusKonflikteTestergebnisse
Konflikte konnen immer aufgelost werdenDie Heuristik findet somit stets eine Losung, wenn eineexistiert
Laufzeit Best-Case: O(n2) (n ist die Anzahl der Elemente)Laufzeit Worst-Case: nicht bewiesen polynomiell, wegen derAnzahl der moglichen Konflikte!
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
DefinitionenAlgorithmusKonflikteTestergebnisse
Konflikte konnen immer aufgelost werdenDie Heuristik findet somit stets eine Losung, wenn eineexistiertLaufzeit Best-Case: O(n2) (n ist die Anzahl der Elemente)
Laufzeit Worst-Case: nicht bewiesen polynomiell, wegen derAnzahl der moglichen Konflikte!
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
DefinitionenAlgorithmusKonflikteTestergebnisse
Konflikte konnen immer aufgelost werdenDie Heuristik findet somit stets eine Losung, wenn eineexistiertLaufzeit Best-Case: O(n2) (n ist die Anzahl der Elemente)Laufzeit Worst-Case: nicht bewiesen polynomiell, wegen derAnzahl der moglichen Konflikte!
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
DefinitionenAlgorithmusKonflikteTestergebnisse
Konflikte konnen immer aufgelost werdenDie Heuristik findet somit stets eine Losung, wenn eineexistiertLaufzeit Best-Case: O(n2) (n ist die Anzahl der Elemente)Laufzeit Worst-Case: nicht bewiesen polynomiell, wegen derAnzahl der moglichen Konflikte!
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
DefinitionenAlgorithmusKonflikteTestergebnisse
Testergebnisse
Implementierung unter JavaTest auf realen Bogen aus der Praxis sowie kunstlicherzeugten Bogen
Kunstliche Bogen bestehen aus gleichen, gitterartigangeordneten RechteckenAuch die kunstlichen Bogen sind praxisrelevant
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
DefinitionenAlgorithmusKonflikteTestergebnisse
Testergebnisse
Implementierung unter JavaTest auf realen Bogen aus der Praxis sowie kunstlicherzeugten BogenKunstliche Bogen bestehen aus gleichen, gitterartigangeordneten Rechtecken
Auch die kunstlichen Bogen sind praxisrelevant
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
DefinitionenAlgorithmusKonflikteTestergebnisse
Testergebnisse
Implementierung unter JavaTest auf realen Bogen aus der Praxis sowie kunstlicherzeugten BogenKunstliche Bogen bestehen aus gleichen, gitterartigangeordneten RechteckenAuch die kunstlichen Bogen sind praxisrelevant
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
DefinitionenAlgorithmusKonflikteTestergebnisse
Testergebnisse
Implementierung unter JavaTest auf realen Bogen aus der Praxis sowie kunstlicherzeugten BogenKunstliche Bogen bestehen aus gleichen, gitterartigangeordneten RechteckenAuch die kunstlichen Bogen sind praxisrelevant
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
DefinitionenAlgorithmusKonflikteTestergebnisse
Naive Losung
Fur die gitterartigen Bogen benotigt eine naive Losung n − 1 vieleSchnitte.
s1 s2 s3
s4
s5
s6
s7
s8
s9
s10
s11
s12
s13
s14
s15
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
DefinitionenAlgorithmusKonflikteTestergebnisse
Optimale Losung
Eine optimale Losung benotigt nur 2dlog√
ne viele Schnitte.
s1s2
s3 s4
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
DefinitionenAlgorithmusKonflikteTestergebnisse
Ergebnisse kunstlicher Datensatz
0 50 100 150 200 250 300 3500
10
20
30
40
50
60
70
80
90
100
Anzahl der Elemente
Anz
ahl S
chni
tteAnzahl der Schnitte auf rechteckigen Gitterboegen
Anzahl Schnitte naive Loesung
Anzahl Schnitte Heuristik
Anzahl Schnitte optimale Loesung
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
DefinitionenAlgorithmusKonflikteTestergebnisse
Laufzeiten kunstlicher Datensatz
0 50 100 150 200 250 300 3500
50
100
150
200
250
300Laufzeit auf rechteckigen Gitterboegen
Lauf
zeit
(in m
s)
Anzahl der Elemente
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
DefinitionenAlgorithmusKonflikteTestergebnisse
Ergebnisse realer Datensatz
100 101 102 103
100
101
102
103
Anzahl der Elemente
Anz
ahl S
chni
tteAnzahl Schnitte auf realem Datensatz
Anzahl Schnitte naive LoesungAnzahl Schnitte Heuristik
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
DefinitionenAlgorithmusKonflikteTestergebnisse
Laufzeiten realer Datensatz
0 50 100 1500
5
10
15
20
25
30
35
40
45
50Laufzeit auf realem Datensatz
Lauf
zeit
(in m
s)
Anzahl der Elemente
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
DefinitionenAlgorithmusKonflikteTestergebnisse
Fazit
Heuristik bietet noch viele VerbesserungsmoglichkeitenWie nutzlich sind die Ergebnisse fur die Praxis?
Guillotine ist nicht beliebig breitBeschleunigt das Einsparen von Schnitten uberhaupt denSchneideprozess?
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
DefinitionenAlgorithmusKonflikteTestergebnisse
Fazit
Heuristik bietet noch viele VerbesserungsmoglichkeitenWie nutzlich sind die Ergebnisse fur die Praxis?
Guillotine ist nicht beliebig breit
Beschleunigt das Einsparen von Schnitten uberhaupt denSchneideprozess?
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
DefinitionenAlgorithmusKonflikteTestergebnisse
Fazit
Heuristik bietet noch viele VerbesserungsmoglichkeitenWie nutzlich sind die Ergebnisse fur die Praxis?
Guillotine ist nicht beliebig breitBeschleunigt das Einsparen von Schnitten uberhaupt denSchneideprozess?
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
DefinitionenAlgorithmusKonflikteTestergebnisse
Fazit
Heuristik bietet noch viele VerbesserungsmoglichkeitenWie nutzlich sind die Ergebnisse fur die Praxis?
Guillotine ist nicht beliebig breitBeschleunigt das Einsparen von Schnitten uberhaupt denSchneideprozess?
Adrian Loy Optimieren von Schnittplanen
EinfuhrungBeweis der NP-Vollstandigkeit
ILPHeuristik
DefinitionenAlgorithmusKonflikteTestergebnisse
Vielen Dank fur ihre Aufmerksamkeit!
Adrian Loy Optimieren von Schnittplanen