An O (N2)-time algorithm for the stochastic uncapacitated lot-sizing problem with random lead times

Ruiwei Jiang; Yongpei Guan

doi:10.1016/j.orl.2010.10.004

An O (N²)-time algorithm for the stochastic uncapacitated lot-sizing problem with random lead times

Ruiwei Jiang, Yongpei Guan

Research output: Contribution to journal › Article › peer-review

10 Scopus citations

Abstract

In this paper, we develop a dynamic programming algorithm for the scenario-tree-based stochastic uncapacitated lot-sizing problem with random lead times. Our algorithm runs in O(N²) time, where N is the input size of the scenario tree, and improves the recently developed algorithm that runs in O(N³) time.

Original language	English (US)
Pages (from-to)	74-77
Number of pages	4
Journal	Operations Research Letters
Volume	39
Issue number	1
DOIs	https://doi.org/10.1016/j.orl.2010.10.004
State	Published - Jan 2011
Externally published	Yes

Keywords

Dynamic programming
Lot-sizing
Random lead time
Stochastic programming

ASJC Scopus subject areas

Software
Management Science and Operations Research
Industrial and Manufacturing Engineering
Applied Mathematics

Access to Document

10.1016/j.orl.2010.10.004

Cite this

@article{e756a787545b4d2fb863100b92dc3d36,

title = "An O (N2)-time algorithm for the stochastic uncapacitated lot-sizing problem with random lead times",

abstract = "In this paper, we develop a dynamic programming algorithm for the scenario-tree-based stochastic uncapacitated lot-sizing problem with random lead times. Our algorithm runs in O(N2) time, where N is the input size of the scenario tree, and improves the recently developed algorithm that runs in O(N3) time.",

keywords = "Dynamic programming, Lot-sizing, Random lead time, Stochastic programming",

author = "Ruiwei Jiang and Yongpei Guan",

note = "Funding Information: The authors would like to thank the area editor, R{\"u}diger Schultz, and the anonymous referee for their suggestions on improving the quality of this paper. This research was supported in part by the US National Science Foundation under Award CMMI-0942154 and under CAREER Award CMMI-0942156 . ",

year = "2011",

month = jan,

doi = "10.1016/j.orl.2010.10.004",

language = "English (US)",

volume = "39",

pages = "74--77",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - An O (N2)-time algorithm for the stochastic uncapacitated lot-sizing problem with random lead times

AU - Jiang, Ruiwei

AU - Guan, Yongpei

N1 - Funding Information: The authors would like to thank the area editor, Rüdiger Schultz, and the anonymous referee for their suggestions on improving the quality of this paper. This research was supported in part by the US National Science Foundation under Award CMMI-0942154 and under CAREER Award CMMI-0942156 .

PY - 2011/1

Y1 - 2011/1

N2 - In this paper, we develop a dynamic programming algorithm for the scenario-tree-based stochastic uncapacitated lot-sizing problem with random lead times. Our algorithm runs in O(N2) time, where N is the input size of the scenario tree, and improves the recently developed algorithm that runs in O(N3) time.

AB - In this paper, we develop a dynamic programming algorithm for the scenario-tree-based stochastic uncapacitated lot-sizing problem with random lead times. Our algorithm runs in O(N2) time, where N is the input size of the scenario tree, and improves the recently developed algorithm that runs in O(N3) time.

KW - Dynamic programming

KW - Lot-sizing

KW - Random lead time

KW - Stochastic programming

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

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

U2 - 10.1016/j.orl.2010.10.004

DO - 10.1016/j.orl.2010.10.004

M3 - Article

AN - SCOPUS:78650792113

SN - 0167-6377

VL - 39

SP - 74

EP - 77

JO - Operations Research Letters

JF - Operations Research Letters

IS - 1

ER -