Bin Packing Problem & Heuristics

Problem

Given items sizes $s_i ∈ (0,1]$ (bin capacity 1) or integer capacity $C$, pack into minimum number of bins. Decision version NP-complete (reduction from Partition), optimization NP-hard. No known polytime exact → heuristics & approximation.

Heuristics (online — items appear one by one)

First Fit (FF): For each item in given order, place in first bin where it fits (scanning bins in order); if none, open new bin.

• Time $O(n\log n)$ or O(n·#bins).
• Approximation: $FF ≤ 1.7·OPT +1$ (Johnson), uses at most $⌈1.7 OPT⌉$ bins.

Best Fit (BF): Place item in bin where it leaves smallest leftover space that still fits (tightest fit); if none, new bin.

• Also ~1.7 approx. Often better in practice than FF on average, but worst similar.
• Needs searching bins by leftover.

Next Fit (NF): Keep only current bin open; if item doesn't fit current, close it and open new bin (don't look back).

• Simplest $O(n)$, but worst $2·OPT -1$ (factor 2, worse than FF/BF). Example: items $0.5,0.5,0.5,0.5$ → NF uses 4 bins vs OPT2? Actually NF: bin1:0.5+0.5 fits →2 items per bin →2 bins optimal; worst case alternating 0.6,0.4 etc shows gap.

Sorted variants: First Fit Decreasing (FFD), Best Fit Decreasing (BFD) sort items descending first → improves to $11/9 OPT +1$ (~1.22) for FFD/BFD, best among simple heuristics.

Example $C=10$, items 6,6,5,5,4,4,4:

• NF: Bin1 6 → next6 no fit → Bin2 6, 5 no→Bin3 5,4 fits→5+4=9, next4 no→Bin4 4,4→8 → total4 bins
• FF: Bin1 6+4=10, Bin2 6+4=10, Bin3 5+5=10, Bin4 4→4 bins optimal =4
• BF similar 4.

Optimal is NP-hard; heuristics give fast near-optimal packing used in memory allocation, cutting stock, scheduling.