Bin Packing Prof. Dr. S. Albers
Prof. Dr. Th. Ottmann
Bin Packing Prof. Dr. S. Albers
Prof. Dr. Th. Ottmann
Bin Packing
1. Problembeschreibung und einfache Beobachtungen
2. Approximative Lösung des Online Bin Packing Problems
3. Approximative Lösung des Offline Bin Packing Problems
Problembeschreibung
Gegeben:
n Objekte der Größen
s1, ... , sn
mit 0 < si 1, für 1 i n.
Gesucht:
Die kleinst mögliche Anzahl von Kisten (Bins) der Größe 1, mit der alle
Objekte verpackt werden können.
Beispiel:
7 Objekte mit Größen 0.2, 0.5, 0.4, 0.7, 0.1, 0.3, 0.8
Problembeschreibung
Online Bin Packing:
Jedes (ankommende) Objekt muss verpackt sein, bevor das nächste
Objekt betrachtet wird. Ein Objekt verbleibt in derjenigen Kiste, in die
es zuerst gepackt wird.
Offline Bin Packing:
Zunächst werden die Anzahl n und alle n Objekte vorgegeben. Dann
beginnt die Verpackung.
Beobachtung
1/2 0 .... ..... 1 2 m m + 1 m + 2 2m Zeit 1 Bin Packing ist beweisbar schwer.
(Offline Version ist NP-schwer.
Entscheidungsproblem ist NP-vollständig.)
Kein Online Bin-Packing Verfahren kann stets
eine optimale Lösung liefern
Online Verfahren
1/2 0 .... ..... 1 2 m m + 1 m + 2 2m Zeit 1 Satz 1
Es gibt Eingaben, die jeden Online Bin Packing Algorithmus zwingen,
wenigstens 4/3 OPT Bins zu verwenden, wobei OPT die minimal
mögliche Binzahl ist.
Beweis:
Annahme: Online Bin Packing Algorithmus A benötigt stets weniger als
4/3 OPT Bins
Online Verfahren
1/2 0 .... ..... 1 2 m m + 1 m + 2 2m Zeit 1 Zeitpunkt 1:
OPT = m/2 und #Bins(A) = b
Es gilt nach Annahme: b < 4/3 m/2 = 2/3m
Sei b1 = #Bins mit einem Objekt
b2 = #Bins mit zwei Objekten
Es gilt: b1 + 2 b2 = m
Online Verfahren
1/2 0 .... ..... 1 2 m m + 1 m + 2 2m Zeit 1 Zeitpunkt 2:
OPT = m und #Bins(A) (b1 + b2 ) + (m – b1) = m + b2
Annahme: m + b2 #Bins( A ) < 4/3 m
b2 < m/3
Online Verfahren
Next Fit (NF), First-Fit (FF), Best-Fit (BF)
Next Fit:
Verpacke das nächste Objekt in dieselbe Kiste wie das vorherige, wenn
es dort noch hineinpasst, sonst öffne eine neue Kiste und verpacke es
dort.
Satz 2
(a) Für alle Inputfolgen I gilt:
NF(I) 2OPT(I).
(b) Es gibt Inputfolgen I mit:
NF(I) 2OPT(I) – 2.
Next Fit
0 1 B1 B2 B2k-1 B2k Beweis: (a)
Betrachte zwei Kisten B2k-1, B2k, 2k NF( I ).
Next Fit
0 1 B1 B2 Bn/4 Bn/4 + 1 0.5 0.5 0.5 0.5 0.5 0.5 2/n 2/n 2/n .......... ..... Beweis: (b)
Betrachte Inputfolge I mit Länge n
(n 0 ( mod 4)):
0.5, 2/n, 0.5, 2/n, 0.5, ... , 0.5, 2/n
Optimale Packung:
Next Fit
0 0.5 1 B1 B2 Bn/2 .......... 2/n 2/n 0.5 0.5 2/n Next Fit Liefert:
NF ( I ) =
OPT ( I ) =
First Fit
First Fit:
Packe nächstes Objekt in die erste Kiste, in die es noch hineinpasst,
wenn es eine solche Kiste gibt, sonst in eine neue Kiste.
Beobachtung:
Zu jedem Zeitpunkt kann es höchstens eine Kiste geben, die weniger
als halb voll ist.
FF( I ) 2OPT( I )
First Fit
Satz 3
(a) Für alle Inputfolgen I gilt:
FF( I ) 17/10 OPT( I )
(b) Es gibt Inputfolgen I mit:
FF( I ) 17/10 (OPT( I ) – 1)
(b´) Es gibt Inputfolgen I mit:
FF( I ) = 10/6 OPT( I )
First Fit
Beweis (b`): Inputfolge der Länge 3 6m
First Fit
First-Fit liefert:
First Fit
.........
Best Fit
Best Fit:
Verpacke das nächste Objekt in diejenige Kiste, in die es am besten
passt (d.h. den geringsten Platz ungenutzt lässt).
Verhalten von BF ähnlich zu FF
Laufzeit für Inputfolgen der Länge n
NF O(n)
FF O(n2) O(n log n)
BF O(n2) O(n log n)
Off-line Verfahren
n und s1, ..., sn sind gegeben, bevor die Verpackung beginnt
Optimale Packung kann durch erschöpfende Suche
bestimmt werden.
Idee für off-line Approximationsalgorithmus:
Sortiere die Objekte zunächst nach abnehmender
Größe und verpacke größerer Objekte zuerst!
First Fit Decreasing (FFD) bzw. FFNI
Best Fit Decreasing (BFD)
First Fit Decreasing
Lemma 1
Sei I eine Folge von n Objekten mit Größen
s1 s2 ..... sn
und sei m = OPT(I).
Dann haben alle von FFD in den Bins
Bm+1,Bm+2, ... , BFFD(I)
verpackten Objekte eine Größe von höchstens 1/3.
Comments