Analysis of a hybrid algorithm for packing unequal bins

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 for its solution 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 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 optimally and by our algorithm increases asymptotically to 4/3. The hybrid, B2F and FFD were programmed and sets of instances were generated randomly for various distributions of piece and bin sizes. The estimates of expected behavior computed by applying the algorithms to these instances are only a few percent from optimality, which suggests that the worst-case behavior of the hybrid is evoked only by comparatively rare instances. In all the kinds of problems examined, our hybrid and the unelaborated B2F were superior to the simpler FFD.