Visualisierung vom Online Bin Packing

Bin Packing bezeichnet das Problem hintereinander ankommende Requests in Form von Gewichten in Bins zu packen. Die Bins haben eine feste maximale Füllgröße und die Gewichte der Requests müssen kleiner als diese Füllgröße sein. Jedes Gewicht muss sofort gepackt werden, noch bevor bekannt wird welches Gewicht das nächste zu packende Gewicht hat. Wenn für ein Gewicht kein Bin mit ausreichend Platz vorhanden ist, so muss ein neues Bin angelegt werden. Das Ziel des Bin Packings ist so wenig Bins wie möglich zu verwenden.

Hier gehen wir von normierten Bins aus, so dass die Gewichte immer einen Wert zwischen 0 und 1 einnehmen müssen.

Allgemeines zum Bin-Packing

Die Allgorithmen Last-Fit, Worst-Fit, Next-Fit haben den kompetitiven Faktor 2. Besser sind die Algorithmen First-Fit, Best-Fit und Allmost-Worst-Fit, diese haben den kompetitiven Faktor 17/10. ( Für einen Beweis siehe "Online Computation and Competitive Analysis" von Allan Borodin und Ran El-Yaniv). Die beste bisher bewiesene untere Schranke ist 1,54. Es gibt somit für jeden Algorithmus mindestens eine Folge, so dass der Quotient von Onlinekosten und Offlinekosten gegen 1,54 geht. Die beste bisher bewiesene obere Schranke beträgt 1,5887. Es gibt somit einen Algorithmus, der für jede Eingabefolge für den Quotienten Onlinekosten/ Offlinekosten maximal gegen 1,5887 geht.

Erklärung des Applets

Im oberen Bereich des Applets findet die Visualisierung statt.
Der erste Kasten unter Onlineberechnung stellt im Verlauf der Visualisierung die Onlineberechnung des ausgewählten Onlineverfahren dar.
Der zweite Kasten unter Offlineberechnung stellt dann die optimale Offlineberechnung dar

Im unteren Bereich findet links die Ausgabe der optimalen Kosten, sowie der online Kosten und dem Quotienten zwischen Online Kosten und Offline Kosten statt. Die jeweiligen Kosten sind immer die Anzahl der bisher verwendeten Bins. Der Quotient gibt eine Art Güte des Online Algorithmusses für die bisher verwendeten Requests dar, dieser Quotient kann natürlich nicht größer werden als der kompetitive Faktor des verwendeten Online Algorithmusses.

Im unteren Bereich rechts befindet sich dann die Eingabe.
Hinter Online-Verfahren kann für den nächsten Request der gewünschte Online Algorithmus ausgewählt werden. Behind "Online-Verfahren" you can chose the preferred onlinealgorithm for the next request.:]
Mit der Auswahl für die Offline-Algorithmen kann der jeweils zu verwendende Offline-Algorithmus ausgewählt werden.
Mit dem Reset-Button kann das Applet in seine Ausgangslage zurückgesetzt werden.
Hinter Gewicht können Prozentwerte zwischen 0 und 100 eingegeben werden. Um eine längere Eingabe zu tätigen müssen die Prozentwerte mit einem Leerzeichen getrennt werden.
Zahlen mit Nachkommaanteil müssen mit "." angegeben werden.
Durch den Makebutton wird die erste Gewichtseingabe bearbeitet, mit dem MakeAll Button wird die gesamte Gewichtsleiste bearbeitet. In der letzten Auswahlliste können dann noch Beispielfolgen ausgewählt werden.

Achtung: Bei Benutzung von optimal als optimalen Offline Algorithmus, werden durch die nicht vermeidbar exponentielle Laufzeit schnell sehr hohe Laufzeiten erreicht. (Offline Bin Packing ist NP-Hart)

Applet zur Visialisierung des Bin Packings

Online-Verfahren

Alle Verfahren erschaffen ein neues Bin, wenn die folgende Aktion nicht ausführbar ist.
First-Fit: Das erste befüllbare Bin wird gefüllt. c=17/10
Last-Fit: Das letzte befüllbare Bin wird gefüllt. c=2
Best-Fit: Das vollste befüllbare Bin wird gefüllt. c=17/10
Worst-Fit: Das leerste befüllbare Bin wird gefüllt. c=2
Allmost-Worst-Fit: Das zweit leerste befüllbare Bin wird gefüllt, wenn es dieses gibt, ansonsten wird das leerste Bin gefüllt. c=17/10
Next-Fit: Das letzte Bin wird befüllt. c=2
Everytime-New-Bin: Es wird immer ein neues Bin erstellt. nicht kompetitiv

Offline-Verfahren

Optimal: Die optimale Berechnung über alle Möglichkeiten.
First-Fit-Decreasing: First-Fit-Benutzung bei vorhergehender absteigender Sortierung.
Last-Fit-Decreasing: Last-Fit-Benutzung bei vorhergehender absteigender Sortierung.
Best-Fit-Decreasing: Best-Fit-Benutzung bei vorhergehender absteigender Sortierung.
Worst-Fit-Decreasing: Worst-Fit-Benutzung bei vorhergehender absteigender Sortierung.
Next-Fit-Decreasing: Next-Fit-Benutzung bei vorhergehender absteigender Sortierung.

Beispielfolgen

a) Beispielfolge zur Verdeutlichung der Online Algorithmen.
b) Beispielfolge um die nicht Optimalität der Decreasing-Offline Verfahren zu verdeutlichen.
c) d) e) f) (kurze / mittel lange /lange / sehr lange) Beispielfolge zur Darstellung von On/Opt >= 5/3 für First-Fit, Best-Fit, Allmost-Worst-Fit.
g) h) i) (kurze/lange/sehr lange) Beispielfolge zur Darstellung des kompetitiven Faktors 2 für Next-Fit, Worst-Fit, Last-Fit.

Autor: Sören Kühl