Multidimensional Approximation Algorithms for Capacity-Expansion Problems

• 成果类型: Article
• 署名作者: Truong, Van-Anh; Roundy, Robin O.
• 署名单位: Columbia University; Cornell University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.1100.0892
• 发表日期: 2011
• 页码: 313-327
• 关键词: investment; replacement; SYSTEM; MODEL

摘要

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.