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

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

0.00 Avg rating0 Votes
Article ID: iaor1997500
Country: United States
Volume: 42
Issue: 1
Start Page Number: 142
End Page Number: 150
Publication Date: Jan 1996
Journal: Management Science
Authors: ,
Keywords: inventory: storage, storage, programming: dynamic
Abstract:

The authors 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, they 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.

Reviews

Required fields are marked *. Your email address will not be published.