 |
|
|
|
|
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.
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.
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)
