PROBABILISTIC ANALYSIS OF A GENERALIZED BIN PACKING PROBLEM AND APPLICATIONS

We give a unified probabilistic analysis for a general class of bin pa cking problems by directly analyzing corresponding mathematical progra ms. In this general class of packing problems, objects are described b y a given number of attribute values. (Some attributes may be discrete ; others may be continuous.) Bins are sets of objects, and the collect ion of feasible bins is merely required to satisfy some general consis tency properties. We characterize the asymptotic optimal value as the value of an easily specified linear program whose size is independent of the number of objects to be packed. or as the limit of a sequence o f such linear program values. We also provide bounds for the rate of c onvergence of the average cost to its asymptotic value. The analysis s uggests an (a.s.) asymptotically E-optimal heuristic that runs in line ar time. The heuristics can be designed to he asymptotically optimal w hile still running in polynomial time. We also show that in several im portant cases, the algorithm has both polynomially fast convergence an d polynomial running time. This heuristic consists of solving a linear program and rounding its solution up to the nearest integer vector. W e show how our results can be used to analyze a general vehicle routin g model with capacity and time window constraints.