Optimal design of process flexibility for general production systems

Xi Chen, Tengyu Ma, Jiawei Zhang, Yuan Zhou

Research output: Contribution to journalArticle

Abstract

Process flexibility is widely adopted as an effective strategy for responding to uncertain demand. Many algorithms for constructing sparse flexibility designs with good theoretical guarantees have been developed for balanced and symmetrical production systems. These systems assume that the number of plants equals the number of products, that supplies have the same capacity, and that demands are independently and identically distributed. In this paper we relax these assumptions and consider a general class of production systems. We construct a simple flexibility design to fulfill (1 − )-fraction of expected demand with high probability where the average degree is O(ln(1/)). To motivate our construction, we first consider a natural weighted probabilistic construction from the existing literature where the degree of each node is proportional to its expected capacity. However, this strategy is shown to be suboptimal. To obtain an optimal construction, we develop a simple yet effective thresholding scheme. The analysis of our approach extends the classic analysis of expander graphs by overcoming several technical difficulties. Our approach may prove useful in other applications that require expansion properties of graphs with nonuniform degree sequences.

Original languageEnglish (US)
Pages (from-to)516-531
Number of pages16
JournalOperations Research
Volume67
Issue number2
DOIs
StatePublished - Jan 1 2019

Fingerprint

Optimal design
Graph
Node
Guarantee
Uncertain demand

Keywords

  • Flexible manufacturing
  • Graph expanders
  • Thresholding
  • Weighted probabilistic construction

ASJC Scopus subject areas

  • Computer Science Applications
  • Management Science and Operations Research

Cite this

Optimal design of process flexibility for general production systems. / Chen, Xi; Ma, Tengyu; Zhang, Jiawei; Zhou, Yuan.

In: Operations Research, Vol. 67, No. 2, 01.01.2019, p. 516-531.

Research output: Contribution to journalArticle

Chen, Xi ; Ma, Tengyu ; Zhang, Jiawei ; Zhou, Yuan. / Optimal design of process flexibility for general production systems. In: Operations Research. 2019 ; Vol. 67, No. 2. pp. 516-531.
@article{dbfe07742be64c8491215389e38de86c,
title = "Optimal design of process flexibility for general production systems",
abstract = "Process flexibility is widely adopted as an effective strategy for responding to uncertain demand. Many algorithms for constructing sparse flexibility designs with good theoretical guarantees have been developed for balanced and symmetrical production systems. These systems assume that the number of plants equals the number of products, that supplies have the same capacity, and that demands are independently and identically distributed. In this paper we relax these assumptions and consider a general class of production systems. We construct a simple flexibility design to fulfill (1 − )-fraction of expected demand with high probability where the average degree is O(ln(1/)). To motivate our construction, we first consider a natural weighted probabilistic construction from the existing literature where the degree of each node is proportional to its expected capacity. However, this strategy is shown to be suboptimal. To obtain an optimal construction, we develop a simple yet effective thresholding scheme. The analysis of our approach extends the classic analysis of expander graphs by overcoming several technical difficulties. Our approach may prove useful in other applications that require expansion properties of graphs with nonuniform degree sequences.",
keywords = "Flexible manufacturing, Graph expanders, Thresholding, Weighted probabilistic construction",
author = "Xi Chen and Tengyu Ma and Jiawei Zhang and Yuan Zhou",
year = "2019",
month = "1",
day = "1",
doi = "10.1287/opre.2018.1780",
language = "English (US)",
volume = "67",
pages = "516--531",
journal = "Operations Research",
issn = "0030-364X",
publisher = "INFORMS Inst.for Operations Res.and the Management Sciences",
number = "2",

}

TY - JOUR

T1 - Optimal design of process flexibility for general production systems

AU - Chen, Xi

AU - Ma, Tengyu

AU - Zhang, Jiawei

AU - Zhou, Yuan

PY - 2019/1/1

Y1 - 2019/1/1

N2 - Process flexibility is widely adopted as an effective strategy for responding to uncertain demand. Many algorithms for constructing sparse flexibility designs with good theoretical guarantees have been developed for balanced and symmetrical production systems. These systems assume that the number of plants equals the number of products, that supplies have the same capacity, and that demands are independently and identically distributed. In this paper we relax these assumptions and consider a general class of production systems. We construct a simple flexibility design to fulfill (1 − )-fraction of expected demand with high probability where the average degree is O(ln(1/)). To motivate our construction, we first consider a natural weighted probabilistic construction from the existing literature where the degree of each node is proportional to its expected capacity. However, this strategy is shown to be suboptimal. To obtain an optimal construction, we develop a simple yet effective thresholding scheme. The analysis of our approach extends the classic analysis of expander graphs by overcoming several technical difficulties. Our approach may prove useful in other applications that require expansion properties of graphs with nonuniform degree sequences.

AB - Process flexibility is widely adopted as an effective strategy for responding to uncertain demand. Many algorithms for constructing sparse flexibility designs with good theoretical guarantees have been developed for balanced and symmetrical production systems. These systems assume that the number of plants equals the number of products, that supplies have the same capacity, and that demands are independently and identically distributed. In this paper we relax these assumptions and consider a general class of production systems. We construct a simple flexibility design to fulfill (1 − )-fraction of expected demand with high probability where the average degree is O(ln(1/)). To motivate our construction, we first consider a natural weighted probabilistic construction from the existing literature where the degree of each node is proportional to its expected capacity. However, this strategy is shown to be suboptimal. To obtain an optimal construction, we develop a simple yet effective thresholding scheme. The analysis of our approach extends the classic analysis of expander graphs by overcoming several technical difficulties. Our approach may prove useful in other applications that require expansion properties of graphs with nonuniform degree sequences.

KW - Flexible manufacturing

KW - Graph expanders

KW - Thresholding

KW - Weighted probabilistic construction

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

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

U2 - 10.1287/opre.2018.1780

DO - 10.1287/opre.2018.1780

M3 - Article

AN - SCOPUS:85068432317

VL - 67

SP - 516

EP - 531

JO - Operations Research

JF - Operations Research

SN - 0030-364X

IS - 2

ER -