This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Federgruen, A. Articles by Tzur, M. Search for Related Content

Progressive Interval Heuristics for Multi-Item Capacitated Lot-Sizing Problems

Graduate School of Business, Columbia University, 101 Uris Hall, New York, New York 10027
Department of Management Science, Lancaster University Management School, Room A48, Lancaster, LA1 4YX, United Kingdom
Department of Industrial Engineering, Tel Aviv University, Ramat Aviv, Tel Aviv 69978, Israel
af7{at}columbia.edu
joe{at}meiss.com
tzur{at}eng.tau.ac.il

We consider a family of N items that are produced in, or obtained from, the same production facility. Demands are deterministic for each item and each period within a given horizon of T periods. If in a given period an order is placed, setup costs are incurred. The aggregate order size is constrained by a capacity limit. The objective is to find a lot-sizing strategy that satisfies the demands for all items over the entire horizon without backlogging, and that minimizes the sum of inventory-carrying costs, fixed-order costs, and variable-order costs.

All demands, cost parameters, and capacity limits may be time dependent. In the basic joint setup cost (JS) model, the setup cost of an order does not depend on the composition of the order. The joint and item-dependent setup cost (JIS) model allows for item-dependent setup costs in addition to the joint setup costs. We develop and analyze a class of so-called progressive interval heuristics. A progessive interval heuristic solves a JS or JIS problem over a progressively larger time interval, always starting with period 1, but fixing the setup variables of a progressively larger number of periods at their optimal values in earlier iterations. Different variants in this class of heuristics allow for different degrees of flexibility in adjusting continuous variables determined in earlier iterations of the algorithm.

For the JS-model and the two basic implementations of the progressive interval heuristics, we show under some mild parameter conditions that the heuristics can be designed to be -optimal for any desired value of > 0 with a running time that is polynomially bounded in the size of the problem. They can also be designed to be simultaneously asymptotically optimal and polynomially bounded.

A numerical study covering both the JS and JIS models shows that a progressive interval heuristic generates close-to-optimal solutions with modest computational effort and that it can be effectively used to solve large-scale problems.

Subject classifications: inventory; production; multi-item; echelon; approximation; heuristic.
History: Received June 2003; revision received July 2006; accepted July 2006.