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 − ϵ)‐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 O(n/ϵ) arcs to achieve (1 − ϵ)‐optimality for every demand realization. Wang and Zhang (2015) showed that the simple k‐chain design with O(n/ϵ) arcs can achieve (1 − ϵ)‐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/ϵ)) arcs guarantees (1 − ϵ)‐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 Ω(n ln(1/ϵ)) arcs to achieve (1 − ϵ)‐optimality in expectation (and hence w.h.p.). We also show that in order to achieve (1 − ϵ)‐optimality in the worst case, any design would need at least Ω(n/ϵ) arcs; and in order to achieve (1 − ϵ)‐optimality in expectation, k‐chain needs at least Ω(n/ϵ) arcs.
