Optimal Sparse Designs for Process Flexibility via Probabilistic Expanders

• 成果类型: Article
• 署名作者: Chen, Xi; Zhang, Jiawei; Zhou, Yuan
• 署名单位: New York University; New York University; New York University; NYU Shanghai; Massachusetts Institute of Technology (MIT)
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2015.1416
• 发表日期: 2015
• 页码: 1159-1176
• 关键词: long-chain; performance; networks; benefits

摘要

We study the problem of how to design a sparse flexible process structure in a balanced and symmetrical production system to match supply with random demand more effectively. Our goal is to provide a sparsest design to achieve (1 - epsilon)-optimality relative to the fully flexible system. In a balanced system with n plants and n products, Chou et al. (2011) proved that there exists a graph expander with Omicron(n/epsilon) arcs to achieve (1 - epsilon)-optimality for every demand realization. Wang and Zhang (2015) showed that the simple k-chain design with Omicron(n/epsilon) arcs can achieve (1 - epsilon)-optimality in expectation. In this paper, we introduce a new concept called probabilistic graph expanders. We prove that a probabilistic expander with O(n ln (1/epsilon) ) arcs guarantees (1 - epsilon) -optimality with high probability (w.h.p.), which is a stronger notion of optimality as compared to the expected performance. Easy-to-implement randomized and deterministic constructions of probabilistic expanders are provided. We show our bound is best possible in the sense that any structure should need at least Omega(n ln (1/epsilon)) arcs to achieve (1 - epsilon)-optimality in expectation (and hence w.h.p.). We also show that in order to achieve (1 - epsilon)-optimality in the worst case, any design would need at least Omega(n/epsilon) arcs; and in order to achieve (1 - epsilon)-optimality in expectation, k-chain needs at least Omega(n/epsilon) arcs.