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
• The full-bin algorithm is also covered

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 for all bin-packing algorithms

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

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

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