Probabilistic Analysis of a Generalized Bin Packing Problem and Applications

Awi Federgruen and Garrett van Ryzin
Additional contact information
Awi Federgruen: Columbia University, New York, New York
Garrett van Ryzin: Columbia University, New York, New York

Operations Research, 1997, vol. 45, issue 4, 596-609

Abstract: We give a unified probabilistic analysis for a general class of bin packing problems by directly analyzing corresponding mathematical programs. In this general class of packing problems, objects are described by a given number of attribute values. (Some attributes may be discrete; others may be continuous.) Bins are sets of objects, and the collection of feasible bins is merely required to satisfy some general consistency 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 of such linear program values. We also provide bounds for the rate of convergence of the average cost to its asymptotic value. The analysis suggests an (a.s.) asymptotically ϵ-optimal heuristic that runs in linear time. The heuristics can be designed to be asymptotically optimal while still running in polynomial time. We also show that in several important cases, the algorithm has both polynomially fast convergence and polynomial running time. This heuristic consists of solving a linear program and rounding its solution up to the nearest integer vector. We show how our results can be used to analyze a general vehicle routing model with capacity and time window constraints.

Keywords: analysis of algorithms; probabilistic; transportation; vehicle routing; production/scheduling; bin packing/cutting stock (search for similar items in EconPapers)
Date: 1997
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.45.4.596 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:45:y:1997:i:4:p:596-609

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().