IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v56y2008i1p255-261.html
   My bibliography  Save this article

TECHNICAL NOTE---Solving Linear Cost Dynamic Lot-Sizing Problems in O ( n log n ) Time

Author

Listed:
  • Ravindra K. Ahuja

    (Department of Industrial and Systems Engineering, University of Florida, Gainesville, Florida 32611)

  • Dorit S. Hochbaum

    (Department of Industrial Engineering and Operations Research, and Haas School of Management, University of California, Berkeley, California 94720)

Abstract

In this paper, we study capacitated dynamic lot-sizing problems with or without backorders, under the assumption that production costs are linear, that is, there are no setup costs. These two dynamic lot-sizing problems (with or without backorders) are minimum-cost flow problems on an underlying network that possess a special structure. We show how the well-known successive shortest-path algorithm for the minimum-cost flow problem can be used to solve these problems in O ( n 2 ) time, where n is the number of periods in the dynamic lot-sizing problems, and how, with the use of dynamic trees, we can solve these problems in O ( n log n ) time. Our algorithm also extends to the dynamic lot-sizing problem with integer variables and convex production costs with running time O ( n log n log U ), where U is the largest demand value.

Suggested Citation

  • Ravindra K. Ahuja & Dorit S. Hochbaum, 2008. "TECHNICAL NOTE---Solving Linear Cost Dynamic Lot-Sizing Problems in O ( n log n ) Time," Operations Research, INFORMS, vol. 56(1), pages 255-261, February.
    • Handle: RePEc:inm:oropre:v:56:y:2008:i:1:p:255-261
    DOI: 10.1287/opre.1070.0508
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1070.0508
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.1070.0508?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. 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.
    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. James B. Orlin, 1993. "A Faster Strongly Polynomial Minimum Cost Flow Algorithm," Operations Research, INFORMS, vol. 41(2), pages 338-350, April.
    5. 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. Balachandran Vaidyanathan & Ravindra K. Ahuja, 2010. "Fast Algorithms for Specially Structured Minimum Cost Flow Problems with Applications," Operations Research, INFORMS, vol. 58(6), pages 1681-1696, December.

    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. Kerem Akartunalı & Andrew Miller, 2012. "A computational analysis of lower bounds for big bucket production planning problems," Computational Optimization and Applications, Springer, vol. 53(3), pages 729-753, December.
    2. Ming Zhao & Minjiao Zhang, 2020. "Multiechelon Lot Sizing: New Complexities and Inequalities," Operations Research, INFORMS, vol. 68(2), pages 534-551, March.
    3. Jenny Carolina Saldana Cortés, 2011. "Programación semidefinida aplicada a problemas de cantidad económica de pedido," Documentos CEDE 8735, Universidad de los Andes, Facultad de Economía, CEDE.
    4. 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.
    5. 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.
    6. Drexl, A. & Kimms, A., 1997. "Lot sizing and scheduling -- Survey and extensions," European Journal of Operational Research, Elsevier, vol. 99(2), pages 221-235, June.
    7. 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.
    8. Vernon Ning Hsu, 2000. "Dynamic Economic Lot Size Model with Perishable Inventory," Management Science, INFORMS, vol. 46(8), pages 1159-1169, August.
    9. Pan, Zhendong & Tang, Jiafu & Liu, Ou, 2009. "Capacitated dynamic lot sizing problems in closed-loop supply chain," European Journal of Operational Research, Elsevier, vol. 198(3), pages 810-821, November.
    10. 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.
    11. Hnaien, Faicel & Afsar, Hasan Murat, 2017. "Robust single-item lot-sizing problems with discrete-scenario lead time," International Journal of Production Economics, Elsevier, vol. 185(C), pages 223-229.
    12. 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.
    13. 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.
    14. Kerem Akartunalı & Ioannis Fragkos & Andrew J. Miller & Tao Wu, 2016. "Local Cuts and Two-Period Convex Hull Closures for Big-Bucket Lot-Sizing Problems," INFORMS Journal on Computing, INFORMS, vol. 28(4), pages 766-780, November.
    15. Zhang, Zhi-Hai & Jiang, Hai & Pan, Xunzhang, 2012. "A Lagrangian relaxation based approach for the capacitated lot sizing problem in closed-loop supply chain," International Journal of Production Economics, Elsevier, vol. 140(1), pages 249-255.
    16. H. Edwin Romeijn & Dolores Romero Morales & Wilco Van den Heuvel, 2014. "Computational complexity of finding Pareto efficient outcomes for biobjective lot‐sizing models," Naval Research Logistics (NRL), John Wiley & Sons, vol. 61(5), pages 386-402, August.
    17. 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).
    18. Alper Atamtürk & Dorit S. Hochbaum, 2001. "Capacity Acquisition, Subcontracting, and Lot Sizing," Management Science, INFORMS, vol. 47(8), pages 1081-1100, August.
    19. Brahimi, Nadjib & Absi, Nabil & Dauzère-Pérès, Stéphane & Nordli, Atle, 2017. "Single-item dynamic lot-sizing problems: An updated survey," European Journal of Operational Research, Elsevier, vol. 263(3), pages 838-863.
    20. Hong, Zhaofu & Chu, Chengbin & Yu, Yugang, 2016. "Dual-mode production planning for manufacturing with emission constraints," European Journal of Operational Research, Elsevier, vol. 251(1), pages 96-106.

    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:inm:oropre:v:56:y:2008:i:1:p:255-261. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.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.