Optimization Online


An O(n^2) Algorithm for Lot Sizing with Inventory Bounds and Fixed Costs

Alper Atamturk (atamturk***at***berkeley.edu)
Simge Kucukyavuz (simge***at***sie.arizona.edu)

Abstract: Lot-sizing problems with inventory bounds and fixed charges have not received much attention in the literature, even though there are many emerging applications in which highly specialized storage is the main activity of interest. The traditional infinite capacity and variable cost assumptions on inventory that have been prevalent in the literature are inappropriate in situations for which tight storage capacity and high fixed cost of specialized storage are critical. Here we present an O(n^2) dynamic programming algorithm for the lot-sizing problem with inventory bounds and fixed costs, where n is the number of time periods. The algorithm operates on a hierarchy of two layers of value functions to solve the problem efficiently. It improves the complexity bound of the classic O(n^3) algorithm of Love (1973) for lot sizing with concave cost and bounded inventory.


Category 1: Applications -- OR and Management Sciences

Category 2: Applications -- OR and Management Sciences (Production and Logistics )

Citation: Appeared in Operations Research Letters. Check http://www.ieor.berkeley.edu/~atamturk/


Entry Submitted: 06/26/2007
Entry Accepted: 06/29/2007
Entry Last Modified: 05/21/2009

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society