Analysis of a Hybrid Algorithm for Packing Unequal Bins
Authors:
- 1 February 1988
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 17 (1) , 23-40
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}$.
Keywords
This publication has 5 references indexed in Scilit:
- Performance of Heuristics for a Computer Resource Allocation ProblemSIAM Journal on Algebraic Discrete Methods, 1984
- Bounds for Multifit Scheduling on Uniform ProcessorsSIAM Journal on Computing, 1983
- Combinatorial Analysis of an Efficient Algorithm for Processor and Storage AllocationSIAM Journal on Computing, 1979
- Bin packing: Maximizing the number of pieces packedActa Informatica, 1978
- Worst-Case Performance Bounds for Simple One-Dimensional Packing AlgorithmsSIAM Journal on Computing, 1974