Bin Packing Algorithms (Edexcel International A Level Maths): Revision Note

Introduction to Bin Packing Algorithms

• Bin packing algorithms organise objects into as few containers as possible

• The containers are called bins

  • In problems all bins will be of equal size

    • Size may refer to length, width, capacity (volume), weight, etc.

• 'Packing' is a loose term that could mean 'separating', 'cutting' or similar

• Examples of bin packing problems include:

  • Loading pallets (objects) of varying weights into lorries (bins) without exceeding their weight capacity

    • The aim is to minimise the number of lorries required

  • Cutting short strips of cable (objects) from large reels of cable (bins)

    • The aim is to minimise wastage at the end of a reel

• There are three bin packing algorithms covered

  • The first-fit bin packing algorithm

  • The first-fit decreasing bin packing algorithm

  • The full-bin packing algorithm

  • All are heuristic algorithms - they will provide a (good) solution

    • but not necessarily an optimal solution

    • and not necessarily the only (good) solution

First-Fit Bin Packing Algorithm

What is the first-fit bin packing algorithm?

• The first-fit bin packing algorithm packs objects into bins in the order in which they are presented

  • E.g.  Scattered boxes are organised in the order they are encountered

  • They are not organised beforehand

• The algorithm finds the number of bins required to pack all the objects

  • Ideally this would be the minimum number of bins required

  • However, the algorithm will not necessarily provide the optimal solution

• An advantage of using the first-fit bin packing algorithm is speed

  • The objects do not have to be sorted (into size or any other criteria) first

  • In many cases, the solution obtained, will be sufficient for business or practical purposes

    • I.e.  speed (efficiency) is more important than optimisation

How do I apply the first-fit bin packing algorithm?

• Each object, in turn, is placed in the first available bin that has enough capacity (room) for it

  • Object 1 (the first on the list) will be placed into bin 1

    • If bin 1 then has enough spare capacity, object 2 (the second on the list) will also go into bin 1

    • If not, object 2 will need a new bin, bin 2

    • Object 3 would be considered for bin 1 first, then bin 2, and failing both, it would require a new bin, bin 3

• For each object, if an existing bin does not have enough capacity remaining, a new bin will be used

  • For example,

    • If a bin has capacity 10 and the first two objects are of capacity 6 and 3, the 6 will go into bin 1, then the 3 will go into bin 1 too
      (6 + 3 = 9 ≤ 10)

    • If the first two objects are of capacity 5 and 9, the 5 would go in bin 1, then the 9 would go into bin 2
      (5 + 9 = 14 > 10)

• The algorithm is complete when all objects have been placed in a bin

How do I find the lower bound for the number of bins?

• The lower bound (LB) for the number of bins required in the first-fit bin packing problem is the smallest integer that satisfies

• As it is a number of bins, the lower bound will be an integer

  • The calculation should always be rounded up to the nearest integer

  • E.g. For a value of 3.01, more than 3 bins would be required and so the lower bound will be 4

• Note that this is exactly the same lower bound as for the first-fit decreasing and the full-bin packing algorithms

First-Fit Decreasing Bin Packing Algorithm

What is the first-fit decreasing bin packing algorithm?

• The first-fit decreasing bin packing algorithm packs objects into bins once they have been arranged into decreasing (descending) order

  • E.g. Scattered boxes are arranged in descending order of size/weight, starting with the biggest/heaviest

• The algorithm finds the number of bins required to pack all the objects

  • Ideally this would be the minimum number of bins required

  • However, the algorithm will not necessarily provide the optimal solution

• An advantage of using the first-fit decreasing bin packing algorithm is that it usually gets close to the optimal solution

  • This is good for situations where minimising the number of bins is more desirable than speed
    

How do I apply the first-fit decreasing bin packing algorithm?

• Each object, in turn, is placed in the first available bin that has enough capacity (room) for it

  • Object 1 (the biggest) will be placed into bin 1

    • If bin 1 then has enough spare capacity, object 2 (the second biggest) will also go into bin 1

    • If not, object 2 will need a new bin, bin 2

    • Object 3 would be considered for bin 1 first, then bin 2, and failing both, it would require a new bin, bin 3

  • For each object, if any existing bin does not have enough capacity remaining, a new bin will be required

  • For example,

    • If a bin has capacity 15 and the first two objects are of capacity 13 and 10, the 13 will go into bin 1, then the 10 will go into bin 2
      (as 13 + 10 = 23 > 15)

    • If the first two objects are of capacity 8 and 6, the 8 would go in bin 1, then the 6 would go into bin 1 too
      (as 8 + 6 = 14 ≤ 15)

• The algorithm is complete when all objects have been placed in a bin

How do I find the lower bound for the number of bins?

• The lower bound (LB) for the number of bins required in the first-fit decreasing bin packing problem is the smallest integer that satisfies

• As it is a number of bins, the lower bound will be an integer

  • The calculation should always be rounded up to the nearest integer

  • E.g. For a value 3.01, more than 3 bins would be required and so the lower bound will be 4

• Note that this is exactly the same lower bound as for the first-fit and full-bin packing algorithms

Full-Bin Packing Algorithm

What is the full-bin packing algorithm?

• The full-bin packing algorithm identifies combinations of objects that will fill a bin

  • Any objects that cannot be grouped to fill a bin will be packed using the first-fit bin packing algorithm

• This algorithm finds the number of bins required to pack all the objects

  • Ideally this would be the minimum number of bins required

• An advantage of the full-bin packing algorithm is that it generates a good solution

  • It will often produce the optimal solution

• Full-bin combinations are identified by inspection

  • This can be time-consuming for a situation with many objects 

  • It is not suitable for situations where speed is important

How do I apply the full-bin packing algorithm?

• The list of objects is inspected to identify combinations of objects that fill a bin

  • As many combinations of full-bins as possible from the original list should be identified and placed into bins
    

    • E.g. For the list of objects: 2, 6, 4, 9, 8, 8, 2, 5, 2 and a bin capacity of 10

    • A possible set of full-bin combinations is: 2 + 8, 6 + 4, 8 + 2

    • The remaining objects are 9, 5 and 2

  • Any remaining objects should be placed into bins using the first-fit bin packing algorithm

    • E.g. for the remaining objects above

    • 9 will be place in the next available bin

    • 5 and 2 will be placed in an additional bin 

• The algorithm is complete when all objects have been placed in a bin

How do I find the lower bound for the number of bins?

• The lower bound (LB) for the number of bins required in the full-bin packing problem is the smallest integer that satisfies

• As it is a number of bins, the lower bound will be an integer

  • The calculation should always be rounded up to the nearest integer

  • E.g. For a value 3.01, more than 3 bins would be required and so the lower bound will be 4

• Note that this is exactly the same lower bound as for the first-fit and the first-fit decreasing bin packing algorithms