Abstract: Long chain refers to a directed bi-partite network with directed edges from supply nodes (with fixed unit supply) to demand nodes (with random demand) that form a hamiltonian cycle. This design was introduced in a seminal paper of Jordan and Graves (1995) and has been an important design in process flexibility. Jordan and Graves (1995) observed empirically that the expected performance (satisfied demand) is quite close to the complete bi-partite graph for certain demand distributions. Recently, Simchi-Levi and Wei (2012) show that long chain maximizes the expected performance among all 2-regular networks for exchangeable demand distributions.
We study the performance of long chain in comparison to all networks with 2n edges when the assumption of 2-regularity is relaxed. We show that surprisingly long chain is not optimal in this class of networks even for i.i.d. demand distributions. We present a family of instances where a disconnected network with 2n edges has a strictly better performance than long chain.
However, if we restrict to connected networks with 2n arcs, we show that long chain is optimal for exchangeable demand distributions. Our proof is based on a combinatorial analysis of the structure of maximum flow in directed graphs and a coupling argument that reduces the comparison of expected performance to a sample pathwise comparison of satisfied demand. Our analysis provides useful insights towards not just understanding the optimality of long chain but also towards designing more general sparse flexibility networks (this is joint work with Antoine Desir, Yehua Wei and Jiawei Zhang).
