Bin Packing Algorithms (Edexcel A Level Further Maths: Decision Maths 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
    • with the aim of minimising the number of lorries required
  • cutting short strips of cable (objects) from large reels of cable (bins)
    • with the aim of minimising wastage at the end of a reel
• There are two bin packing algorithms covered
  • the first-fit bin packing algorithm
  • the first-fit decreasing bin packing algorithm
  • Both are heuristic algorithms - they will provide a (good) solution
    • but not necessarily an optimal solution
    • and not necessarily the only 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 (listed)
  • e.g.  organising scattered boxes in the order they are encountered instead of organising them first

• The algorithm finds the number of bins required to pack all the objects
  • ideally this would be the minimum number of bins required
  • but 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 of more importance 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 any existing bin does not have enough capacity remaining, a new bin will be required
  • 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
  • even if the calculation gave the value 3.01, say, more than 3 bins would be required, and so the lower bound will be 4
  • i.e.  always round up (unless the value happens to be an exact integer)
• Note that this is exactly the same as for the 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.  arranging scattered boxes in order of size/weight first, then organising them, in descending order, 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
  • but 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 would be 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
  • even if the calculation gave the value 3.01, say, more than 3 bins would be required, and so the lower bound will be 4
  • i.e.  always round up (unless the value happens to be an exact integer)
• Note that this is exactly the same as for the first-fit bin packing algorithm