Optimal sparse designs for process flexibility via probabilistic expanders

Xi Chen, Jiawei Zhang, Yuan Zhou

Research output: Contribution to journalArticle

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 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
Volume63
Issue number5
DOIs
StatePublished - Sep 1 2015
Externally publishedYes

Fingerprint

Optimality
Graph
Guarantee
Random demand

Keywords

  • Flexible manufacturing
  • Graph expanders
  • Probabilistic expanders

ASJC Scopus subject areas

  • Computer Science Applications
  • Management Science and Operations Research

Cite this

Optimal sparse designs for process flexibility via probabilistic expanders. / Chen, Xi; Zhang, Jiawei; Zhou, Yuan.

In: Operations Research, Vol. 63, No. 5, 01.09.2015, p. 1159-1176.

Research output: Contribution to journalArticle

Chen, Xi ; Zhang, Jiawei ; Zhou, Yuan. / Optimal sparse designs for process flexibility via probabilistic expanders. In: Operations Research. 2015 ; Vol. 63, No. 5. pp. 1159-1176.
@article{9d9f3d49fe12486f9ec93d1caf39faed,
title = "Optimal sparse designs for process flexibility via probabilistic expanders",
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 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.",
keywords = "Flexible manufacturing, Graph expanders, Probabilistic expanders",
author = "Xi Chen and Jiawei Zhang and Yuan Zhou",
year = "2015",
month = "9",
day = "1",
doi = "10.1287/opre.2015.1416",
language = "English (US)",
volume = "63",
pages = "1159--1176",
journal = "Operations Research",
issn = "0030-364X",
publisher = "INFORMS Inst.for Operations Res.and the Management Sciences",
number = "5",

}

TY - JOUR

T1 - Optimal sparse designs for process flexibility via probabilistic expanders

AU - Chen, Xi

AU - Zhang, Jiawei

AU - Zhou, Yuan

PY - 2015/9/1

Y1 - 2015/9/1

N2 - 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.

AB - 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.

KW - Flexible manufacturing

KW - Graph expanders

KW - Probabilistic expanders

UR - http://www.scopus.com/inward/record.url?scp=84947912025&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84947912025&partnerID=8YFLogxK

U2 - 10.1287/opre.2015.1416

DO - 10.1287/opre.2015.1416

M3 - Article

AN - SCOPUS:84947912025

VL - 63

SP - 1159

EP - 1176

JO - Operations Research

JF - Operations Research

SN - 0030-364X

IS - 5

ER -