Optimal Design of Process Flexibility for General Production Systems

• 成果类型: Article
• 署名作者: Chen, Xi; Ma, Tengyu; Zhang, Jiawei; Zhou, Yuan
• 署名单位: New York University; Facebook Inc; New York University; New York University; NYU Shanghai; Indiana University System; Indiana University Bloomington; University of Illinois System; University of Illinois Urbana-Champaign
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2018.1780
• 发表日期: 2019
• 页码: 516-531
• 关键词: long-chain; performance; expander

摘要

Process flexibility is widely adopted as an effective strategy for responding to uncertain demand. Many algorithms for constructing sparse flexibility designs with good theoretical guarantees have been developed for balanced and symmetrical production systems. These systems assume that the number of plants equals the number of products, that supplies have the same capacity, and that demands are independently and identically distributed. In this paper we relax these assumptions and consider a general class of production systems. We construct a simple flexibility design to fulfill (1 - epsilon)-fraction of expected demand with high probability where the average degree is O(ln(1/epsilon)). To motivate our construction, we first consider a natural weighted probabilistic construction from the existing literature where the degree of each node is proportional to its expected capacity. However, this strategy is shown to be suboptimal. To obtain an optimal construction, we develop a simple yet effective thresholding scheme. The analysis of our approach extends the classic analysis of expander graphs by overcoming several technical difficulties. Our approach may prove useful in other applications that require expansion properties of graphs with nonuniform degree sequences.