An O(T 3 ) Algorithm for the Economic Lot-Sizing Problem with Constant Capacities

C. P. M. van Hoesel and A. P. M. Wagelmans
Additional contact information
C. P. M. van Hoesel: Limburg University, Maastricht, The Netherlands
A. P. M. Wagelmans: Erasmus University, Rotterdam, The Netherlands

Management Science, 1996, vol. 42, issue 1, 142-150

Abstract: We develop an algorithm that solves the constant capacities economic lot-sizing problem with concave production costs and linear holding in O(T 3 ) time. The algorithm is based on the standard dynamic programming approach which requires the computation of the minimal costs for all possible subplans of the production plan. Instead of computing these costs in a straightforward manner, we use structural properties of optimal subplans to arrive at a more efficient implementation. Our algorithm improves upon the O(T 4 ) running time of an earlier algorithm.

Keywords: economic lot-sizing; complexity (search for similar items in EconPapers)
Date: 1996
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.42.1.142 (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:42:y:1996:i:1:p:142-150

Access Statistics for this article

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