Tata Institute of Fundamental Research

Sparse Process Flexibility Designs: Is Long-Chain Really Optimal?

Speaker: Vineet Goyal (Columbia University Industrial Engineering and Operations Research 500 West, 120th Street New York, NY 10027 United States of America)
Organiser: Sandeep K Juneja
Date: Thursday, 22 May 2014, 16:00 to 17:00
Venue: AG-80

(Scan to add to calendar)
Abstract:  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).