Analysis of a Hybrid Algorithm for Packing Unequal Bins

Authors:

Abstract
We consider a bin-packing problem where the sizes of the bins are allowed to vary and where the goal is to maximize the number of pieces packed. This problem is NP-hard. We examine a new efficient approximation algorithm which is a hybrid of two algorithms reported earlier, First-Fit Decreasing (FFD) and Best-Two Fit (B2F). The hybrid is iterative: it attempts to pack smaller and smaller suffixes of its list of pieces until it succeeds in packing an entire suffix. During each attempt, the hybrid operates by partitioning the current list of pieces and packing one part by B2F and afterward packing the other part of its list by FFD. We prove that no instance of the problem exists where an optimal algorithm can pack more than $\tfrac{4}{3}$ the number of pieces the hybrid can pack. We also give a sequence of examples for which the ratio of the number of pieces packed optimally and by our algorithm increases asymptotically to $\frac{4}{3}$.