Bin Packing Algorithms (Edexcel International AS Maths: Decision 1)

• 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

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

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

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