A Simple Forward Algorithm to Solve General Dynamic Lot Sizing Models with n Periods in 0(n log n) or 0(n) Time

Awi Federgruen and Michal Tzur
Additional contact information
Awi Federgruen: Graduate School of Business, Columbia University, New York, New York 10027
Michal Tzur: Graduate School of Business, Columbia University, New York, New York 10027

Management Science, 1991, vol. 37, issue 8, 909-925

Abstract: This paper is concerned with the general dynamic lot size model, or (generalized) Wagner-Whitin model. Let n denote the number of periods into which the planning horizon is divided. We describe a simple forward algorithm which solves the general model in 0(n log n) time and 0(n) space, as opposed to the well-known shortest path algorithm advocated over the last 30 years with 0(n 2 ) time. A linear, i.e., 0(n)-time and space algorithm is obtained for two important special cases: (a) models without speculative motives for carrying stock, i.e., where in each interval of time the per unit order cost increases by less than the cost of carrying a unit in stock; (b) models with nondecreasing setup costs. We also derive conditions for the existence of monotone optimal policies and relate these to known (planning horizon and other) results from the literature.

Keywords: dynamic lot sizing models; dynamic programming; complexity (search for similar items in EconPapers)
Date: 1991
References: Add references at CitEc
Citations: View citations in EconPapers (127)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.37.8.909 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:37:y:1991:i:8:p:909-925

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().