• PDF / 3,188,605 Bytes
• 26 Pages / 481.89 x 691.654 pts Page_size
• 14 Downloads / 228 Views

DOWNLOAD

REPORT

---

M. R. Garey and D. S. Johnson BeU Laboratories Murray HiU, New Jersey 07fJ74

Abstract. Bin packing problems, in which one is asked to pack items of various sizes into bins so as to optimize some given objective function, arise in a wide variety of contexts and have been studied extensively during the past ten years, primarily with the goal of finding fast "approximation algorithms" that construct near-optimal packings. Beginning with the classical one-dimensional bin packing problem first studied in the early 1970's, we survey the approximation results that have been obtained for this problem and its many variants and generalizations. including recent (unpublished) work that reflects the cu"ently most active areas of bin packing research. Our emphasis is on the worst-case performance guarantees that have been proved, but we also discuss work that has· been done on expected performance and behavior "in practice," as well as mentioning some of the many applications of these problems. 1. Introduction Bin packing is a problem that has shown up under many guises, but to the authors of this survey, it is mainly known as "The Problem That Wouldn't Go Away." Every year or so we finish a paper on the subject, heave a sigh of relief, and remark that at long last we can wash our hands of bin packing. But, inevitably, some member of an ever-growing band of researchers on the topic comes up with yet another variant on the model, a new question to ask, or even (heaven forbid) a new application, and we find ourselves charging back into the fray for "just one last time." We have been back and forth over the territory so often now that it seems appropriate for us to prepare a new map. (Some earlier maps can be found in [25,33,34,35]). We hope this survey wiU be of use in pulling together many of the disparate strands that have (often in disguised fonn) made up the fabric of bin packing research to date.

G. Ausiello et al. (eds.), Analysis and Design of Algorithms in Combinatorial Optimization © Springer-Verlag Wien 1981

M.R Garey, D.S J~hnson

148 - - - - - - - - - - - - - - - - - - - - ·----·

The classical one~dimensional bin packing r~oblem can be stated as follows: Suppose we are given a positive integer bin capacity C and a :;et or list of items L=(p 17p2 , • · • ,p~), each item IJi having an integer size s(p;) :;arir;:ying C~s~i)~O. What is the smallest integer m St;Ch that there is a partition L~B1UB2U · · · UEm sz.~~Ting 1r,EIJ/~;):$C, l:S;j:S;m? w~ usually thi:..k of each set Bi as bing the contetJts of a bin of capacity B, :md view ourselPs as attempting to minimize the n•·1.1bt;r cf bins needed for a p~ckin~ of L. This abstr~ct problem ca..• be used to model a variety oi: problems in the real world, from packing trucks having a given weight limit to assigning commercials to station break..; on television [7). One commonly cited example is the plumber's pipe-cutting problem: A plumber needs a collection of pipes of lengths s(p 1), s(p 2), ... , s(pn), which she can obtair. by cutting up standard 8-foot lengths (C=8) t