Geometry Lab [German] [Sitemap] [About geometrylab.de]

Visualization of Online Bin Packing

Bin Packing is the problem of packing requests in form of Weights, which comes one after one, in to bins. The maximal fillvalue of the bins is defined and the weight of the requests must be less than this value. Every request has to be packed immediately, before the weight of the next bin gets known. If there is no bin left with enough place for the incoming request, a new bin has to be created. The target is to have as less bins as possible.

Here we claim, that the bins are normalized, so that the weights of the requests are between 0 and 1.

General to Bin-Packing

The algorithms Last-Fit, Worst-Fit, Next-Fit have the competitive ratio 2. Better are the algorithms First-Fit, Best-Fit and Allmost-Worst-Fit, they have the competitive ratio 17/10. ( A proof can be found in "Online Computation and Competitive Analysis" from Allan Borodin and Ran El-Yaniv). The best lower Bound shown until now is 1,54. So for every algorithm exists at least one sequence of requests, that the ration of Onlinecost / Offlinecost goes against 1,54. The best shown upper bound is 1,5887. So it exists one Algorithm, that for every Sequence the ratio Onlinecost/Offlinecost is at the highest 1,5887.

Explanation of the Applet

At the upper area you will find the visualization.
The first rectangular visualizes the selected onlinealgorithm
The second rectangular shows the offline algorithm

At the lower area on the left is the output of the optimal cost, the online costs and the ratio of onlincecost/offlinecost. The value of the costs are the number of bins used from the algorithm. The ratio On/Opt is a value, which shows how good the onlinealgorithm was for the last requests, this ratio can not be greater than the competitive ratio of the onlinealgorithm used, of course.

]At the lower area on the right you will find the input.
Behind "Online-Verfahren" you can chose the preferred onlinealgorithm for the next request.:]
The box under this can be used to choose an offline algorithm.
The reset button resets the applet to its initial settings
Behind "Gewicht" you can do some input for the next weight of request. The value must be between 0 and 100, it is the percentage of the weight. For longer request sequences the values must be separated with space
Decimalnumbers have to be written with '.'
With the make-button the first weight of the request sequence will be processed. By pressing the MakeAll- button the whole request sequence will be processed. At last there is another box where you can chose some example sequences.

Warning: By Using optimal for the offline algorithm, the processing of the sequence can be very long. (Offline Bin Packing is NP-complete)

Applet showing the visualization of Bin Packing

Online Algorithms

Every Algorithm creates a new Bin, if the following action is not executeable
First-Fit: The first fillable Bin gets filled c=17/10
Last-Fit: The last fillable Bin gets filled c=2
Best-Fit: The fullest fillable Bin gets filled. c=17/10
Worst-Fit: The emptiest fillable Bin gets filled. c=2
Allmost-Worst-Fit: The second emptiest fillable Bin gets filled if it exist, otherwise the emptiest Bin gets filled. c=17/10
Next-Fit: The last Bin gets filled. c=2
Everytime-New-Bin: Everytime a new Bin will be created, not competitive.

Offline Algorithms

Optimal: The optimal calculation over all possibilities.
First-Fit-Decreasing: First-Fit with preceding decreasing sort.
Last-Fit-Decreasing: Last-Fit with preceding decreasing sort
Best-Fit-Decreasing: Best-Fit with preceding decreasing sort
Worst-Fit-Decreasing: Worst-Fit with preceding decreasing sort
Next-Fit-Decreasing: Next-Fit with preceding decreasing sort(short/long/very long) sequence to show the competitive ratio 2 of Next-Fit, Worst-Fit, Last-Fit.

Examplesequences

a) Example of the functionality of all algorithms.
b) Example to show that Decreasing-Offline ist not optimal
c) d) e) f) (short / medium long / long / very long) sequence to show On/Opg>=5/3 for First-Fit, Best-Fit, Allmost-Worst-Fit
g) h) i)


Developed by Sören Kühl for a practical exercise, summer term 2006

 

© University of Bonn, Computer Science I - - Last modified 21-07-2009 11:48