An O (n2) algorithm for lot sizing with inventory bounds and fixed costs

Alper Atamtürk; Simge Küçükyavuz

doi:10.1016/j.orl.2007.08.004

An O (n²) algorithm for lot sizing with inventory bounds and fixed costs

Alper Atamtürk^*, Simge Küçükyavuz

^*Corresponding author for this work

Industrial Engineering and Management Sciences

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

29 Scopus citations

Abstract

We present an O (n²) dynamic programming algorithm for lot sizing with inventory bounds and fixed costs, where n is the number of time periods. The algorithm utilizes a hierarchy of two layers of value functions and improves the complexity bound of an earlier O (n³) algorithm for concave-cost and bounded inventory.

Original language	English (US)
Pages (from-to)	297-299
Number of pages	3
Journal	Operations Research Letters
Volume	36
Issue number	3
DOIs	https://doi.org/10.1016/j.orl.2007.08.004
State	Published - May 2008

Keywords

Dynamic programming
Extreme points
Lot sizing

ASJC Scopus subject areas

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

Access to Document

10.1016/j.orl.2007.08.004

Cite this

@article{ad1996f9c9b1489caef23ed488e7732c,

title = "An O (n2) algorithm for lot sizing with inventory bounds and fixed costs",

abstract = "We present an O (n2) dynamic programming algorithm for lot sizing with inventory bounds and fixed costs, where n is the number of time periods. The algorithm utilizes a hierarchy of two layers of value functions and improves the complexity bound of an earlier O (n3) algorithm for concave-cost and bounded inventory.",

keywords = "Dynamic programming, Extreme points, Lot sizing",

author = "Alper Atamt{\"u}rk and Simge K{\"u}{\c c}{\"u}kyavuz",

year = "2008",

month = may,

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

language = "English (US)",

volume = "36",

pages = "297--299",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier",

number = "3",

}

TY - JOUR

T1 - An O (n2) algorithm for lot sizing with inventory bounds and fixed costs

AU - Atamtürk, Alper

AU - Küçükyavuz, Simge

PY - 2008/5

Y1 - 2008/5

N2 - We present an O (n2) dynamic programming algorithm for lot sizing with inventory bounds and fixed costs, where n is the number of time periods. The algorithm utilizes a hierarchy of two layers of value functions and improves the complexity bound of an earlier O (n3) algorithm for concave-cost and bounded inventory.

AB - We present an O (n2) dynamic programming algorithm for lot sizing with inventory bounds and fixed costs, where n is the number of time periods. The algorithm utilizes a hierarchy of two layers of value functions and improves the complexity bound of an earlier O (n3) algorithm for concave-cost and bounded inventory.

KW - Dynamic programming

KW - Extreme points

KW - Lot sizing

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

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

U2 - 10.1016/j.orl.2007.08.004

DO - 10.1016/j.orl.2007.08.004

M3 - Article

AN - SCOPUS:42949138212

SN - 0167-6377

VL - 36

SP - 297

EP - 299

JO - Operations Research Letters

JF - Operations Research Letters

IS - 3

ER -