Premium
Improved algorithms for a lot‐sizing problem with inventory bounds and backlogging
Author(s) -
Hwang HarkChin,
van den Heuvel Wilco
Publication year - 2012
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/nav.21485
Subject(s) - sizing , computer science , procurement , mathematical optimization , time horizon , dynamic programming , algorithm , operations research , mathematics , economics , art , management , visual arts
Abstract This article considers a dynamic lot‐sizing problem with storage capacity limitation in which backlogging is allowed. For general concave procurement and inventory costs, we present an O ( T 2 ) dynamic programming algorithm where T is the length of the planning horizon. Furthermore, in case of a fixed‐charge cost structure without speculative motives, we show that the problem can be solved in O ( T ) time. By carefully choosing decompositions of the problems, we can use classical results like an efficient matrix searching algorithm and geometric techniques to achieve the results. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012