Distributionally Robust Optimization of Two-Stage Lot-Sizing Problems

• 成果类型: Article
• 署名作者: Zhang, Yuli; Shen, Zuo-Jun Max; Song, Shiji
• 署名单位: Tsinghua University; University of California System; University of California Berkeley; University of California System; University of California Berkeley; Tsinghua University
• 刊物名称: PRODUCTION AND OPERATIONS MANAGEMENT
• ISSN/ISSBN: 1059-1478
• DOI: 10.1111/poms.12602
• 发表日期: 2016
• 页码: 2116-2131
• 关键词: polynomial-time algorithms; shortest-path problem; lost sales; bounded inventory; size model; uncertainty; Stockouts

摘要

This paper studies two-stage lot-sizing problems with uncertain demand, where lost sales, backlogging and no backlogging are all considered. To handle the ambiguity in the probability distribution of demand, distributionally robust models are established only based on mean-covariance information about the distribution. Based on shortest path reformulations of lot-sizing problems, we prove that robust solutions can be obtained by solving mixed 0-1 conic quadratic programs (CQPs) with mean-risk objective functions. An exact parametric optimization method is proposed by further reformulating the mixed 0-1 CQPs as single-parameter quadratic shortest path problems. Rather than enumerating all potential values of the parameter, which may be the super-polynomial in the number of decision variables, we propose a branch-and-bound-based interval search method to find the optimal parameter value. Polynomial time algorithms for parametric subproblems with both uncorrelated and partially correlated demand distributions are proposed. Computational results show that the proposed models greatly reduce the system cost variation at the cost of a relative smaller increase in expected system cost, and the proposed parametric optimization method is much more efficient than the CPLEX solver.