by Heidi Smith
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.
- To find out more about bin packing click here (explanations of one and two-dimensional bin packing problems and strip packing)
- To find out about the different approaches used to solve the strip packing problem, click here
- To read about some strip packing algorithms in detail and view demonstrations of how they work, click here
- Demonstrations:
Level Algorithms: Next-Fit Decreasing Height and First-Fit Decreasing Height
Shelf Algorithms: Next-Fit Shelf and First-Fit Shelf