by Heidi Smith

Bin Packing

This web site was set up as part of my MSc Computing dissertation, 2001. The site explains the basic characteristics of the bin packing problem and provides visual demonstrations of some approximation algorithms that are used to solve it. In particular, it explores the issue of strip packing, which itself is a variation of bin packing.

Bin packing is a generic term describing a frequent daily exercise that takes place in factory outlets throughout the world. Most commonly it involves packing smaller items into defined spaces. However, it will be seen that the activity does in fact extend well beyond this.

The fundamental aim of bin packing is to pack a collection of objects into well defined regions called bins, so that they do not overlap. In the real world, the critical issue is to make efficient use of time and/or space.

Some areas where the bin packing problem can occur are in stock cutting, scheduling tasks, layouts on computer chips, packing goods into crates, assigning commercials to station breaks on television, loading trucks with a given size or weight limit and storage problems. The list is endless and extremely diverse.

Level Algorithms: Next-Fit Decreasing Height and First-Fit Decreasing Height

Shelf Algorithms: Next-Fit Shelf and First-Fit Shelf