An O(T3) algorithm for the economic lot-sizing problem with constant capacities

C. P.M. Van Hoesel, A. P.M. Wagelmans

Research output: Contribution to journalArticleAcademicpeer-review

125 Citations (Scopus)

Abstract

We develop an algorithm that solves the constant capacities economic lot-sizing problem with concave production costs and linear holding costs in O(T3) 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(T4) running time of an earlier algorithm.

Original languageEnglish
Pages (from-to)142-150
Number of pages9
JournalManagement Science
Volume42
Issue number1
DOIs
Publication statusPublished - Jan 1996

Fingerprint

Dive into the research topics of 'An O(T3) algorithm for the economic lot-sizing problem with constant capacities'. Together they form a unique fingerprint.

Cite this