Improved algorithms for a lot-sizing problem with inventory bounds and backlogging

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(T2) dynamic programming algorithm where T is the length of the planning horizon. Furthermore, in case of a fixed‐...

Full description

Saved in:
Bibliographic Details
Published in:Naval research logistics 2012-04, Vol.59 (3-4), p.244-253
Main Authors: Hwang, Hark-Chin, van den Heuvel, Wilco
Format: Article
Language:English
Subjects:
algorithms
inventory and production
lot-sizing
storage capacity
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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(T2) 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
ISSN:0894-069X
1520-6750
DOI:10.1002/nav.21485