Sparse Process Flexibility Designs: Is the Long Chain Really Optimal?
研究了在最多2n条边的供需网络中，长链设计是否总是最优。发现存在特定需求分布下，断开网络反而优于长链，但长链在可交换分布下对连通设计是最优的。
Sparse process flexibility and the long chain have become important concepts in design flexible manufacturing systems. In this paper, we study the performance of the long chain in comparison to all designs with at most 2n edges over n supply and n demand nodes. We show that, surprisingly, long chain is not always optimal in this class of networks even for i.i.d. demand distributions. In particular, we present a family of instances where a disconnected network with 2n edges has a strictly better performance than the long chain under a specific class of i.i.d. demand distributions. This is quite surprising and contrary to the intuition that a connected design performs better than a disconnected one under exchangeable distributions. Although our family of examples disprove the optimality of the long chain in general, we observe that the empirical performance of the long chain is nearly optimal. To further understand the effectiveness of the long chain, we compare its performance to connected designs with at most 2n arcs. We show that the long chain is optimal in this class of designs for exchangeable demand distributions. Our proof is based on a coupling argument and a combinatorial analysis of the structure of maximum flow in directed networks. The analysis provides useful insights towards not just understanding the optimality of long chain but also toward designing more general sparse flexibility networks.