Optimal Sparse Designs for Process Flexibility via Probabilistic Expanders

Xi Chen (), Jiawei Zhang () and Yuan Zhou ()
Additional contact information
Xi Chen: Stern School of Business, New York University, New York, New York 10012
Jiawei Zhang: Stern School of Business, New York University, New York, New York 10012; and New York University Shanghai, Shanghai, China 200122
Yuan Zhou: Mathematics Department, Massachusetts Institute of Technology, Cambridge, Massachusetts, 02139

Operations Research, 2015, vol. 63, issue 5, 1159-1176

Abstract: 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.

Keywords: flexible manufacturing; graph expanders; probabilistic expanders (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (13)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2015.1416 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:63:y:2015:i:5:p:1159-1176

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().