An Algorithm for Single-Item Capacitated Economic Lot Sizing with Piecewise Linear Production Costs and General Holding Costs

Dong X. Shaw and Albert P. M. Wagelmans
Additional contact information
Dong X. Shaw: School of Industrial Engineering, Purdue University, West Lafayette, Indiana 47907
Albert P. M. Wagelmans: Econometric Institute, Erasmus University Rotterdam, P.O. Box 1738, 3000 DR Rotterdam, The Netherlands

Management Science, 1998, vol. 44, issue 6, 831-838

Abstract: We consider the Capacitated Economic Lot Size Problem with piecewise linear production costs and general holding costs, which is an NP-hard problem but solvable in pseudo-polynomial time. A straightforward dynamic programming approach to this problem results in an O(n 2 c\bar d\bar ) algorithm, where n is the number of periods, and d\bar and c\bar are the average demand and the average production capacity over the n periods, respectively. However, we present a dynamic programming procedure with complexity O(n 2 q\bar d\bar ), where q\bar is the average number of pieces required to represent the production cost functions. In particular, this means that problems in which the production functions consist of a fixed set-up cost plus a linear variable cost are solved in O(n 2 d\bar ) time. Hence, the running time of our algorithm is only linearly dependent on the magnitude of the data. This result also holds if extensions such as backlogging and startup costs are considered. Moreover, computational experiments indicate that the algorithm is capable of solving quite large problem instances within a reasonable amount of time. For example, the average time needed to solve test instances with 96 periods, 8 pieces in every production cost function, and average demand of 100 units is approximately 40 seconds on a SUN SPARC 5 workstation.

Keywords: Economic Lot Sizing; Dynamic Programming; Computational Complexity (search for similar items in EconPapers)
Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (33)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.44.6.831 (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:44:y:1998:i:6:p:831-838

Access Statistics for this article

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