WorstFit versus NextFit for Classic 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 classic bin packing problem, we test the relative behavior of WorstFit compared with NextFit. The algorithms represent different strategies for packing items of real sizes up to one into bins of size one, aiming at using as few bins as possible. When processing an item, WorstFit places it in a least full open bin if there is enough space. If there is not enough space in any open bin, it opens a new bin and places it there. NextFit uses a so-called current bin. When processing an item, it places it in the current bin if there is enough space. If there is not enough space in any open bin, it opens a new bin, which will then be the current bin, and places the item there. Previous bins are considered closed and are never considered again.

We test the algorithms on sequences of uniformly distributed data over (0,1], as approximated using Python's built-in random number generator. For each maximal input sequence length, we check 20 equidistant measuring points of actual input sequence length. For each measuring point, we generate 10 random sequences of that length and compute the average performance. More specifically, for each random sequence s, we determine the number of bins used by WorstFit, denoted WorstFit(s), and we determine the number of bins used by NextFit on the same sequence, denoted NextFit(s). From this we compute the ratio WorstFit(s)/NextFit(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 WorstFit and NextFit can be found in

Approximation Algorithms for NP-Hard Problems.
Dorit Hochbaum, editor.
PWS Publishing Company, 1997.

Program files

  1. WFversusNF.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 WorstFit's performance to NextFit's performance shows very little variation except for very short sequences. The ratio seems to tend towards approximately 1.138.

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