FirstFit versus WorstFit for Dual Bin Packing on Uniformly Distributed Data

This file and all files listed below in one zip-file.

Introduction

This directory contains a Python program written for a Linux platform using Gnuplot for graphical summary of experimental results (Python version 2.4.3, Gnuplot version 4.0). The program needs write permission in the current directory. The program should be very easy to adapt to other versions and platforms. Notice, however, that Gnuplot produces postscript.

For the on-line dual bin packing problem, we test the relative behavior of FirstFit compared with WorstFit. The algorithms represent different strategies for packing items of real sizes up to one into bins of size one, aiming at packing (accepting) as many items as possible in a fixed number of bins, given from the beginning. When processing an item, WorstFit places it in a least full bin if there is enough space. If there is not enough space in any bin, it must reject the item. FirstFit considers the given bins in a fixed order. When processing an item, it places it in the first bin where there is enough space. If there is not enough space in any bin, it must reject the item.

We test the algorithms on sequences of uniformly distributed data over (0,1], as approximated using Python's built-in random number generator. For dual bin packing it is harder to design a canonical test than it is for classic bin packing. In dual bin packing, we must choose a fixed number of bins and also a sequence. If the sequence is too short, all algorithms will do well because all or nearly all items will fit. If the sequence is too long, there will eventually be enough small items that both algorithms will accept a lot of items independent of initial decisions. Thus, to distinguish algorithms, we must make it likely that a fair number of items can be rejected without an unreasonably large number of items, compared to the number of bins, being offered.

Our attempt at a canonical decision is to first choose a number of bins, and then generate items uniformly at random until the first point where the sum of all generated items (also referred to as the volume of the items) is at least the number of bins.

For each maximal number of bins, we check 20 equidistant measuring points of actual number of bins. For each measuring point, we generate 10 random sequences of that volume and compute the average performance. More specifically, for each random sequence s, we determine the number of items accepted by FirstFit, denoted FirstFit(s), and we determine the number of items accepted by WorstFit on the same sequence, denoted WorstFit(s). From this we compute the ratio FirstFit(s)/WorstFit(s). Thus, 10 random sequences give us 10 ratios and we compute the average of these.

The program has different plotting possibilities. In the plots in this directory, we show all 10 results for each measuring point (some may coincide), as well as the graph connecting all of the averages that are computed for different measuring points.

From the plotting, it appears that averaging over 10 sequences is reasonable. However, this has also been investigated separately. The program contains routines for varying the number of samples used while using a fixed maximal sequence length to see when results converge. The results clearly indicate that a sample size of 10 is sufficient.

The on-line algorithms FirstFit and WorstFit for Dual Bin Packing can be found in

The Accommodating Function: a generalization of the competitive ratio.
Joan Boyar, Kim S. Larsen, and Morten N. Nielsen.
SIAM Journal on Computing, 31(1): 233-258, 2001.

Program files

  1. FFversusWF.py
  2. PriorityQueue.py
  3. gnuplotFrame.gp
  4. gnuplotFrame2.gp

Test Results

  1. Maximal sequence length 100
  2. Maximal sequence length 1000
  3. Maximal sequence length 10000
  4. Maximal sequence length 100000

Conclusions

Many conclusions can be drawn. Here, we just emphasize that the ratio of FirstFit's performance to WorstFit's performance shows very little variation except for very short sequences. The ratio seems to be increasing very slowly with the number of bins. It is approximately 1.174 at our largest measuring point of 100,000 bins.


Last modified: Wed Feb 28 13:40:55 CET 2007
Kim Skak Larsen (kslarsen@imada.sdu.dk)