IDEAS home Printed from https://ideas.repec.org/p/cor/louvco/2000039.html
   My bibliography  Save this paper

Solving multi-item capacitated lot-sizing problems with setup times by branch-and-cut

Author

Listed:
  • MILLER, Andrew
  • NEMHAUSER, George
  • SAVELSBERGH, Martin

Abstract

Instances of the multi-item capacitated lot-sizing problem with setup times (MCL) often appear in practice, either in standard form or with additional constraints, but they have generally been difficult to solve to optimality. In MCL demand for multiple items must be met over a time horizon, items compete for a shared capacity, and each setup uses up some of this capacity. In this paper we use results concerning the polyhedral structure of simplified models obtained from a single time period of MCL to obtain strong valid inequalities for MCL. To the best of our knowledge, these inequalities are the first to consider demand for multiple items and the joint capacity restriction simultaneously. We also discuss how to implement these inequalities successfully in a branch-and-cut algorithm. Our computational results suggest that our contributions represent significant progress in solving instances of MCL.

Suggested Citation

  • MILLER, Andrew & NEMHAUSER, George & SAVELSBERGH, Martin, 2000. "Solving multi-item capacitated lot-sizing problems with setup times by branch-and-cut," LIDAM Discussion Papers CORE 2000039, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    • Handle: RePEc:cor:louvco:2000039
    as

    Download full text from publisher

    File URL: https://sites.uclouvain.be/core/publications/coredp/coredp2000.html
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. BELVAUX, Gaetan & WOLSEY, Laurence A., 1998. "Lot-sizing problems: modelling issues and a specialized branch-and-cut system BC-PROD," LIDAM Discussion Papers CORE 1998049, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    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. Christopher Suerie & Hartmut Stadtler, 2003. "The Capacitated Lot-Sizing Problem with Linked Lot Sizes," Management Science, INFORMS, vol. 49(8), pages 1039-1054, August.
    2. Doostmohammadi, Mahdi & Akartunalı, Kerem, 2018. "Valid inequalities for two-period relaxations of big-bucket lot-sizing problems: Zero setup case," European Journal of Operational Research, Elsevier, vol. 267(1), pages 86-95.
    3. 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.
    4. Silvio Alexandre de Araujo & Bert De Reyck & Zeger Degraeve & Ioannis Fragkos & Raf Jans, 2015. "Period Decompositions for the Capacitated Lot Sizing Problem with Setup Times," INFORMS Journal on Computing, INFORMS, vol. 27(3), pages 431-448, August.
    5. 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.
    6. Tao Wu, 2022. "Predictive Search for Capacitated Multi-Item Lot Sizing Problems," INFORMS Journal on Computing, INFORMS, vol. 34(1), pages 385-406, January.
    7. AkartunalI, Kerem & Miller, Andrew J., 2009. "A heuristic approach for big bucket multi-level production planning problems," European Journal of Operational Research, Elsevier, vol. 193(2), pages 396-411, March.
    8. Ioannis Fragkos & Zeger Degraeve & Bert De Reyck, 2016. "A Horizon Decomposition Approach for the Capacitated Lot-Sizing Problem with Setup Times," INFORMS Journal on Computing, INFORMS, vol. 28(3), pages 465-482, August.
    9. VAN VYVE, Mathieu & POCHET, Yves, 2001. "A general heuristic or production planning problems," LIDAM Discussion Papers CORE 2001056, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    10. Muller, Laurent Flindt & Spoorendonk, Simon & Pisinger, David, 2012. "A hybrid adaptive large neighborhood search heuristic for lot-sizing with setup times," European Journal of Operational Research, Elsevier, vol. 218(3), pages 614-623.
    11. Shuai Wang & Jizhuang Hui & Bin Zhu & Ying Liu, 2022. "Adaptive Genetic Algorithm Based on Fuzzy Reasoning for the Multilevel Capacitated Lot-Sizing Problem with Energy Consumption in Synchronizer Production," Sustainability, MDPI, vol. 14(9), pages 1-24, April.
    12. 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.
    13. Yves Pochet & Mathieu Van Vyve, 2004. "A General Heuristic for Production Planning Problems," INFORMS Journal on Computing, INFORMS, vol. 16(3), pages 316-327, August.

    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. BELVAUX, Gaetan & WOLSEY, Laurence A., 2000. "Modelling practical lot-sizing problems as mixed integer programs," LIDAM Discussion Papers CORE 2000009, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).

    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:cor:louvco:2000039. 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: Alain GILLIS (email available below). General contact details of provider: https://edirc.repec.org/data/coreebe.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.