Scheduling: Bin Packing

Example

A lumber yard sells wooden boards in 12 foot lengths. To build a shelf system for your garage, you need wood in the following lengths:
8, 8, 5, 3, 5, 5, 5, 6, 6, 8, 8, 4, 4, 2.

Find out how many boards you need to buy from the lumber yard using the Next Fit Algorithm, the Next Fit Decreasing Algorithm, and the Worst Fit Decreasing Algorithm.

Next Fit

Here is how you would cut the desired lengths from 12 foot boards using Next Fit algorithm. You would need to buy 9 12 foot boards.

Next Fit Decreasing

Reorder the list of lengths needed: 8, 8, 8, 8, 6, 6, 5, 5, 5, 5, 4, 4, 3, 2.

Here is how you would cut the desired lengths from 12 foot boards using Next Fit Decreasing algorithm. You would need to buy 9 12 foot boards.

Worst Fit Decreasing

Reorder the list of lengths needed: 8, 8, 8, 8, 6, 6, 5, 5, 5, 5, 4, 4, 3, 2.

Here is how you would cut the desired lengths from 12 foot boards using Worst Fit Decreasing algorithm. You would need to buy 7 12 foot boards.

If you know all the objects you want to put in the bins before you start, then one of the decreasing algorithms is usually best. Also, for small situations, leaving the bins open is not computationally expensive, so a first fit or worst fit algorithm is a better choice than the next fit algorithm.

The bottom line is, if you can plan ahead you can improve efficiency!

Example

If in the example above, the lumber yard also offered 15 foot boards for sale, and both 12 and 15 foot boards cost $3.25/foot, use the Worst Fit Decreasing algorithm to help you decide if you should buy 12 or 15 foot boards.

Worst Fit Decreasing

In the previous example, we saw that we required 7 of the 12 foot boards to make our shelves. At $3.25/foot, this means we would spend $3.25/foot x 7 x 12 = $273 on the lumber.

Now, let's figure out how many boards we need if we use boards of length 15 feet.

Reorder the list of lengths needed: 8, 8, 8, 8, 6, 6, 5, 5, 5, 5, 4, 4, 3, 2.

Here is how you would cut the desired lengths from 15 foot boards using Worst Fit Decreasing algorithm.

Here, we see that we required 6 of the 15 foot boards to make our shelves. At $3.25/foot, this means we would spend $3.25/foot x 6 x 15 = $292.50 on the lumber.

We should buy the 12 foot lumber to reduce our costs.