Optimal sparse designs for process flexibility via probabilistic expanders

Xi Chen, Jiawei Zhang, Yuan Zhou

Research output: Contribution to journalArticlepeer-review


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 O4n=.5 arcs to achieve (1-ε)-optimality for every demand realization. Wang and Zhang (2015) showed that the simple k-chain design with O4n=.5 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 O4n ln(1ε/5) 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/ε) 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 ω4n=.5 arcs; and in order to achieve (1-ε)-optimality in expectation, k-chain needs at least ω(n/ε) arcs.

Original languageEnglish (US)
Pages (from-to)1159-1176
Number of pages18
JournalOperations Research
Issue number5
StatePublished - Sep 1 2015
Externally publishedYes


  • Flexible manufacturing
  • Graph expanders
  • Probabilistic expanders

ASJC Scopus subject areas

  • Computer Science Applications
  • Management Science and Operations Research


Dive into the research topics of 'Optimal sparse designs for process flexibility via probabilistic expanders'. Together they form a unique fingerprint.

Cite this