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

Fix-and-optimize heuristics for capacitated lot-sizing with sequence-dependent setups and substitutions

Author

Listed:
  • Lang, Jan Christian
  • Shen, Zuo-Jun Max

Abstract

In this paper, we consider a capacitated single-level dynamic lot-sizing problem with sequence-dependent setup costs and times that includes product substitution options. The model is motivated from a real-world production planning problem of a manufacturer of plastic sheets used as an interlayer in car windshields. We develop a mixed-integer programming (MIP) formulation of the problem and devise MIP-based Relax&Fix and Fix&Optimize heuristics. Unlike existing literature, we combine Fix&Optimize with a time decomposition. Also, we develop a specialized substitute decomposition and devise a computation budget allocation scheme for ensuring a uniform, efficient usage of computation time by decompositions and their subproblems. Computational experiments were performed on generated instances whose structure follows that of the considered practical application and which have rather tight production capacities. We found that a Fix&Optimize algorithm with an overlapping time decomposition yielded the best solutions. It outperformed the state-of-the-art approach Relax&Fix and all other tested algorithm variants on the considered class of instances, and returned feasible solutions with neither overtime nor backlogging for all instances. It returned solutions that were on average only 5% worse than those returned by a standard MIP solver after 4Â hours and 19% better than those of Relax&Fix.

Suggested Citation

  • Lang, Jan Christian & Shen, Zuo-Jun Max, 2011. "Fix-and-optimize heuristics for capacitated lot-sizing with sequence-dependent setups and substitutions," European Journal of Operational Research, Elsevier, vol. 214(3), pages 595-605, November.
    • Handle: RePEc:eee:ejores:v:214:y:2011:i:3:p:595-605
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221711004395
    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. 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. Jörg Thomas Dickersbach, 2006. "Supply Chain Management with APO," Springer Books, Springer, edition 0, number 978-3-540-24817-0, July.
    3. Horst Tempelmeier & Matthias Derstroff, 1996. "A Lagrangean-Based Heuristic for Dynamic Multilevel Multiitem Constrained Lotsizing with Setup Times," Management Science, INFORMS, vol. 42(5), pages 738-757, May.
    4. Helber, Stefan & Sahling, Florian, 2010. "A fix-and-optimize approach for the multi-level capacitated lot sizing problem," International Journal of Production Economics, Elsevier, vol. 123(2), pages 247-256, February.
    5. 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).
    6. Helsgaun, Keld, 2000. "An effective implementation of the Lin-Kernighan traveling salesman heuristic," European Journal of Operational Research, Elsevier, vol. 126(1), pages 106-130, October.
    7. Sahling, Florian & Buschkühl, Lisbeth & Tempelmeier, Horst & Helber, Stefan, 2008. "Solving a Multi-Level Capacitated Lot Sizing Problem with Multi-Period Setup Carry-Over via a Fix-and-Optimize Heuristic," Hannover Economic Papers (HEP) dp-400, Leibniz Universität Hannover, Wirtschaftswissenschaftliche Fakultät.
    8. Stadtler, Hartmut, 2003. "Multilevel lot sizing with setup times and multiple constrained resources: Internally rolling schedules with lot-sizing windows," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 20204, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    9. Hartmut Stadtler, 2003. "Multilevel Lot Sizing with Setup Times and Multiple Constrained Resources: Internally Rolling Schedules with Lot-Sizing Windows," Operations Research, INFORMS, vol. 51(3), pages 487-502, June.
    10. Anantaram Balakrishnan & Joseph Geunes, 2000. "Requirements Planning with Substitutions: Exploiting Bill-of-Materials Flexibility in Production Planning," Manufacturing & Service Operations Management, INFORMS, vol. 2(2), pages 166-185, January.
    11. Haase, Knut & Kimms, Alf, 2000. "Lot sizing and scheduling with sequence-dependent setup costs and times and efficient rescheduling opportunities," International Journal of Production Economics, Elsevier, vol. 66(2), pages 159-169, June.
    12. 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.
    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. Rohaninejad, Mohammad & Hanzálek, Zdeněk, 2023. "Multi-level lot-sizing and job shop scheduling with lot-streaming: Reformulation and solution approaches," International Journal of Production Economics, Elsevier, vol. 263(C).
    2. Zhu, Yongqiu & Goverde, Rob M.P., 2020. "Integrated timetable rescheduling and passenger reassignment during railway disruptions," Transportation Research Part B: Methodological, Elsevier, vol. 140(C), pages 282-314.
    3. Rakiz, Asma & Absi, Nabil & Fenies, Pierre, 2023. "Comparing approaches for a multi-level planning problem in a mining industry," International Journal of Production Economics, Elsevier, vol. 265(C).
    4. Rasmus Ø. Mikkelsen & Dennis S. Holm, 2022. "A parallelized matheuristic for the International Timetabling Competition 2019," Journal of Scheduling, Springer, vol. 25(4), pages 429-452, August.
    5. Hashemi-Petroodi, S. Ehsan & Thevenin, Simon & Kovalev, Sergey & Dolgui, Alexandre, 2022. "Model-dependent task assignment in multi-manned mixed-model assembly lines with walking workers," Omega, Elsevier, vol. 113(C).
    6. Guo, Peng & Weidinger, Felix & Boysen, Nils, 2019. "Parallel machine scheduling with job synchronization to enable efficient material flows in hub terminals," Omega, Elsevier, vol. 89(C), pages 110-121.
    7. 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.
    8. Xiao, Yiyong & Zhang, Renqian & Zhao, Qiuhong & Kaku, Ikou & Xu, Yuchun, 2014. "A variable neighborhood search with an effective local search for uncapacitated multilevel lot-sizing problems," European Journal of Operational Research, Elsevier, vol. 235(1), pages 102-114.

    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. Sereshti, Narges & Adulyasak, Yossiri & Jans, Raf, 2024. "Managing flexibility in stochastic multi-level lot sizing problem with service level constraints," Omega, Elsevier, vol. 122(C).
    2. Tao Wu, 2022. "Predictive Search for Capacitated Multi-Item Lot Sizing Problems," INFORMS Journal on Computing, INFORMS, vol. 34(1), pages 385-406, January.
    3. Marcos Mansano Furlan & Maristela Oliveira Santos, 2017. "BFO: a hybrid bees algorithm for the multi-level capacitated lot-sizing problem," Journal of Intelligent Manufacturing, Springer, vol. 28(4), pages 929-944, April.
    4. Daniel Quadt & Heinrich Kuhn, 2009. "Capacitated lot‐sizing and scheduling with parallel machines, back‐orders, and setup carry‐over," Naval Research Logistics (NRL), John Wiley & Sons, vol. 56(4), pages 366-384, June.
    5. Wei, Mingyuan & Qi, Mingyao & Wu, Tao & Zhang, Canrong, 2019. "Distance and matching-induced search algorithm for the multi-level lot-sizing problem with substitutable bill of materials," European Journal of Operational Research, Elsevier, vol. 277(2), pages 521-541.
    6. Absi, Nabil & van den Heuvel, Wilco, 2019. "Worst case analysis of Relax and Fix heuristics for lot-sizing problems," European Journal of Operational Research, Elsevier, vol. 279(2), pages 449-458.
    7. Ahmed Senoussi & Youcef Boutarfa & Nadjib Brahimi & Tarik Aouam, 2024. "Sustainable Hybrid Manufacturing and Refurbishing Systems with Substitution," Sustainability, MDPI, vol. 16(17), pages 1-33, August.
    8. 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.
    9. Schmid, Verena & Doerner, Karl F. & Laporte, Gilbert, 2013. "Rich routing problems arising in supply chain management," European Journal of Operational Research, Elsevier, vol. 224(3), pages 435-448.
    10. Tao Wu & Leyuan Shi & Joseph Geunes & Kerem Akartunalı, 2012. "On the equivalence of strong formulations for capacitated multi-level lot sizing problems with setup times," Journal of Global Optimization, Springer, vol. 53(4), pages 615-639, August.
    11. Helber, Stefan & Sahling, Florian, 2010. "A fix-and-optimize approach for the multi-level capacitated lot sizing problem," International Journal of Production Economics, Elsevier, vol. 123(2), pages 247-256, February.
    12. Kristin Uggen & Marte Fodstad & Vibeke Nørstebø, 2013. "Using and extending fix-and-relax to solve maritime inventory routing problems," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 21(2), pages 355-377, July.
    13. Guido, Rosita & Groccia, Maria Carmela & Conforti, Domenico, 2018. "An efficient matheuristic for offline patient-to-bed assignment problems," European Journal of Operational Research, Elsevier, vol. 268(2), pages 486-503.
    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. Wu, Tao & Shi, Leyuan & Geunes, Joseph & AkartunalI, Kerem, 2011. "An optimization framework for solving capacitated multi-level lot-sizing problems with backlogging," European Journal of Operational Research, Elsevier, vol. 214(2), pages 428-441, October.
    16. Chen, Haoxun, 2015. "Fix-and-optimize and variable neighborhood search approaches for multi-level capacitated lot sizing problems," Omega, Elsevier, vol. 56(C), pages 25-36.
    17. Nadjib Brahimi & Tarik Aouam, 2016. "Multi-item production routing problem with backordering: a MILP approach," International Journal of Production Research, Taylor & Francis Journals, vol. 54(4), pages 1076-1093, February.
    18. Tao Wu & Leyuan Shi & Jie Song, 2012. "An MIP-based interval heuristic for the capacitated multi-level lot-sizing problem with setup times," Annals of Operations Research, Springer, vol. 196(1), pages 635-650, July.
    19. Gislaine Mara Melega & Silvio Alexandre de Araujo & Reinaldo Morabito, 2020. "Mathematical model and solution approaches for integrated lot-sizing, scheduling and cutting stock problems," Annals of Operations Research, Springer, vol. 295(2), pages 695-736, December.
    20. Correa, Renata Naoko & Scarpin, Cassius Tadeu & Ferrari, Linamara Smaniotto & Arce, Julio Eduardo, 2020. "Application of relax-and-fix heuristic in the aggregation of stands for tactical forest scheduling," Forest Policy and Economics, Elsevier, vol. 119(C).

    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:214:y:2011:i:3:p:595-605. 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.