Selected topics in finite mathematics/Bin Packing

Bin packing in this course refers to the following problem: given a list of weights and bins all with the same capacity, how many bins are needed to pack all of the objects into the bins?

Objectives

• Learn techniques to solve the bin-packing problem: place all of the objects in bins and use the least number of bins.

Details

Bin Packing refers to finding the minimum number of bins required to place a sequence of objects. Each bin will be the same size, but the objects placed in them can vary in size. Commonly the of the objects is referred to as weight. Two algorithms that attempt to answer this question are:

First-Fit - packing bins by placing an object from a sequence into the first bin it will fit into

First-Fit Decreasing - reorganizing the sequence of objects (from largest to smallest), and then placing each object in the first bin it will fit into

Note that these algorithms may not use the fewest number of bins, that is, they're examples of heuristic algorithms.

Examples

Suppose that objects of the following weights must be placed into bins that can hold 50 units: 10, 12, 14, 15, 15, 15, 20, 20, 25, 25, 30, 35, 45. Then one valid packing is:

Bin 1: 10, 12, 14

Bin 2: 15, 15

Bin 3: 15, 20

Bin 4: 25, 25

Bin 5: 30

Bin 6: 35

Bin 7: 45

Homework

1. Using the First-Fit algorithm, pack the following weights into bins of size 100: 20, 30, 40, 20, 50, 60, 40, 30, 60, 70, 80, 90, 100, 60, 70, 60.
2. Using the First-Fit Decreasing algorithm, pack the following weights into bins of size 100: 20, 30, 40, 20, 50, 60, 40, 30, 60, 70, 80, 90, 100, 60, 70, 60.
3. Is the First-Fit algorithm guaranteed to use as few bins as possible? Why or why not?
4. Is the First-Fit Decreasing algorithm guaranteed to use as few bins as possible? Why or why not?

Homework Solutions

3. It is not guaranteed to use the minimal amount of bins because although some items would fit better in specific boxes, and more items later on in the sequence may be able to fit, in first fit, it is imperative that you use the first fitting item in the sequence and do not go over the given set-point.