Improved Algorithms for Economic Lot Size Problems

Alok Aggarwal and James K. Park
Additional contact information
Alok Aggarwal: IBM T. J. Watson Research Center, Yorktown Heights, New York
James K. Park: Sandia National Laboratories, Sandia, New Mexico

Operations Research, 1993, vol. 41, issue 3, 549-571

Abstract: Many problems in inventory control, production planning, and capacity planning can be formulated in terms of a simple economic lot size model proposed independently by A. S. Manne (1958) and by H. M. Wagner and T. M. Whitin (1958). The Manne-Wagner-Whitin model and its variants have been studied widely in the operations research and management science communities, and a large number of algorithms have been proposed for solving various problems expressed in terms of this model, most of which assume concave costs and rely on dynamic programming. In this paper, we show that for many of these concave cost economic lot size problems, the dynamic programming formulation of the problem gives rise to a special kind of array, called a Monge array. We then show how the structure of Monge arrays can be exploited to obtain significantly faster algorithms for these economic lot size problems. We focus on uncapacitated problems, i.e., problems without bounds on production, inventory, or backlogging; capacitated problems are considered in a separate paper.

Keywords: analysis of algorithms: optimal and suboptimal algorithms; computers/computer science: faster lot sizing using Monge arrays; inventory/production: faster algorithms for various Wagner-Whitin models (search for similar items in EconPapers)
Date: 1993
References: Add references at CitEc
Citations: View citations in EconPapers (107)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.41.3.549 (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:oropre:v:41:y:1993:i:3:p:549-571

Access Statistics for this article

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