A Primal-Dual Approach to Analyzing ATO Systems

• 成果类型: Article
• 署名作者: DeValve, Levi; Pekec, Sasa; Wei, Yehua
• 署名单位: University of Chicago; Duke University
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.2019.3486
• 发表日期: 2020
• 页码: 5389-5407
• 关键词: primal-dual analysis; assemble-to-order system; approximations-heuristics

摘要

We study assemble-to-order (ATO) problems from the literature. ATO problems with general structure and integrality constraints are well known to be difficult to solve, and we provide new insight into these issues by establishing worst-case approximation guarantees through primal-dual analyses and linear programming (LP) rounding. First, we relax the one-period ATO problem using a natural newsvendor decomposition and use the dual solution for the relaxation to derive a lower bound on optimal cost, providing a tight approximation guarantee that grows with the maximum product size in the system. Then, we present an LP rounding algorithm that achieves both asymptotic optimality as demand grows large, and a 1.8 approximation factor for any problem instance. In addition to theoretical guarantees, we perform comprehensive numerical simulations and find that our rounding algorithm outperforms existing techniques and is close to optimal. Finally, we demonstrate that our one-period LP rounding results can be used to develop an asymptotically optimal integral policy for dynamic ATO problems with backlogging and identical component lead-times.