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

Valid inequalities and extended formulations for lot-sizing and scheduling problem with sequence-dependent setups

Author

Listed:
  • Lee, Younsoo
  • Lee, Kyungsik

Abstract

In this paper, we propose new valid inequalities and extended formulations for the lot-sizing and scheduling problem with sequence-dependent setups, which are derived by investigating the single-period substructure of the problem. Specifically, we derive two new families of valid inequalities and identify their facet-defining conditions. Additionally, we demonstrate that these inequalities can be separated in polynomial time. After introducing the existing extended formulations for the problem, we provide new extended formulations adapting decision variables representing the time-flow and compare the theoretical strengths of the various formulations and valid inequalities, including the proposed ones. Finally, we conduct computational experiments to demonstrate the effectiveness of the proposed inequalities and formulations. The test results indicate that the proposed inequalities and extended formulations facilitate tightening the linear programming relaxation bounds.

Suggested Citation

  • Lee, Younsoo & Lee, Kyungsik, 2023. "Valid inequalities and extended formulations for lot-sizing and scheduling problem with sequence-dependent setups," European Journal of Operational Research, Elsevier, vol. 310(1), pages 201-216.
    • Handle: RePEc:eee:ejores:v:310:y:2023:i:1:p:201-216
    DOI: 10.1016/j.ejor.2023.03.003
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221723001972
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2023.03.003?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
    ---><---

    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. Ríos-Solís, Yasmín Á & Ibarra-Rojas, Omar J. & Cabo, Marta & Possani, Edgar, 2020. "A heuristic based on mathematical programming for a lot-sizing and scheduling problem in mold-injection production," European Journal of Operational Research, Elsevier, vol. 284(3), pages 861-873.
    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. Guimarães, Luis & Klabjan, Diego & Almada-Lobo, Bernardo, 2013. "Pricing, relaxing and fixing under lot sizing and scheduling," European Journal of Operational Research, Elsevier, vol. 230(2), pages 399-411.
    4. Guimarães, Luis & Klabjan, Diego & Almada-Lobo, Bernardo, 2014. "Modeling lotsizing and scheduling problems with sequence dependent setups," European Journal of Operational Research, Elsevier, vol. 239(3), pages 644-662.
    5. 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.
    6. Alan S. Manne, 1958. "Programming of Economic Lot Sizes," Management Science, INFORMS, vol. 4(2), pages 115-135, January.
    7. BARANY, Imre & VAN ROY, Tony J. & WOLSEY, Laurence A., 1984. "Strong formulations for multi-item capacitated lot sizing," LIDAM Reprints CORE 590, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    8. Fleischmann, B. & Meyr, H., 1997. "The General Lotsizing and Scheduling Problem," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 36068, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    9. Karina Copil & Martin Wörbelauer & Herbert Meyr & Horst Tempelmeier, 2017. "Simultaneous lotsizing and scheduling problems: a classification and review of models," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 39(1), pages 1-64, January.
    10. Lee, Younsoo & Lee, Kyungsik, 2020. "Lot-sizing and scheduling in flat-panel display manufacturing process," Omega, Elsevier, vol. 93(C).
    11. Gary D. Eppen & R. Kipp Martin, 1987. "Solving Multi-Item Capacitated Lot-Sizing Problems Using Variable Redefinition," Operations Research, INFORMS, vol. 35(6), pages 832-848, December.
    12. Carvalho, Desiree M. & Nascimento, Mariá C.V., 2022. "Hybrid matheuristics to solve the integrated lot sizing and scheduling problem on parallel machines with sequence-dependent and non-triangular setup," European Journal of Operational Research, Elsevier, vol. 296(1), pages 158-173.
    13. Letchford, Adam N. & Salazar-González, Juan-José, 2015. "Stronger multi-commodity flow formulations of the Capacitated Vehicle Routing Problem," European Journal of Operational Research, Elsevier, vol. 244(3), pages 730-738.
    14. 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.
    15. Imre Barany & Tony J. Van Roy & Laurence A. Wolsey, 1984. "Strong Formulations for Multi-Item Capacitated Lot Sizing," Management Science, INFORMS, vol. 30(10), pages 1255-1261, October.
    Full references (including those not matched with items on IDEAS)

    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. 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.
    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. Mac Cawley, Alejandro & Maturana, Sergio & Pascual, Rodrigo & Tortorella, Guilherme Luz, 2022. "Scheduling wine bottling operations with multiple lines and sequence-dependent set-up times: Robust formulation and a decomposition solution approach," European Journal of Operational Research, Elsevier, vol. 303(2), pages 819-839.
    4. Bunn, Kevin A. & Ventura, José A., 2023. "A dynamic programming approach for the two-product capacitated lot-sizing problem with concave costs," European Journal of Operational Research, Elsevier, vol. 307(1), pages 116-129.
    5. Dogacan Yilmaz & İ. Esra Büyüktahtakın, 2023. "Learning Optimal Solutions via an LSTM-Optimization Framework," SN Operations Research Forum, Springer, vol. 4(2), pages 1-40, June.
    6. 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.
    7. Melega, Gislaine Mara & de Araujo, Silvio Alexandre & Jans, Raf, 2018. "Classification and literature review of integrated lot-sizing and cutting stock problems," European Journal of Operational Research, Elsevier, vol. 271(1), pages 1-19.
    8. Nadjib Brahimi & Stéphane Dauzère-Pérès & Najib M. Najid, 2006. "Capacitated Multi-Item Lot-Sizing Problems with Time Windows," Operations Research, INFORMS, vol. 54(5), pages 951-967, October.
    9. 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.
    10. 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.
    11. Drexl, Andreas & Kimms, Alf, 1996. "Lot sizing and scheduling: Survey and extensions," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 421, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    12. Fabrizio Marinelli & Maria Nenni & Antonio Sforza, 2007. "Capacitated lot sizing and scheduling with parallel machines and shared buffers: A case study in a packaging company," Annals of Operations Research, Springer, vol. 150(1), pages 177-192, March.
    13. Eksioglu, Sandra Duni, 2009. "A primal-dual algorithm for the economic lot-sizing problem with multi-mode replenishment," European Journal of Operational Research, Elsevier, vol. 197(1), pages 93-101, August.
    14. Palak, Gökçe & Ekşioğlu, Sandra Duni & Geunes, Joseph, 2014. "Analyzing the impacts of carbon regulatory mechanisms on supplier and mode selection decisions: An application to a biofuel supply chain," International Journal of Production Economics, Elsevier, vol. 154(C), pages 198-216.
    15. Lee, Younsoo & Lee, Kyungsik, 2022. "New integer optimization models and an approximate dynamic programming algorithm for the lot-sizing and scheduling problem with sequence-dependent setups," European Journal of Operational Research, Elsevier, vol. 302(1), pages 230-243.
    16. Andrea Raiconi & Julia Pahl & Monica Gentili & Stefan Voß & Raffaele Cerulli, 2017. "Tactical Production and Lot Size Planning with Lifetime Constraints: A Comparison of Model Formulations," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 34(05), pages 1-24, October.
    17. Karina Copil & Martin Wörbelauer & Herbert Meyr & Horst Tempelmeier, 2017. "Simultaneous lotsizing and scheduling problems: a classification and review of models," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 39(1), pages 1-64, January.
    18. B Karimi & S M T Fatemi Ghomi & J M Wilson, 2006. "A tabu search heuristic for solving the CLSP with backlogging and set-up carry-over," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 57(2), pages 140-147, February.
    19. Zeger Degraeve & Raf Jans, 2007. "A New Dantzig-Wolfe Reformulation and Branch-and-Price Algorithm for the Capacitated Lot-Sizing Problem with Setup Times," Operations Research, INFORMS, vol. 55(5), pages 909-920, October.
    20. Absi, Nabil & Kedad-Sidhoum, Safia, 2008. "The multi-item capacitated lot-sizing problem with setup times and shortage costs," European Journal of Operational Research, Elsevier, vol. 185(3), pages 1351-1374, March.

    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:310:y:2023:i:1:p:201-216. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.