Capacitated dynamic lot-sizing problem with delivery/production time windows

H. C. Hwang; W. Jaruphongsa; S. Çetinkaya; C. Y. Lee

doi:10.1016/j.orl.2010.04.009

Capacitated dynamic lot-sizing problem with delivery/production time windows

H. C. Hwang
, W. Jaruphongsa
, S. Çetinkaya
, C. Y. Lee

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

9 Citations (Scopus)

Abstract

In this paper we generalize the classical dynamic lot-sizing problem by considering production capacity constraints as well as delivery and/or production time windows. Utilizing an untraditional decomposition principle, we develop a polynomial-time algorithm for computing an optimal solution for the problem under the assumption of non-speculative costs. The proposed solution methodology is based on a dynamic programming algorithm that runs in O(nT4) time, where n is the number of demands and T is the length of the planning horizon.

Original language	English
Pages (from-to)	408-413
Number of pages	6
Journal	Operations Research Letters
Volume	38
Issue number	5
DOIs	https://doi.org/10.1016/j.orl.2010.04.009
Publication status	Published - Sept 2010

Bibliographical note

Funding Information:
The authors are grateful to Professor Retsef Levi for pointing out the relevance between our problem and capacitated rectangle stabbing problem. This research is supported in part by NUS ARF grant R-266-000-019-112 and NSF grants CAREER/DMII-0093654 and DMII-9908221 and the Korea Research Foundation Grant funded by the Korean Government (MOEHRD, Basic Research Promotion Fund) ( KRF-2008-521-D00540 ).

Keywords

Capacitated production model
Demand time window
Dynamic lot-sizing model

Access to Document

10.1016/j.orl.2010.04.009

Cite this

@article{6234901f41744e0296c7688ca7c6df4d,

title = "Capacitated dynamic lot-sizing problem with delivery/production time windows",

abstract = "In this paper we generalize the classical dynamic lot-sizing problem by considering production capacity constraints as well as delivery and/or production time windows. Utilizing an untraditional decomposition principle, we develop a polynomial-time algorithm for computing an optimal solution for the problem under the assumption of non-speculative costs. The proposed solution methodology is based on a dynamic programming algorithm that runs in O(nT4) time, where n is the number of demands and T is the length of the planning horizon.",

keywords = "Capacitated production model, Demand time window, Dynamic lot-sizing model",

author = "Hwang, \{H. C.\} and W. Jaruphongsa and S. {\c C}etinkaya and Lee, \{C. Y.\}",

note = "Funding Information: The authors are grateful to Professor Retsef Levi for pointing out the relevance between our problem and capacitated rectangle stabbing problem. This research is supported in part by NUS ARF grant R-266-000-019-112 and NSF grants CAREER/DMII-0093654 and DMII-9908221 and the Korea Research Foundation Grant funded by the Korean Government (MOEHRD, Basic Research Promotion Fund) ( KRF-2008-521-D00540 ).",

year = "2010",

month = sep,

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

language = "English",

volume = "38",

pages = "408--413",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "5",

}

TY - JOUR

T1 - Capacitated dynamic lot-sizing problem with delivery/production time windows

AU - Hwang, H. C.

AU - Jaruphongsa, W.

AU - Çetinkaya, S.

AU - Lee, C. Y.

N1 - Funding Information: The authors are grateful to Professor Retsef Levi for pointing out the relevance between our problem and capacitated rectangle stabbing problem. This research is supported in part by NUS ARF grant R-266-000-019-112 and NSF grants CAREER/DMII-0093654 and DMII-9908221 and the Korea Research Foundation Grant funded by the Korean Government (MOEHRD, Basic Research Promotion Fund) ( KRF-2008-521-D00540 ).

PY - 2010/9

Y1 - 2010/9

N2 - In this paper we generalize the classical dynamic lot-sizing problem by considering production capacity constraints as well as delivery and/or production time windows. Utilizing an untraditional decomposition principle, we develop a polynomial-time algorithm for computing an optimal solution for the problem under the assumption of non-speculative costs. The proposed solution methodology is based on a dynamic programming algorithm that runs in O(nT4) time, where n is the number of demands and T is the length of the planning horizon.

AB - In this paper we generalize the classical dynamic lot-sizing problem by considering production capacity constraints as well as delivery and/or production time windows. Utilizing an untraditional decomposition principle, we develop a polynomial-time algorithm for computing an optimal solution for the problem under the assumption of non-speculative costs. The proposed solution methodology is based on a dynamic programming algorithm that runs in O(nT4) time, where n is the number of demands and T is the length of the planning horizon.

KW - Capacitated production model

KW - Demand time window

KW - Dynamic lot-sizing model

UR - https://www.scopus.com/pages/publications/77957906774

U2 - 10.1016/j.orl.2010.04.009

DO - 10.1016/j.orl.2010.04.009

M3 - Article

AN - SCOPUS:77957906774

SN - 0167-6377

VL - 38

SP - 408

EP - 413

JO - Operations Research Letters

JF - Operations Research Letters

IS - 5

ER -

Capacitated dynamic lot-sizing problem with delivery/production time windows

Abstract

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this