IDEAS home Printed from https://ideas.repec.org/p/ems/eureir/18017.html
   My bibliography  Save this paper

A geometric algorithm to solve the NI/G/NI/ND capacitated lot-sizing problem in O(T2) time

Author

Listed:
  • van den Heuvel, W.J.
  • Wagelmans, A.P.M.

Abstract

In this paper we consider the capacitated lot-sizing problem (CLSP) with linear costs. It is known that this problem is NP-hard, but there exist special cases that can be solved in polynomial time. The purpose of this paper is twofold. First, we derive a backward algorithm based on the forward algorithm by Chen et al. (1994), which solves the general CLSP. We give a problem instances that requires exponential running time using the backward algo- rithm. Second, we provide a new O(T2) algorithm for the CLSP with non-increasing setup cost, general holding cost, non-increasing production cost and non-decreasing capacities over time. This is done by adapting the backward algorithm. Numerical tests show the better performance of our algorithm compared to the algorithm proposed by Chung and Lin (1988).

Suggested Citation

  • van den Heuvel, W.J. & Wagelmans, A.P.M., 2003. "A geometric algorithm to solve the NI/G/NI/ND capacitated lot-sizing problem in O(T2) time," Econometric Institute Research Papers EI 2003-24, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    • Handle: RePEc:ems:eureir:18017
    as

    Download full text from publisher

    File URL: https://repub.eur.nl/pub/18017/feweco20030806162625.pdf
    Download Restriction: no
    ---><---

    Other versions of this item:

    References listed on IDEAS

    as
    1. Albert Wagelmans & Stan van Hoesel & Antoon Kolen, 1992. "Economic Lot Sizing: An O(n log n) Algorithm That Runs in Linear Time in the Wagner-Whitin Case," Operations Research, INFORMS, vol. 40(1-supplem), pages 145-156, February.
    2. Harvey M. Wagner & Thomson M. Whitin, 1958. "Dynamic Version of the Economic Lot Size Model," Management Science, INFORMS, vol. 5(1), pages 89-96, October.
    3. 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.
    4. 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.
    5. Michael Florian & Morton Klein, 1971. "Deterministic Production Planning with Concave Costs and Capacity Constraints," Management Science, INFORMS, vol. 18(1), pages 12-20, September.
    6. Awi Federgruen & Michal Tzur, 1991. "A Simple Forward Algorithm to Solve General Dynamic Lot Sizing Models with n Periods in 0(n log n) or 0(n) Time," Management Science, INFORMS, vol. 37(8), pages 909-925, August.
    7. Alok Aggarwal & James K. Park, 1993. "Improved Algorithms for Economic Lot Size Problems," Operations Research, INFORMS, vol. 41(3), pages 549-571, June.
    8. van Hoesel, Stan & Wagelmans, Albert & Moerman, Bram, 1994. "Using geometric techniques to improve dynamic programming algorithms for the economic lot-sizing problem and extensions," European Journal of Operational Research, Elsevier, vol. 75(2), pages 312-331, June.
    9. 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.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Stan van Hoesel & H. Edwin Romeijn & Dolores Romero Morales & Albert P. M. Wagelmans, 2005. "Integrated Lot Sizing in Serial Supply Chains with Production Capacities," Management Science, INFORMS, vol. 51(11), pages 1706-1719, November.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Chung-Lun Li & Qingying Li, 2016. "Polynomial-Time Solvability of Dynamic Lot Size Problems," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 33(03), pages 1-20, June.
    2. Jans, Raf & Degraeve, Zeger, 2007. "Meta-heuristics for dynamic lot sizing: A review and comparison of solution approaches," European Journal of Operational Research, Elsevier, vol. 177(3), pages 1855-1875, March.
    3. Stan van Hoesel & H. Edwin Romeijn & Dolores Romero Morales & Albert P. M. Wagelmans, 2005. "Integrated Lot Sizing in Serial Supply Chains with Production Capacities," Management Science, INFORMS, vol. 51(11), pages 1706-1719, November.
    4. Awi Federgruen & Joern Meissner & Michal Tzur, 2007. "Progressive Interval Heuristics for Multi-Item Capacitated Lot-Sizing Problems," Operations Research, INFORMS, vol. 55(3), pages 490-502, June.
    5. Vernon Ning Hsu, 2000. "Dynamic Economic Lot Size Model with Perishable Inventory," Management Science, INFORMS, vol. 46(8), pages 1159-1169, August.
    6. Goisque, Guillaume & Rapine, Christophe, 2017. "An efficient algorithm for the 2-level capacitated lot-sizing problem with identical capacities at both levels," European Journal of Operational Research, Elsevier, vol. 261(3), pages 918-928.
    7. van Hoesel, C.P.M. & Romeijn, H.E. & Romero Morales, M.D. & Wagelmans, A., 2002. "Polynomial time algorithms for some multi-level lot-sizing problems with production capacities," Research Memorandum 018, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    8. Alper Atamtürk & Dorit S. Hochbaum, 2001. "Capacity Acquisition, Subcontracting, and Lot Sizing," Management Science, INFORMS, vol. 47(8), pages 1081-1100, August.
    9. Brahimi, Nadjib & Dauzere-Peres, Stephane & Najid, Najib M. & Nordli, Atle, 2006. "Single item lot sizing problems," European Journal of Operational Research, Elsevier, vol. 168(1), pages 1-16, January.
    10. Mathieu Van Vyve, 2007. "Algorithms for Single-Item Lot-Sizing Problems with Constant Batch Size," Mathematics of Operations Research, INFORMS, vol. 32(3), pages 594-613, August.
    11. Stan van Hoesel & H. Edwin Romeijn & Dolores Romero Morales & Albert P.M. Wagelmans, 2002. "Polynomial Time Algorithms for Some Multi-Level Lot-Sizing Problems with Production Capacities," Tinbergen Institute Discussion Papers 02-066/4, Tinbergen Institute.
    12. Ming Zhao & Minjiao Zhang, 2020. "Multiechelon Lot Sizing: New Complexities and Inequalities," Operations Research, INFORMS, vol. 68(2), pages 534-551, March.
    13. Atamturk, Alper & Munoz, Juan Carlos, 2002. "A Study of the Lot-Sizing Polytope," University of California Transportation Center, Working Papers qt6zz2g0z4, University of California Transportation Center.
    14. Yongpei Guan, 2011. "Stochastic lot-sizing with backlogging: computational complexity analysis," Journal of Global Optimization, Springer, vol. 49(4), pages 651-678, April.
    15. Hark-Chin Hwang, 2010. "Economic Lot-Sizing for Integrated Production and Transportation," Operations Research, INFORMS, vol. 58(2), pages 428-444, April.
    16. Hark-Chin Hwang, 2009. "Inventory Replenishment and Inbound Shipment Scheduling Under a Minimum Replenishment Policy," Transportation Science, INFORMS, vol. 43(2), pages 244-264, May.
    17. Fink, Jiří & Hurink, Johann L., 2015. "Minimizing costs is easier than minimizing peaks when supplying the heat demand of a group of houses," European Journal of Operational Research, Elsevier, vol. 242(2), pages 644-650.
    18. Laurence A. Wolsey, 2002. "Solving Multi-Item Lot-Sizing Problems with an MIP Solver Using Classification and Reformulation," Management Science, INFORMS, vol. 48(12), pages 1587-1602, December.
    19. Jean-Philippe Gayon & Guillaume Massonnet & Christophe Rapine & Gautier Stauffer, 2017. "Fast Approximation Algorithms for the One-Warehouse Multi-Retailer Problem Under General Cost Structures and Capacity Constraints," Mathematics of Operations Research, INFORMS, vol. 42(3), pages 854-875, August.
    20. Hwang, Hark-Chin & Jaruphongsa, Wikrom, 2008. "Dynamic lot-sizing model for major and minor demands," European Journal of Operational Research, Elsevier, vol. 184(2), pages 711-724, January.

    More about this item

    Keywords

    capacitated lot-sizing problem; inventory; production;
    All these keywords.

    JEL classification:

    • L11 - Industrial Organization - - Market Structure, Firm Strategy, and Market Performance - - - Production, Pricing, and Market Structure; Size Distribution of Firms
    • M - Business Administration and Business Economics; Marketing; Accounting; Personnel Economics
    • M11 - Business Administration and Business Economics; Marketing; Accounting; Personnel Economics - - Business Administration - - - Production Management
    • R4 - Urban, Rural, Regional, Real Estate, and Transportation Economics - - Transportation Economics

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:ems:eureir:18017. See general information about how to correct material in RePEc.

    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 CitEc recognized a bibliographic reference but did not link an item in RePEc 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 RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: RePub (email available below). General contact details of provider: https://edirc.repec.org/data/feeurnl.html .

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

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.