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

A variable neighborhood search with an effective local search for uncapacitated multilevel lot-sizing problems

Author

Listed:
  • Xiao, Yiyong
  • Zhang, Renqian
  • Zhao, Qiuhong
  • Kaku, Ikou
  • Xu, Yuchun

Abstract

In this study, we improved the variable neighborhood search (VNS) algorithm for solving uncapacitated multilevel lot-sizing (MLLS) problems. The improvement is twofold. First, we developed an effective local search method known as the Ancestors Depth-first Traversal Search (ADTS), which can be embedded in the VNS to significantly improve the solution quality. Second, we proposed a common and efficient approach for the rapid calculation of the cost change for the VNS and other generate-and-test algorithms. The new VNS algorithm was tested against 176 benchmark problems of different scales (small, medium, and large). The experimental results show that the new VNS algorithm outperforms all of the existing algorithms in the literature for solving uncapacitated MLLS problems because it was able to find all optimal solutions (100%) for 96 small-sized problems and new best-known solutions for 5 of 40 medium-sized problems and for 30 of 40 large-sized problems.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:235:y:2014:i:1:p:102-114
    DOI: 10.1016/j.ejor.2013.10.025
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221713008485
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2013.10.025?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. Mladenović, Nenad & Kratica, Jozef & Kovačević-Vujčić, Vera & Čangalović, Mirjana, 2012. "Variable neighborhood search for metric dimension and minimal doubly resolving set problems," European Journal of Operational Research, Elsevier, vol. 220(2), pages 328-337.
    2. 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.
    3. Willard I. Zangwill, 1968. "Minimum Concave Cost Flows in Certain Networks," Management Science, INFORMS, vol. 14(7), pages 429-450, March.
    4. Joseph D. Blackburn & Robert A. Millen, 1982. "Improved Heuristics for Multi-Stage Requirements Planning Systems," Management Science, INFORMS, vol. 28(1), pages 44-56, January.
    5. Hansen, Pierre & Mladenovic, Nenad, 2001. "Variable neighborhood search: Principles and applications," European Journal of Operational Research, Elsevier, vol. 130(3), pages 449-467, May.
    6. Mladenović, Nenad & Urošević, Dragan & Hanafi, Saı¨d & Ilić, Aleksandar, 2012. "A general variable neighborhood search for the one-commodity pickup-and-delivery travelling salesman problem," European Journal of Operational Research, Elsevier, vol. 220(1), pages 270-285.
    7. Harvey M. Wagner & Thomson M. Whitin, 2004. "Dynamic Version of the Economic Lot Size Model," Management Science, INFORMS, vol. 50(12_supple), pages 1770-1774, December.
    8. 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.
    9. Wallace B. Crowston & Michael H. Wagner, 1973. "Dynamic Lot Size Models for Multi-Stage Assembly Systems," Management Science, INFORMS, vol. 20(1), pages 14-21, September.
    10. Harvey M. Wagner, 2004. "Comments on ÜDynamic Version of the Economic Lot Size ModelÝ," Management Science, INFORMS, vol. 50(12_supple), pages 1775-1777, December.
    11. Dellaert, N. & Jeunet, J. & Jonard, N., 2000. "A genetic algorithm to solve the general multi-level lot-sizing problem with time-varying costs," International Journal of Production Economics, Elsevier, vol. 68(3), pages 241-257, December.
    12. Panayotis Afentakis & Bezalel Gavish, 1986. "Optimal Lot-Sizing Algorithms for Complex Product Structures," Operations Research, INFORMS, vol. 34(2), pages 237-249, April.
    13. Tang, Ou, 2004. "Simulated annealing in lot sizing problems," International Journal of Production Economics, Elsevier, vol. 88(2), pages 173-181, March.
    14. Xiao, Yiyong & Kaku, Ikou & Zhao, Qiuhong & Zhang, Renqian, 2011. "A reduced variable neighborhood search algorithm for uncapacitated multilevel lot-sizing problems," European Journal of Operational Research, Elsevier, vol. 214(2), pages 223-231, October.
    15. Hansen, Pierre & Mladenovic, Nenad & Moreno Pérez, Jos´e A., 2008. "Variable neighborhood search," European Journal of Operational Research, Elsevier, vol. 191(3), pages 593-595, December.
    16. Jörg Homberger, 2008. "A Parallel Genetic Algorithm for the Multilevel Unconstrained Lot-Sizing Problem," INFORMS Journal on Computing, INFORMS, vol. 20(1), pages 124-132, February.
    17. Labadie, Nacima & Mansini, Renata & Melechovský, Jan & Wolfler Calvo, Roberto, 2012. "The Team Orienteering Problem with Time Windows: An LP-based Granular Variable Neighborhood Search," European Journal of Operational Research, Elsevier, vol. 220(1), pages 15-27.
    18. Willard I. Zangwill, 1969. "A Backlogging Model and a Multi-Echelon Model of a Dynamic Economic Lot Size Production System--A Network Approach," Management Science, INFORMS, vol. 15(9), pages 506-527, May.
    19. Panayotis Afentakis & Bezalel Gavish & Uday Karmarkar, 1984. "Computationally Efficient Optimal Solutions to the Lot-Sizing Problem in Multistage Assembly Systems," Management Science, INFORMS, vol. 30(2), pages 222-239, February.
    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. Boonmee, Atiwat & Sethanan, Kanchana, 2016. "A GLNPSO for multi-level capacitated lot-sizing and scheduling problem in the poultry industry," European Journal of Operational Research, Elsevier, vol. 250(2), pages 652-665.
    2. Zeng, Zhizhong & Yu, Xinguo & He, Kun & Huang, Wenqi & Fu, Zhanghua, 2016. "Iterated Tabu Search and Variable Neighborhood Descent for packing unequal circles into a circular container," European Journal of Operational Research, Elsevier, vol. 250(2), pages 615-627.
    3. Yiyong Xiao & Abdullah Konak, 2017. "A variable neighborhood search for the network design problem with relays," Journal of Heuristics, Springer, vol. 23(2), pages 137-164, June.
    4. Yiyong Xiao & Meng You & Xiaorong Zuo & Shenghan Zhou & Xing Pan, 2018. "The Uncapacitatied Dynamic Single-Level Lot-Sizing Problem under a Time-Varying Environment and an Exact Solution Approach," Sustainability, MDPI, vol. 10(11), pages 1-14, October.
    5. Sifaleras, Angelo & Konstantaras, Ioannis & Mladenović, Nenad, 2015. "Variable neighborhood search for the economic lot sizing problem with product returns and recovery," International Journal of Production Economics, Elsevier, vol. 160(C), pages 133-143.
    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. Xiao, Yiyong & Konak, Abdullah, 2016. "The heterogeneous green vehicle routing and scheduling problem with time-varying traffic congestion," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 88(C), pages 146-166.
    8. Zhou, Shenghan & Zhou, Yuliang & Zuo, Xiaorong & Xiao, Yiyong & Cheng, Yang, 2018. "Modeling and solving the constrained multi-items lot-sizing problem with time-varying setup cost," Chaos, Solitons & Fractals, Elsevier, vol. 116(C), pages 202-207.
    9. Gansterer, Margaretha & Födermayr, Patrick & Hartl, Richard F., 2021. "The capacitated multi-level lot-sizing problem with distributed agents," International Journal of Production Economics, Elsevier, vol. 235(C).

    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. Xiao, Yiyong & Kaku, Ikou & Zhao, Qiuhong & Zhang, Renqian, 2011. "A reduced variable neighborhood search algorithm for uncapacitated multilevel lot-sizing problems," European Journal of Operational Research, Elsevier, vol. 214(2), pages 223-231, 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. Dellaert, N. P. & Jeunet, J., 2003. "Randomized multi-level lot-sizing heuristics for general product structures," European Journal of Operational Research, Elsevier, vol. 148(1), pages 211-228, July.
    4. Dellaert, N. & Jeunet, J. & Jonard, N., 2000. "A genetic algorithm to solve the general multi-level lot-sizing problem with time-varying costs," International Journal of Production Economics, Elsevier, vol. 68(3), pages 241-257, December.
    5. N.C. Simpson & S. Selcuk Erenguc, 2005. "Modeling multiple stage manufacturing systems with generalized costs and capacity issues," Naval Research Logistics (NRL), John Wiley & Sons, vol. 52(6), pages 560-570, September.
    6. Chu, Chi-Leung & Leon, V. Jorge, 2009. "Scalable methodology for supply chain inventory coordination with private information," European Journal of Operational Research, Elsevier, vol. 195(1), pages 262-279, May.
    7. Kimms, Alf & Drexl, Andreas, 1996. "Multi-level lot sizing: A literature survey," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 405, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    8. Grubbström, Robert W. & Tang, Ou, 2012. "The space of solution alternatives in the optimal lotsizing problem for general assembly systems applying MRP theory," International Journal of Production Economics, Elsevier, vol. 140(2), pages 765-777.
    9. Simpson, N. C., 1999. "Multiple level production planning in rolling horizon assembly environments," European Journal of Operational Research, Elsevier, vol. 114(1), pages 15-28, April.
    10. 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).
    11. Erenguc, S. Selcuk & Simpson, N. C. & Vakharia, Asoo J., 1999. "Integrated production/distribution planning in supply chains: An invited review," European Journal of Operational Research, Elsevier, vol. 115(2), pages 219-236, June.
    12. Xiao, Yiyong & Konak, Abdullah, 2016. "The heterogeneous green vehicle routing and scheduling problem with time-varying traffic congestion," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 88(C), pages 146-166.
    13. Gencer, Cevriye & Erol, Serpil & Erol, Yalcin, 1999. "A decision network algorithm for multi-stage dynamic lot sizing problems," International Journal of Production Economics, Elsevier, vol. 62(3), pages 281-285, September.
    14. Wolsey, Laurence A., 1995. "Progress with single-item lot-sizing," European Journal of Operational Research, Elsevier, vol. 86(3), pages 395-401, November.
    15. Joseph Geunes & H. Edwin Romeijn & Kevin Taaffe, 2006. "Requirements Planning with Pricing and Order Selection Flexibility," Operations Research, INFORMS, vol. 54(2), pages 394-401, April.
    16. Janssen, Larissa & Diabat, Ali & Sauer, Jürgen & Herrmann, Frank, 2018. "A stochastic micro-periodic age-based inventory replenishment policy for perishable goods," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 118(C), pages 445-465.
    17. Vernon Ning Hsu, 2000. "Dynamic Economic Lot Size Model with Perishable Inventory," Management Science, INFORMS, vol. 46(8), pages 1159-1169, August.
    18. Abraham Duarte & Eduardo G. Pardo, 2020. "Special issue on recent innovations in variable neighborhood search," Journal of Heuristics, Springer, vol. 26(3), pages 335-338, June.
    19. 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.
    20. Hark-Chin Hwang & Hyun-Soo Ahn & Philip Kaminsky, 2013. "Basis Paths and a Polynomial Algorithm for the Multistage Production-Capacitated Lot-Sizing Problem," Operations Research, INFORMS, vol. 61(2), pages 469-482, April.

    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:235:y:2014:i:1:p:102-114. 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.