Multidimensional Approximation Algorithms for Capacity-Expansion Problems

Truong Van-Anh () and Robin O. Roundy ()
Additional contact information
Truong Van-Anh: Department of Industrial Engineering and Operations Research, Columbia University, New York, New York 10027
Robin O. Roundy: School of Operations Research and Information Engineering, Cornell University, Ithaca, New York

Operations Research, 2011, vol. 59, issue 2, 313-327

Abstract: We develop multidimensional balancing algorithms to compute provably near-optimal capacity-expansion policies. Our approach is computationally efficient and guaranteed to produce a policy with total expected cost of no more than twice that of an optimal policy. We overcome the curse of dimensionality by introducing novel cost-separation schemes to separate the lost-sales cost of the system into exact monotonic subparts. This is the first approximation technique for multimachine, multiproduct systems facing stochastic, nonstationary, and correlated demands. To show the generality of this separation technique, we apply it to the capacity-expansion problem under two different production planning models: monotone production and revenue-maximizing production. We make the assumptions of minimal inventory and lost sales.

Keywords: analysis of algorithms; facilities/equipment planning; capacity expansion; dynamic programming; applications (search for similar items in EconPapers)
Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1100.0892 (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:59:y:2011:i:2:p:313-327

Access Statistics for this article

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