IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v256y2017i3p777-784.html
   My bibliography  Save this article

Improved exact algorithms to economic lot-sizing with piecewise linear production costs

Author

Listed:
  • Ou, Jinwen

Abstract

In this article we study a classical single-item economic lot-sizing problem, where production cost functions are assumed to be piecewise linear. The lot-sizing problem is fundamental in lot-sizing research, and it is applicable to a wide range of production planning models. The intractability of the problem is related to the value of m, the number of different breakpoints of the production cost functions. When m is arbitrary, the problem is known to be NP-hard (Florian, Lenstra & Rinnooy Kan, 1980). However, if m is fixed, then it can be solved in polynomial time (Koca, Yaman & Akturk, 2014). So far, the most efficient algorithm to solve the problem has a complexity of O(T2m+3), where T is the number of periods in the planning horizon (Koca et al., 2014). In this article we present an improved exact algorithm for solving the problem, where the complexity is reduced to O(Tm+2·logT). As such it also improves upon the computational efficiency of solving some existing lot-sizing problems which are important special cases of our model. In order to achieve a more efficient implementation, our algorithm makes use of a specific data structure, named range minimum query (RMQ).

Suggested Citation

  • Ou, Jinwen, 2017. "Improved exact algorithms to economic lot-sizing with piecewise linear production costs," European Journal of Operational Research, Elsevier, vol. 256(3), pages 777-784.
  • Handle: RePEc:eee:ejores:v:256:y:2017:i:3:p:777-784
    DOI: 10.1016/j.ejor.2016.06.040
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221716304611
    Download Restriction: Full text for ScienceDirect subscribers only

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Hellion, Bertrand & Mangione, Fabien & Penz, Bernard, 2012. "A polynomial time algorithm to solve the single-item capacitated lot sizing problem with minimum order quantities and concave costs," European Journal of Operational Research, Elsevier, vol. 222(1), pages 10-16.
    2. Okhrin, Irena & Richter, Knut, 2011. "An O(T3) algorithm for the capacitated lot sizing problem with minimum order quantities," European Journal of Operational Research, Elsevier, vol. 211(3), pages 507-514, June.
    3. Michael Florian & Morton Klein, 1971. "Deterministic Production Planning with Concave Costs and Capacity Constraints," Management Science, INFORMS, vol. 18(1), pages 12-20, September.
    4. Cary Swoveland, 1975. "A Deterministic Multi-Period Production Planning Model with Piecewise Concave Production and Holding-Backorder Costs," Management Science, INFORMS, vol. 21(9), pages 1007-1013, May.
    5. 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.
    6. 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.
    7. Stephen F. Love, 1973. "Bounded Production and Inventory Models with Piecewise Concave Costs," Management Science, INFORMS, vol. 20(3), pages 313-318, November.
    8. Kenneth R. Baker & Paul Dixon & Michael J. Magazine & Edward A. Silver, 1978. "An Algorithm for the Dynamic Lot-Size Problem with Time-Varying Production Capacity Constraints," Management Science, INFORMS, vol. 24(16), pages 1710-1720, December.
    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. Karimi, B. & Fatemi Ghomi, S. M. T. & Wilson, J. M., 2003. "The capacitated lot sizing problem: a review of models and algorithms," Omega, Elsevier, vol. 31(5), pages 365-378, October.
    11. Sang-Bum Lee & Paul H. Zipkin, 1989. "A Dynamic Lot-Size Model with Make-or-Buy Decisions," Management Science, INFORMS, vol. 35(4), pages 447-458, April.
    12. 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)

    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:eee:ejores:v:256:y:2017:i:3:p:777-784. 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: (Dana Niculescu). General contact details of provider: http://www.elsevier.com/locate/eor .

    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 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.

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

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.