IDEAS home Printed from https://ideas.repec.org/
MyIDEAS: Login to save this paper or follow this series

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

  • Awi Federgruen

    (Graduate School of Business, Columbia University)

  • Joern Meissner

    (Department of Management Science, Lancaster University Management School)

  • Michal Tzur

    (Department of Industrial Engineering, Tel Aviv University)

We consider a family of N items which 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 which minimizes the sum of inventory carrying, fixed and variable order costs. All demands, cost parameters and capacity limits may be time-dependent. In the basic (JS)-model, the setup cost of an order does not depend on the composition of the order. The (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 epsilon-optimal for any desired value of epsilon > 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 the (JIS) model, 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.

If you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.

File URL: http://www.meiss.com/en/publications/interval-heuristics.html
File Function: Webpage
Download Restriction: no

File URL: http://www.meiss.com/download/SC-Federgruen-Meissner-Tzur.pdf
File Function: Full Paper
Download Restriction: no

Paper provided by Department of Management Science, Lancaster University in its series Working Papers with number MRG/0001.

as
in new window

Length: 13 pages
Date of creation: Sep 2002
Date of revision: Nov 2004
Publication status: Published in Operations Research Vol 55, No 3 (May-June 2007), pp 490-502.
Handle: RePEc:lms:mansci:mrg-0001
Contact details of provider: Web page: http://www.lums.lancs.ac.uk/departments/ManSci/
More information through EDIRC

References listed on IDEAS
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:

as in new window
  1. van Nunen, J. A. E. E. & Wessels, J., 1978. "Multi-item lot size determination and scheduling under capacity constraints," European Journal of Operational Research, Elsevier, vol. 2(1), pages 36-41, January.
  2. M. Florian & J. K. Lenstra & A. H. G. Rinnooy Kan, 1980. "Deterministic Production Planning: Algorithms and Complexity," Management Science, INFORMS, vol. 26(7), pages 669-679, July.
  3. William W. Trigeiro & L. Joseph Thomas & John O. McClain, 1989. "Capacitated Lot Sizing with Setup Times," Management Science, INFORMS, vol. 35(3), pages 353-366, March.
  4. Gaetan Belvaux & Laurence A. Wolsey, 2001. "Modelling Practical Lot-Sizing Problems as Mixed-Integer Programs," Management Science, INFORMS, vol. 47(7), pages 993-1007, July.
  5. Stephen C. Graves, 1982. "Using Lagrangean Techniques to Solve Hierarchical Production Planning Problems," Management Science, INFORMS, vol. 28(3), pages 260-275, March.
  6. Michael Florian & Morton Klein, 1971. "Deterministic Production Planning with Concave Costs and Capacity Constraints," Management Science, INFORMS, vol. 18(1), pages 12-20, September.
  7. Christopher Suerie & Hartmut Stadtler, 2003. "The Capacitated Lot-Sizing Problem with Linked Lot Sizes," Management Science, INFORMS, vol. 49(8), pages 1039-1054, August.
  8. Gabriel R. Bitran & Horacio H. Yanasse, 1982. "Computational Complexity of the Capacitated Lot Size Problem," Management Science, INFORMS, vol. 28(10), pages 1174-1186, October.
  9. Suerie, Christopher & Stadtler, Hartmut, 2003. "The Capacitated lot-sizing problem with linked lot sizes," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 20206, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
  10. Dong X. Shaw & Albert P. M. Wagelmans, 1998. "An Algorithm for Single-Item Capacitated Economic Lot Sizing with Piecewise Linear Production Costs and General Holding Costs," Management Science, INFORMS, vol. 44(6), pages 831-838, June.
  11. Stadtler, Hartmut, 2003. "Multilevel lot sizing with setup times and multiple constrained resources: Internally rolling schedules with lot-sizing windows," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 20204, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
Full references (including those not matched with items on IDEAS)

This item is not listed on Wikipedia, on a reading list or among the top items on IDEAS.

When requesting a correction, please mention this item's handle: RePEc:lms:mansci:mrg-0001. See general information about how to correct material in RePEc.

For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Joern Meissner)

If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

If references are entirely missing, you can add them using this form.

If the full references list an item that is present in RePEc, but the system did not link to it, you can help with this form.

If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your profile, as there may be some citations waiting for confirmation.

Please note that corrections may take a couple of weeks to filter through the various RePEc services.

This information is provided to you by IDEAS at the Research Division of the Federal Reserve Bank of St. Louis using RePEc data.