Bin Packing

One-dimensional bin packing is a classic problem with many practical applications related to minimization of space or time. It is a hard problem for which many different heuristic solutions have been proposed. The goal is to pack a collection of objects into the minimum number of fixed-size "bins".

The bpack.icn program illustrates the behavior of six different packing algorithms. It is a streamlined version of the older binpack program from the Icon program library.

The Program

Two shelves of objects appear in the program display. The top shelf shows the candidate objects to be packed. The bottom shelf shows the results of packing. Objects larger than half a bin are colored orange; smaller objects are blue.

The File menu offers three choices:

• About summarizes the available packing algorithms
• New creates a new, random set of objects for packing
• Quit exits the program

The Reorder menu rearranges the candidate objects on the top shelf. The Pack menu selects an algorithm and packs the objects onto the bottom shelf using the selected algorithm. These operations are illustrated in the following sections.

The Reorder Menu

	The Random entry reorders the candidate objects randomly.
	The Regular entry maximizes the distances between similarly-sized objects, producing the pattern seen here.
	The Ascending entry orders the objects from smallest to largest. This display also illustrates the color scheme.
	The Descending entry orders the objects from largest to smallest. Packing is usually improved by starting with the largest objects first.

The Pack Menu

The entries in the Pack menu take the objects from the top shelf and pack them into the bottom shelf using different algorithms. The resulting display notes the packing algorithm used by its initials, and also indicates the number of bins required.

All algorithms take the objects from the top shelf in order and place them one at a time. A new bin is created whenever the algorithm cannot use an existing bin.

	This initial set of candidate objects is used for the illustrations that follow.
	The First Fit algorithm places a new object in the leftmost bin that still has room.
	The Last Fit algorithm places a new object in the rightmost bin that still has room.
	The Next Fit algorithm places a new object in the rightmost bin, starting a new bin if necessary.
	The Best Fit algorithm places a new object in the fullest bin that still has room.
	The Worst Fit algorithm places a new object in the emptiest existing bin.
	The Almost Worst Fit algorithm places a new object in the second-emptiest bin. (This algorithm is provably better than Worst Fit and so it is of some theoretical interest.)

Sorted Packing

Further Reading

E.G. Coffman, Jr., M.R. Garey, and D.S. Johnson. Approximation Algorithms for Bin-Packing -- An Updated Survey. In Algorithm Design for Computer System Design, ed. by Ausiello, Lucertini, and Serafini. Springer-Verlag, 1984.

David S. Johnson. Fast Algorithms for Bin Packing. Journal of Computer and System Sciences 8, 272-314 (1974).