Verfahren für das eindimensionale Bin Packing Problem (1D-BPP)

Verfahren für das eindimensionale Verfahren für das eindimensionale Bin Packing Problem (1D-BPP) Bin Packing Problem (1D-BPP)

Andreas Bortfeldt, Lst. Wirtschaftsinformatik

Gliederung:1 Das 1D-BPP – Definition und Charakterisierung2 Bekannte Lösungsverfahren im Überblick3 Ein neues Hybridverfahren für das 1D-BPP

1 Das 1D-BPP – Definition und Charakterisierung

1 Das 1D-BPP – Definition und Charakterisierung1.1 Problemformulierung• 1D-BPP:

Gegeben: – n Items (Packstücke) mit Gewichten wj (j = 1,…,n) und – n Bins (Behälter) mit einheitlicher Kapazität c

– c, wj > 0, ganz, c wj , j = 1,…,n

Ordne jedes Item einem Bin derart zu, dass – das Gewicht der Items in keinem Bin c überschreitet und – die Anzahl der benutzten Bins minimal ist

• 1D-DBPP (duales Problem):Gegeben: – n Items wie zuvor, Binanzahl m vorgeschriebenErmittle minimale Kapazität c derart, dass die n Items in m Bins verpackt werden können und zugehörigen Packplan.

• Bin Packing vs. Cutting Stock (CS): – 1D-CSP und 1D-BPP sind strukturell identisch – Differenz: BP: stark heterogen; CS: schwach heterogen

1.1 Problemformulierung

Instanz des 1D-BPP mit Lösung

• Instanz: c = 10, n = 7, (wj) = (5,4,3,2,2,2,2)

(1,5)

(2,4)

(3,3)

(4,2)

(5,2)

(6,2)

(7,2)

Bin 1 Bin 2 Bin 3Legende: (x,y) x = Item-Index; y = Item-Gewicht

frei

1.2 Praktische Anwendungen

1.2 Praktische Anwendungen a) Zuschnitt von Stangenmaterial

Geg.: Ausgangsstangen: l = 650 cm herzustellen: 50 x l1 = 200, 100 x l2 = 160, 100 x l3 = 110Erzeuge Sortiment aus minimaler Anzahl von Ausgangsstangen!1D-BPP: c = 650, n = 250, w1= … = w50 = 200, w51 = 160 usw. – Zuschnittproblem, Cutting Stock!

b) Zusätzliche Praxis-Restriktionen bei Zuschnittproblemen– Maximalzahlen der Zuschnittvarianten (z.B. 2 X l1 + 2 X l3) – Sortiment umfasst Aufträge mit verschiedenen Fertigstellungsterminen

c) Verpacken schwerer Stückgüter in ContainernGeg.: identische Container mit max. Frachtgewicht MW, diverse Stückgüter mit hohem Gewicht (Gewichtsrestriktion dominiert Volumenrestriktion) Verpacke alle Stückgüter unter Beachtung von MW in der minimalen Anzahl von Containern! 1D-BPP: c = MW, … – Packproblem, stark oder schwach heterogen!

1.3 1D-BPP und andere kombinatorische Probleme

1.3 1D-BPP und andere kombinatorische Problemea) Tourenplanungsproblem mit Zeitfenstern (VRPTW)

– n Kunden mit Bedarfen bj mit Fahrzeugtouren zu beliefern– jede Tour startet und endet am einzigen Depot (Beladeort)– jeder Kunde genau einmal anzufahren, in seinem Zeitfenster– pro Tour einheitliche Fahrzeugkapazität c einzuhalten– gesucht: Tourenplan mit

(1) min. Tourenzahl und (2) mit minimaler Gesamtstrecke

Teilproblem 1D-BPP: VRPTW verlangt Zerlegung der n Kunden in min. Anzahl von Teilmengen Ki mit Bedarfssummen ≤ c

b) Bandabgleichproblem (SALBP-1)

– Werkstückfertigung: n Arbeitsvorgänge (AV) mit Zeitbedarfen tj

– die AV sind den Stationen eines Fliessbands unter Beachtung von Vorrangbeziehungen (“AV x vor AV y”) zuzuordnen

– Stationszeit STi: Summe tj der AV der Station i– Taktzeit TT: max. Zeitbudget für alle Stationen, also STi ≤ TT!– gesucht: Zuordnung der AV zu minimaler Anzahl von Stationen

Teilproblem 1D-BPP: SALBP-1 = 1D-BPP + Vorrangbeziehungen!

1.4 Härte und Zugänglichkeit des 1D-BPP

1.4 Härte und Zugänglichkeit des 1D-BPP

• Härte: 1D-BPP ist NP-hart(Rechenzeit exakter Verfahren wächst im worst case exponentiell mit Problemgrösse n)

• Zugänglichkeit:Verfahren lösen grosse Instanzen (500 Stücke) meist global-optimal mit Optimalitätsnachweis! lower bound L(I) – Mindestzahl von Bins für Instanz I;Lösung s mit nb Bins als optimal nachgewiesen, falls lower bound L mit nb = L existiert

• weiterer Aspekt der Zugänglichkeit: reichhaltige Theorie, z.B. Performance-Analyse für grundlegende heuristische Verfahren

2 Bekannte Lösungsverfahren im Überblick

2 Bekannte Lösungsverfahren im Überblick

A) Lösungsverfahren basierend auf linearer Optimierung

1) Set-Covering-Modellierung des 1D-BPP

Zuschnittaufgabe 1.2a): 650, 50x200, 100x160, 100x110Zuschnittvarianten:

Nr. 1 2 3 4 5 6 7 8 9 10 11 l1 = 200 3 2 2 1 1 1 0 0 0 0 0l2 = 160 0 1 0 2 1 0 4 3 2 1 0l3 = 110 0 0 2 1 2 4 0 1 3 4 5Verlust 50 90 30 20 70 10 10 60 0 50 100

(EV) xi: Anzahl Ausgangsstangen, die gemäss Variante i zugeschnitten werden

(NB1) xi ≥ 0, ganz, i = 1,…,11

(NB2) 3x1 +2x2 +2x3 +x4 +x5 +x6 ≥ 50

x2 +2x4 +x5 +4x7 +3x8 +2x9 +x10 ≥ 100

2x3 +x4 +2x5 +4x6 +x8 +3x9 +4x10 +5x11 ≥ 100

(ZF) min z = x1 + x2 + … + x11

∑: Zuschnittaufgabe – ganzzahliges lineares Optimierungsproblem

2.1 Zwei grundlegende Lösungsansätze


2) Lösung des relaxierten linearen Optimierungsproblems (LP)– Ganzzahligkeitsbedingung wird vernachlässigt– relaxiertes stetiges LP wird mittels SIMPLEX-Verfahren schnell gelöst– ganzzahlige zulässige Lösungen durch spezielle Rundung – aufgerundeter Optimalwert des LP – exzellenter (“CS”-) Bound für 1D-BPP

3) Spaltengenerierung (pricing)– zuviele Zuschnittvarianten (= Modellspalten) für Vorab-Erzeugung– benötigte Varianten für optimale Lösung des relaxierten LP “unterwegs” erzeugt

4) Einbettung in Branch-und-Bound-Verfahren (B&B)– Ziel: bessere (grössere) Bounds und/oder verbesserte 1D-BPP-Lösung – spezielle Verzweigung: (P) xj = 2.5 -> (S1) xj ≤ 2 (S2) xj ≥ 3

5) Schnittebenen (cutting planes, cuts)– LP’s werden um zusätzliche Nebenbedingungen erweitert– Ziel: Boundverbesserung

∑: Branch & Cut & Price; Branch & Price (ohne 5); Branch & Cut (ohne 3) Ansätze sehr komplex, anspruchsvoll, effektiv – vor allem für CS-Variante!


B) Kombinatorische Lösungsverfahren

1) Typische Modellierung

2) Allgemeine Merkmale kombinatorischer Verfahren – Ganzzahligkeitsforderungen auch nicht temporär ignoriert– keine Anwendung von “stetiger” linearer Optimierung – Anwendung gewisser Typen von Verfahrenskomponenten

1

1

1

{0,1}, 1 ( )

{0,1}, 1

min ( )

. . , {1,..., } ( )

1, ( )

i i

ij ij

n

ii

n

j ij ij

n

iji

y y Bin i benutzt BoolscheEV

x x Stück j liegt in Bin i

z y ZF

s t w x cy i N n Kapazitäts NB

x j N Zuordnungs NB

2.2 Komponenten kombinatorischer Verfahren

2.2 Komponenten kombinatorischer Verfahrena) Lower Bounds

– Mindestanzahlen zu benutzender Bins – Zweck: - Optimalitätsbeweis, - Beschränkung der Suche

L1 – continuous lower bound:

Beispiel:

c = 100, n = 7, (wj) = (50,50,50,42,42,30,29), L1 = 293/100 = 3

Bound Komplexität Bemerkungen_________________________ L1 O(n) geeignet für wj << cL2 O(n) geeignet wenn teils wj > c/2, L2 ≥ L1

L* O(n) dual feasible functions, L* ≥ L2LC O(n) Gewichtssummen, ZählargumentL3 O(n3) Reduktionsprozedur MTRP, L3 ≥ L2LCS LP-Ber. Cutting-Stock-Bound, gibt meist Opt.wert an!

11

/n

jj

L w c


b) Reduktionsprozeduren

• Zweck: Vereinfachung von Instanzen

• Reduktionsprozedur (RP): erzeugt für eine Instanz I eine Teillösung sP

so dass eine Optimallösung sopt existiert mit sP sop;

Basis von RP: u.a. Dominanzkriterium von Martello/Toth

• Folge: sP kann für Optimallösung vorgemerkt, I kann um sP-Items reduziert werden!

• Beispiel: simple Reduktion ( I = (c,n,(wj)) ): (1) ermittle alle c-Paare: wj + wj’ = c und sammle sie in sP

(2) ergänze sP um (nun) unpaarbare Items: wj + wmin > c

• Anwendung der simplen Reduktion auf Instanz c = 10, n = 6, (wj) = (8,7,7,7,3,2): (1) ⇒ sP = { {8,2}, {7,3} } ; (2) ⇒ sP = { {8,2}, {7,3}, {7}, {7} } sP ist vollständige Lösung, also optimal – RP erzeugt Optimallösung!

• MTRP: sP enthält bis zu 3 Items pro Bin

• Komplexität: simple Reduktion: O(n), MTRP: O(n2)


c) Spezielle Heuristiken

• Zweck: - Erzeugung neuer (vollständiger) Bestlösungen (upper bound) - ab ovo oder ausgehend von Teillösung

• Konstruktions- oder Verbesserungsverfahren

• Beispiel: Heuristik First Fit Decreasing (FFD)

ffd sortiere alle Items absteigend nach Gewicht; for j := 1 to n do

if Item j passt in ein offenes (= teilweise gefülltes) Bin then packe j in erstes geeignetes offenes Bin; {in Indexfolge!}else packe j in neues Bin endif;

endfor;end.


• Anwendung FFD auf Instanz c = 10 n = 7 (wj) = (5,4,3,2,2,2,2)

(1,5)

(2,4)

(3,3)

(4,2)

(5,2)

(6,2)

(7,2)

Bin 1 Bin 2 Bin 3

Legende: (x,y) x = Item-Index; y = Item-Gewicht

frei


• einige Standard-Heuristiken:

Heuristik Komplexität Bemerkung

FFD O(n log n) FF O(n log n) First Fit, wie FFD, aber ohne Item-

Sortierung

BFD O(n log n) Best Fit Decreasing; wie FFD, aber

gewählt

wird das geeignete Bin mit min.

Restkapazität

WFD O(n log n) Worst Fit Decreasing, Gegenstück zu BFD


d) Branch-und Bound-Konzepte

• B&B-Ansatz gemäss Partiallösungskonzept:

– B&B allgemein: abgekürzte Vollenumeration mittels Fallunterscheidung und Ausschluss von Lösungsmengen ohne Optimallösungen

– Partiallösungskonzept: Fallunterscheidung durch alternative Fortsetzung von Partiallösungen

– Ablauf einer Iteration:(1) wähle eine Partiallösung sP

(2) falls sP vollständig dann aktualisiere ggf. Bestlösung sbest und beste aktuelle Binzahl nb_min, gehe zu (1) {Ende Iteration}(3) ermittle lower bound L für alle Lösungen, die aus sP erzeugbar

(4) falls L ≥ nb_min dann gehe zu (1) {Ende Iteration} (5) erzeuge komplette Lösungen ab sP und {evtl.!}

aktualisiere ggf. sbest, nbmin (6) Expansion: erzeuge alle mögl. Fortsetzungen s’P von sP und gehe zu (1)


• Struktur und Fortsetzung von Partiallösungen: (i) stück-orientiert:

– Partiallösung umfasst i. a. mehrere nicht max. gefüllte Bins

– Fortsetzung: das grösste freie Stück wird alternativ in allen geeigneten Bins und in einem neuen Bin verpackt

(ii) bin-orientiert:

– Partiallösung umfasst nur max. gefüllte Bins

– Fortsetzung: ein zusätzliches Bin wird in allen möglichen Varianten zusätzlich gefüllt; aber: das grösste freie Stück muss “dabei sein”

• Auswahl der nächsten Partiallösung:

– Tiefensuche: Partiallösung mit max. Itemzahl bzw. Binzahl

– Bestensuche: Partiallösung mit minimalem lower bound

• Dominanzregeln für Expansion:

– Vermeidung redundanter Suchpfade (ohne Exaktheitsverlust)

– Beispiel: keine Erzeugung nicht maximal gefüllter Bins bei Ansatz (ii)

– verwandt mit Reduktion


• Metaheuristik:– durch Adaption allgemein verwendbarer Suchstrategie an gegebenes Problem– Suche nicht systematisch– erzeugt im allgemeinen viele (z.B. 105) Lösungen

• Genetische Algorithmen (GA):– Populationsbasiert:

Menge von aktuellen Lösungen wird simultan gehalten und verbessert– Crossover-Operator:

erzeugt Nachkommen durch Neukombination von Merkmalen je zweier Eltern– Gerichtete Suche:

Eltern mit besserer Lösungsqualität werden mit höherer Wahrscheinlichkeit zur Generierung von Nachkommen ausgewählt

• Qualifizierte Strategien der Nachbarschaftssuche: Tabu Search (TS), Simul. Annealing (SA), Variable Neighborhood Search (VNS)

– Modifikation elementarer Nachbarschaftssuche („Bergsteigen“) so dassSteckenbleiben in ungenügenden lokalen Optimallösungen verhindert wird

– Nachbarschaftsbegriff – entscheidendes Konzept

e) Metaheuristiken

2.3 Einige kombinatorische Verfahren für das 1D-BPP

(1) Branch&Bound Verfahren MTP von Martello und Toth (1990)

A) Komponenten im Überblick

1) Bounds: L1, L2, L3

2) Reduktionsprozeduren (RP): MTRP

3) Spezielle Heuristiken: FFD, BFD, WFD

4) B&B-Konzepte:4.1) Fortsetzung von Partiallösungen: stückorientiert

4.2) Auswahl von Partiallösungen: gemäß Tiefensuche und Bin-Indizier.

4.3) Dominanzregeln (DR): eine einfache DR

5) Metaheuristiken: –

B) Weitere Charakterisierung• Bounds, RP und spezielle Heuristiken werden innerhalb von B&B

eingesetzt• spez. Heuristiken übernehmen teils Expansion des Suchbaums



(2) Genetischer Algorithmus HGGA von Falkenauer (1996)


1) Bounds: L1

2) Reduktionsprozeduren (RP): –

3) Spezielle Heuristiken: FFD, FF

4) B&B-Konzepte: –

5) Metaheuristiken: GA

B) Weitere Charakterisierung• basiert auf Kodierung für Gruppierungs-Probleme, wo Lösungen

Partitionen einer Objektmenge sind (“Grouping GA”).

• CO-Operator: - kombiniert gefüllte Bins beider Eltern, - mehrfach gepackte Items werden entfernt, - Kinder werden mittels FFD, FF und Dominanzregel komplettiert.


(3) Branch&Bound-Verfahren von Schoenfield (2002)

A) Komponenten im Überblick 1) Bounds: L1, L2, L3, LC, weitere neue Bounds

2) Reduktionsprozeduren (RP): MTRP, weitere neue RP

3) Spezielle Heuristiken: FFD, BFD, WFD, weitere neue Heuristiken

4) B&B-Konzepte:

4.1) Fortsetzung von Partiallösungen: binorientiert

4.2) Auswahl von Partiallösungen: gemäss Tiefensuche

4.3) Dominanzregeln (DR): verschiedene DR

5) Metaheuristiken: –

B) Weitere Charakterisierung• reichhaltiger Beitrag Schoenfield (2002) schlägt Vielzahl neuer

Bounds, RP und Heuristiken vor; die (teils) in das B&B-Verfahren einfliessen

• Test von 370000 Instanzen; 28 ultra-harte Instanzen (“Hard28”) extrahiert


(4) Hybridverfahren HI_BP von Alvim et al. (2004)


1) Bounds: L1, L2, L3, L* , L (neu)

2) Reduktionsprozeduren (RP): MTRP

3) Spezielle Heuristiken: DBFD (BFD für duales BPP), …

4) B&B-Konzepte: –

5) Metaheuristiken: TS

B) Weitere Charakterisierung• iteratives Verbesserungsverfahren: pro Iteration wird zuerst

Startlösung für duales BPP mittels dualer Heuristiken wie DBFD bestimmt;

• TS-Verfahren: versucht DBP-Lösung in zulässige BP-Lösung zu transformieren, d.h. Kapazitätsverletzungen zu beseitigen

• Nachbarschaft bei TS durch swap-moves definiert: tausche Item j1 aus Bin i1 gegen Item j2 aus Bin i2

2.4 Verfahren für das 1D-BPP seit 1990 – eine Bilanz

• weitere 1D-BPP-Verfahren sind u.a.:- Hybrid B&B/TS Scholl et al. (1997)- MTP mit CS-Bound Schwerin/Wäscher (1998)- Variable Neighborhood Search Fleszar/Hindi (2002)- Branch&Cut&Price Belov/Scheithauer (2003)

• stärkste Verfahren für stark-heterogenes 1D-BPP:(1) Branch&Cut&Price Belov/Scheithauer (2003)(2) Branch&Bound Schoenfield (2002)(3) Hybrid-TS-Verfahren Alvim et al. (2004)

- (1), (2): 28 ultra-harte Schoenfield-Instanzen gelöst- (3): beste Resultate bei direktem Verfahrensvergleich (ausser (1),(2))

• wichtige Trends: a) immer komplexere Verfahren: Hybrid-Ansätze, viele Komponentenb) kombinatorische Verfahren: entweder B&B oder Metaheuristiken; einfache spezialisierte Heuristiken spielen nur eine Hilfsrolle c) Integration verschiedener Bounds spiegelt Vielgestaltigkeit des 1D-BPP: verschiedenartige Instanzen brauchen verschiedene Bounds; insofern ist Spezialisierung „gesund“ d) hilfsweise Lösung des dualen Problems (1D-DBPP)

2.4 Verfahren für das 1D-BPP seit 1990 – eine Bilanz

3 Ein neues Hybridverfahren für das 1D-BPP

3 Ein neues Hybridverfahren für das 1D-BPP

1. Kann man ein wenig hybrides aber effektives Verfahren entwickeln? Ohne Kreuzung von metaheuristischer Suche und Baumsuche, ohne Behandlung des dualen Problems usw.

2. Dennoch sind effektive Komponenten aus der Literatur (Bounds, RP, spezielle Heuristiken) unumgänglich. Interessant: was bringt Integration von Schoenfield-Ergebnissen?

3. Schwachstelle bei Belov/Scheithauer, Schoenfield: Triplet-Instanzen! Def: es exist. Optimallösung, in der jedes Bin verlustlos mit 3 Items gefüllt ist.

Kann man hier Verbesserung erreichen?

4. Konventionelle Heuristiken spielen Junior-Rolle in hybriden Verfahren. Gibt es konventionelle Verbesserungs-Heuristik, die die Güte von Metaheuristiken erreicht?

3.1 Fragen, Anhaltspunkte, Verfahrensschema

3.1 Fragen, Anhaltspunkte, Verfahrensschema

Schema des Hybridverfahrens

01 wende Reduktionsprozeduren (RP) rpsimple, rpex2(ffd) an (ggf. stop) 02 berechne lower bounds L1, L2, L*, LC (und deren Maximum)03 wende ffd an (ggf. stop)04 wende RP mtrp, rpc(ffdp1/ ffdp2) an (ggf. stop)05 wende Heuristiken ffdp1, ffdp2 an (ggf. stop)06 berechne lower bound L3 (ggf. stop)07 wende Heuristik ffdp an (ggf. stop) 08 berechne lower bounds LCL, LCS (ggf. stop)09 wende B&B-Verfahren an10 gib Bestlösung zurück (ggf. mit Anteil aus Reduktion)

Kommentare:

• “ggf. stop” – Abbruch wenn Optimallösung nachweislich erreicht

• neue Komponenten: Heuristiken: ffdp1, ffdp2, ffdp, B&B-Verfahren, Bound LCL

• Rest: Literatur; Bound LC und RP rpex2, rpc von Schoenfield übernommen

• Gliederung nach wachsender Komplexität: z.B. 2: O(n); 4: O(n2); 6: O(n3)

3.2 Die Heuristiken ffdp1, ffdp2 und ffdp


1. ffd

sortiere Items absteigend nach Gewichtwhile freies Item vorhanden do

j1 := grösstes freies Item if j1 passt in ein offenes Bin then {if-Fall}

ermittle erstes geeignetes offenes Bin ioldpacke j1 in iold

else öffne neues Bin inew und packe j1 dort endif {else-Fall}endwhile

2. ffdp1 (“… with pairs”) – wie ffd, aber:

• if-Fall:ermittle erstes geeignetes offenes Bin iold j2 := zweitgrösstes freies Itemif w(j1) + w(j2) ≥ freie Kapazität von iold then

packe grösstmögliches Paar freier Items (j1*, j2*) in Bin ioldelse packe j1 in iold endif

• else-Fall: unverändert

a) Konstruktions-Heuristiken ffdp1, ffdp2


• Anwendungsbeispiel für ffd und ffdp1: Instanz c = 10, n = 7, (wj) = (5,4,3,2,2,2,2)

ffd packt: ffdp1 packt:

1. 5 in Bin 1 5 in Bin 1 2. 4 in Bin 1 - Rest 1 3 und 2 in Bin 1 (Prüfung: 4 + 3 > 5!) 3. 3 in Bin 2 4 in Bin 2 4. 2 in Bin 2 2 in Bin 2 5. 2 in Bin 2 2 in Bin 2 6. 2 in Bin 2 - Rest 1 2 in Bin 2 7. 2 in Bin 3 Ergo: 1 Bin gespart

L1 = 20/10 = 2, ffdp1-Lösung ist optimal!

Bin 1 Bin 2 Bin 3

(1,5)

(2,4)

(3,3)

(4,2)

(5,2)

(6,2)

(7,2)

Bin 1 Bin 2

(1,5)

(3,3)

(4,2)

(5,2)

(6,2)

(2,4)

(7,2)

Legende: (x,y)

x = Item-Index

y = Item-Gewicht

frei


• Motiv für ffdp1: passen grösstes und zweitgrösstes freies Item nicht mehr in Bin iold, sucht man nach grösstem passenden Paar freier Items für den Rest von iold, um keine Kapazität zu verschenken

3. ffdp2 – wie ffd, aber:

• if-Fall: wie in ffdp1

• else-Fall: {neues Bin zu packen}j2, j3 := zweit- bzw. drittgrösstes freies Item (nach j1)if w(j1) + w(j2) + w(j3) ≥ c then {X}

bestimme grösstes Item-Paar (j2*, j3*) mit w(j1) + w(j2*) + w(j3*) c, j2* j1, j3* j1,

packe j1, j2*, j3* in neues Bin inewelse packe nur j1 in inew endif

• ähnliche Logik wie bei ffdp1:- Suche nach bestem Tripel für ganzes Bin wird durchgeführt, wenn die 3 grössten Items gerade noch / nicht mehr passen- Item j1 wird stets in Tripel einbezogen, um Suchaufwand zu begrenzen

• tie breaker für Bestimmung der Paare in ffdp1, ffdp2: grössere Verfügbarkeit der Gewichte entscheidet


b) Bin-orientierte Versionen von ffd/ffdp1/ffdp2

• Bin-orientiert (bo): – Bins werden separat gefüllt – Frage: wie wird 1 einzelnes Bin

gefüllt?

• ffd_bo:if mindestens ein freies Item passt in aktuelles Bin then

packe das grösste freie passende Itemendif

• ffdp1_bo:wie ffd_bo, aber es wird mindestens einmal ein einzelnes Item verpackt,

dann wird Item-Paar verpackt, wenn Paarsuche- Bedingung von ffdp1 erfüllt ist

• ffdp2_bo: ähnlich wie ffdp1_bo.


c) Verbesserungs-Heuristik ffdp

• Iteratives Verfahren, pro Iteration 1 Lösung, in i-ter Iteration werden: - i Bins mit bin-orientierter Heuristik (ch1_bo)- restliche Bins mit stück-orientierter Heuristik (ch2) gefüllt

• i := 1; stop_flag := 0;forever

fülle i Bins mittels Heuristik ch1_bo;if Gesamt-Gewicht freier Stücke c then stop_flag := 1 endif;komplettiere aktuelle Lösung s durch Heuristik ch2;aktualisiere ggf. Bestlösungif stop_flag = 1 then break endif; {alle Varianten

erschöpft!} i := i + 1;

endfor;

• Diversifikation: 3 Kombinationen (ch1_bo, ch2) – 3 Durchläufe: (1) (ffd_bo, ffdp1), (2) (ffd_bo), ffdp2), (3) (ffdp2_bo, ffdp1)

3.3 Das Branch & Bound Verfahren


• Zweck: 1) neue Bestlösung (Binreduzierung) oder2) Optimalitätsbeweis für alte Bestlösung durch (i.d.R.) vollständige Suche

• Fortsetzungs-Schema:Bin-orientiert, pro Schritt wird Partiallösung um ein gefülltes Bin erweitert

• Tiefensuche, Backtracking-Prozedur:

extend_solution (scurr){

if scurr ist komplette Lösung then aktualisiere sbest; return endif;erzeuge n neue Packings (Itemmengen für 1 Bin) p1,…,pn;for i = 1 to n do

extend_solution (scurr pi)endfor

}

a) Ansatz


b) Drei Problem-Varianten

• B&B-Verfahren unterscheidet 3 Problem-Varianten;jede Variante wird spezifisch behandelt

• Problem-Variante “triplet”Def.: (1) wj = m · c, m bester lower bound d.h. Lösung mit m Bins nur erreichbar, wenn jedes Bin restlos gefüllt wird

(2) Item-Anzahl n = 3*m

• Problem-Variante “small- ”Def.: (1) 3; = minimale Anzahl Items pro Bin bei Lösung mit m Bins; berechenbar nach Resultat von Alvim et al. (2004)

(2) nicht triplet

• Problem-Variante “normal”Def.: (1) nicht triplet und nicht small-


c) Problem-Variante “normal”

• Ausscheidung von Partiallösungen vor Expansion:- erfolgt mittels O(n)-Bounds LC, L*

• Erzeugung von Nachfolgern pro Iteration: - alle Packings (Itemmengen für 1 Bin) erzeugt, die ein Item mit max. Gewicht enthalten (max. bzgl. freier Items!)

• Selektion von Packings mittels L1-Bound und Dominanzregeln: - nur maximale Packings, - Mehrfacherzeugung von Partiallösungen wird vermindert

• wichtiges feature: Verwendung von 4 Sortiermodi für neue Packings (1) Erzeugungsreihenfolge (Packings mit lauter grossen Items zuerst) (2) Inverse Erzeugungsrf. (Packings mit kleinen Items zuerst) (3) Zweites Drittel zuerst (Packings mit mittelgrossen Items zuerst) (4) Sortierung nach Verlust (verlustarme Packings zuerst)

- Sortierung neuer Packings bestimmt Reihenfolge weiterer Expansionen- “richtige” Sortierung der Packings führt ggf. rasch zu neuen Bestlösungen


d) Problem-Variante “triplet”

• allgemeine Merkmale– gesucht: Lösung aus lauter 3-0-Packings (3 Items, 0 Verlust) – auf beliebigem Suchpfad wird Suche abgebrochen, falls ein Item ohne anwendbares 3-0-Packing ist (fehlende Partner!)

• Erzeugung neuer Packings per Iteration– alle anwendbaren 3-0-Packings mit einem Item des Typs iturg – Itemtyp iturg = Typ mit maximaler Dringlichkeit Urg(it): Urg(it) = # freie Exemplare(it) – # anwendbarer 3-0-Packings(it) – d.h.: für Typ iturg ist “Versorgung” mit 3-0-Packings am dringlichsten!

• Sortierung neuer Packings absteigend nach Dringlichkeit: – Urg(Packing) = Urg(it) - Summe über alle Itemtypen des Packing


e) Problem-Variante “small-”• Behandlung von “small-”-Instanzen zuerst wie “normal”-Instanzen;

Anwendung aller 4 Sortiermodi

• zwei weitere Suchen:

• Suche “small--1”– 3-Stufen-Erzeugung von Lösungen: erst 2-Packings, dann 3-0-Packings, dann beliebige n-Packings – Übergang von Stufe 1 zu Stufe 2: wenn (berechenbare) Minimalzahl von 2-Packings erreicht– Übergang von Stufe 2 zu Stufe 3: wenn keine 3-0-Packings mehr realisierbar sind

• Suche “small--2”– wie bei “normal”-Variante, aber mit “Dringlichkeits-Sortierung” von Packings ähnlich wie bei “triplet”-Variante


f) B&B-Suche im Überblick und Aufwandsphasen

if problem_variante = “triplet” thenmax_nodes = 500000; // max. Anzahl Rufe Proz. extend_solutionausführen “triplet”-Suche

else // “normal” or “small-”for i = 1 to 5 do // 5 Aufwands-Phasen mit …

max_nodes = 10i+1; // max. 100, 1000, …, 1000000 Knoten for sort_mode = 1 to 4 do

ausführen “normal”-Sucheendfor;if problem_variante =“small-” then

ausführen “small--1”-Sucheausführen “small--2”-Suche

endifendfor

endif

Zweck Aufwandsstaffelung: - oft ist ein Sortiermodus geeignet, die anderen nicht - Aufwandsstaffelung realisiert ein “Sortier-Karussell” und vermeidet langes Suche mit “falschen” Sortiermodi!

3.4 Test des Hybridverfahrens


• Hybridverfahren in C implementiert, nachfolgend bezeichnet mit “HP”

• Testrechnungen auf 2 GHz PC mit Zeitschranke 60s

• komplettes Verfahren HP wird verglichen mit stärksten 1D-BPP-Verfahren: - Alvim et al. - Belov/Scheithauer - Schoenfield

• Ergebnisse für Verbesserungs-Heuristik ffdp werden separat ausgewiesen

a) Allgemeines


• 440 Instanz-Klassen von Schwerin & Wäscher

– jede Klasse umfasst 100 Instanzen - 44000 Instanzen,n = 20–200, Gewichte gleichverteilt in klassenspez. Intervall

– 145 Klassen gelten als schwierig: FFD dort schwach

• 28 harte Instanzen von Schoenfield (Generator: wie bei Schwerin & Wäscher-Instanzen)

b) Sets von Benchmark-Instanzen

Autoren Set Anzahl Instanzen

Anzahl Items pro Instanz

Bemerkung

Falkenauer uniform 80 120–1000 Gewichte gleichverteilt

triplet 80 60–501 triplet-Instanzen

Scholl, set_1 720 50–500 Gewichte gleichverteilt

Klein & set_2 480 50–500 set_2: mehr Items pro Bin

Jürgens set_3 10 200 Gewichte breit gestreut, kompliziert


c) Ergebnisse des kompletten Verfahrens HP

• 160 Falkenauer-Instanzen und 1210 Scholl-Instanzen:

– Alvim et al. und HP lösen beide alle 1370 Instanzen– Verfahren von Alvim et al.: i.allg. mehr Rechenzeit als HP

Triplet-Instanzen: Faktor 10– Belov/Scheithauer: Rechenzeit für Triplet-Instanzen

liegt um Faktor 200 höher im Vergleich zu HP– Schoenfield löst (offenbar) nicht alle Triplet-Instanzen von Falkenauer

• 44000 Wäscher-Instanzen; darunter 14500 ffd-harte Instanzen:

– HP löst 99.52% aller 44000 Instanzen (213 nicht); mittl. Rechenzeit: 350 ms– HP löst 14318 = 98.74% der ffd-harten Instanzen, 125 mehr als Alvim et al.– Belov/Scheithauer erzielen noch bessere Resultate für vergleichbares Set

• 28 harte Schoenfield-Instanzen:

– Schoenfield und Belov/Scheithauer lösen alle 28 Instanzen– HP löst nur 14 Instanzen

: + HP erzielt bessere Ergebnisse als Alvim et al. – Belov/Scheithauer und Schoenfield dominieren bei extrem-harten Instanzen + HP schneidet besonders gut ab bei Triplet-Instanzen


d) Ergebnisse der Heuristik ffdp

Autoren Set Anzahl Instanzen

Anzahl mit ffdp gelösterInstanzen

mittl. Vergleich mit Anz. Metaheuristiken / B&B Lösng. + : ffdp besser als

Falkenauer uniform 80 79 4.0 +GA-Falkenauer

triplet 80 0 67.6

Scholl, set_1 720 708 4.9 +BISON-Scholl +VNS-Fleszar/Hindi

Klein & set_2 480 409 10.7 +MTPCS-Schwerin/Wäscher

Jürgens set_3 10 7 6.3 +BISON-Scholl +VNS-Fleszar/Hindi

Schwerin &Wäscher

440 Kl. 44000 41976= 95.4%

4.5 +MTPCS-Schwerin/Wäscher

• Heuristik ffdp für Test = komplettes Verfahren HP minus B&B-Verfahren (insbes. Bounds und RP rechnen zu ffdp!)

3.5 Hybridverfahren HP – vorläufige Bilanz

3.5 Hybridverfahren HP – vorläufige Bilanz

• HP kann zu den effektivsten Verfahren für das stark-heterogene 1D-BPP gerechnet werden; erzielt besonders gute Ergebnisse für Triplet-Instanzen

• HP ist konzeptionell eher einfach: Verbesserungs-Heuristik mit nachgeschaltetem B&B plus diverse Bounds und RP

• Verbesserungsverfahren ffdp dominiert z.T. Metaheuristiken / B&B ffdp erzeugt im Mittel nur wenige Lösungen pro Instanz

• wesentliche B&B-features: - differenzierte Behandlung verschiedener Problem-Varianten- verschiedene Sortiermodi für Nachfolger mit alternierender Anwendung

• Weiterentwicklung geplant: u.a. stärkere Dominanzregeln

Documents

Verfahren für das eindimensionale Bin Packing Problem (1D-BPP)