The Full Bin Packing Algorithm

The full bin packing algorithm is more likely to produce an optimal solution – using the least possible number of bins – than the first fit decreasing and first fit algorithms. It works by matching object so as to fill as many bins as possible.

Suppose boxes of heights 0.2, 1.4, 0.4, 0.8, 1.1, 1.0, 0.9, 0.7 and 1.3 m are to be packed into bin of height 2.5 m.

The boxes of height 0.2, 1.4 and 0.9 fill one bin.

The boxes of height 0.4, 0.8 and 1.3 fill one bin.

The boxes of height 1.1, 1.0 and 0.7 m remain. The total of these heights is 2.8 and there is no way to match up any two of them to fill a third bin. We can put any two of them in a thid bin, and the last one must go into a bin of its own.

Four bins are used to store the boxes. It is quite easy to see that at least four bins must be used since the total of the heights of the boxes is 0.2+1.4+0.4+0.8+1.1+1.0+0.9+0.7+1.3=7.8.

To find the least number of bins, 7.8 over 2.5 = 3.12 must be rounded up to the next whole number. This gives 4 bins.

Add comment

Security code