by Heidi Smith

Bin Packing Explained

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. A bin for example, need not necessarily be a container, but could represent a space in time or a surface area.

The One-Dimensional Bin Packing Problem

Mathematically, the one-dimensionalbin packing problem can be described as follows:

Given a bin capacity C>0 and a list of objects {p₁, p₂,...., p_n}, what is the smallest number of bins needed to accommodate all of the objects? ( Each p_i has size s_i, such that 0<=s_i<=C. i.e. none of the objects too big to fit in a bin)

Four easily recognisable one-dimensional bin packing problems are detailed below:

• A material such as piping or cable is supplied in quantities of a standard length C. The demands for pieces of the material are for varying lengths that do not exceed C. The idea is to use the least number of standard lengths of the material in producing a given set of required pieces. Hence minimising the wastage.
• Advertisments of arbitrary lengths, must be assigned to commersial break time slots on television. Each break must last no longer than three minutes.
• Removal lorries with set weight limits are to be packed with furniture. The aim is to use as few lorries as possible to pack all the items, without exceeding the maximum weight in any lorry.
• A set of tasks with known, arbitrary execution times, need to be executed on some identical processors by a given deadline. The problem is to schedule all of the tasks onto the least number of machines so that the deadline is met.

In the last example, it is time that is the critical resource. It is a scheduling problem; the processors are the bins, the deadline is the common bin capacity, and the individual execution times of the tasks are the objects (p_i) in the list.

The Two-Dimensional Bin Packing Problem

This problem is concerned with packing different sized objects (most commonly rectangles) into fixed sized, two-dimensional bins, using as few of the bins as possible. Applications of this type of problem are often found in stock cutting examples, where quantities of material such as glass or metal, are produced in standard sized, rectangular sheets. Demands for pieces of the material are for rectangles of arbitrary sizes, no bigger than the sheet itself. The problem is to use the minimum number of standard sized sheets in accommodating a given list of required pieces.

A variation on the two-dimensional bin packing problem is the strip packing problem and this is the area that I shall be concentrating on most.

The Strip Packing Problem

This is the problem of packing a set of n rectangles into an open-ended bin of fixed width C and infinite height. (the rectangles must not overlap each other) The idea is to pack the rectangles in a way that minimises the overall height of the bin. The clear difference between this problem and the two-dimensional bin packing problem, is that there is only one bin, so instead of trying to minimise the number of bins used, the aim is to minimise the height of the single bin. All the rectangles must be packed orthogonally. They cannot be rotated and they must be packed with their width parallel to the bottom of the bin.

In some versions of the strip packing problem, rotations through ninety degrees are allowed since there are some applications where it makes sense to be able to rotate the objects. There are also cases where the objects to be packed are not necessarily rectangular, but irregularly shaped objects instead. However, the strip packing algorithms which I shall be focussing on, do not take these extensions to the problem into consideration.

A necessity of the orthogonallity condition and also the use of rectangles can be seen in the following scheduling example for the memory resource problem in a multiprogrammed computer system: The rectangles correspond to a set of tasks, with their heights being the amount of processing time they require and their widths the amount of contiguous memory they need. The width of the bin corresponds to the amount of memory available and the height , in this example, is the amount of time required to process all of the tasks. The aim is to schedule all of the tasks so that they are completed in the least possible time, hence using the computers' memory most efficiently. In this example, it would make no sense to rotate a rectangle in any way since the dimensions of execution time and memory requirement, in general, do not directly effect each other.

Another common application of the strip packing problem is stock cutting. This can be seen in many industrial settings, where the material such as cloth, paper, Perspex or sheet metal, comes in rolls of a set width. These rolls may need to be cut into rectangles of arbitrary widths and heights. The goal is then to cut out all the required rectangles from the shortest length of roll possible, so minimising the wastage. In this example, the roll of material corresponds to the bin. It is not infinitely long, as specified in the original definition of the strip packing problem. However, I have discounted this discrepancy as I have assumed that the length of the roll (height of the bin) is considerably longer than its width. Again, the orthogonality condition can be justified since the material may have a bias that dictates the orientation of the rectangles and the cutting may be done by blades that are either parallel or at right-angles to the roll of material.

Back to main page