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

A reduced variable neighborhood search algorithm for uncapacitated multilevel lot-sizing problems

Author

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

Abstract

Multilevel lot-sizing (MLLS) problems, which involve complicated product structures with interdependence among the items, play an important role in the material requirement planning (MRP) system of modern manufacturing/assembling lines. In this paper, we present a reduced variable neighborhood search (RVNS) algorithm and several implemental techniques for solving uncapacitated MLLS problems. Computational experiments are carried out on three classes of benchmark instances under different scales (small, medium, and large). Compared with the existing literature, RVNS shows good performance and robustness on a total of 176 tested instances. For the 96 small-sized instances, the RVNS algorithm can find 100% of the optimal solutions in less computational time; for the 40 medium-sized and the 40 large-sized instances, the RVNS algorithm is competitive against other methods, enjoying good effectiveness as well as high computational efficiency. In the calculations, RVNS updated 7 (17.5%) best known solutions for the medium-sized instances and 16 (40%) best known solutions for the large-sized instances.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:214:y:2011:i:2:p:223-231
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221711003596
    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. Willard I. Zangwill, 1968. "Minimum Concave Cost Flows in Certain Networks," Management Science, INFORMS, vol. 14(7), pages 429-450, March.
    2. 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.
    3. Hansen, Pierre & Mladenovic, Nenad, 2001. "Variable neighborhood search: Principles and applications," European Journal of Operational Research, Elsevier, vol. 130(3), pages 449-467, May.
    4. Earle Steinberg & H. Albert Napier, 1980. "Optimal Multi-Level Lot Sizing for Requirements Planning Systems," Management Science, INFORMS, vol. 26(12), pages 1258-1271, December.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. Panayotis Afentakis & Bezalel Gavish, 1986. "Optimal Lot-Sizing Algorithms for Complex Product Structures," Operations Research, INFORMS, vol. 34(2), pages 237-249, April.
    10. Tang, Ou, 2004. "Simulated annealing in lot sizing problems," International Journal of Production Economics, Elsevier, vol. 88(2), pages 173-181, March.
    11. 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.
    12. 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.
    13. 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.
    14. 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. Patrícia Lopes Costa & Ana Margarida Graça & Pedro Marques-Quinteiro & Catarina Marques Santos & António Caetano & Ana Margarida Passos, 2013. "Multilevel Research in the Field of Organizational Behavior," SAGE Open, , vol. 3(3), pages 21582440134, August.
    2. 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.
    3. Devika, K. & Jafarian, A. & Nourbakhsh, V., 2014. "Designing a sustainable closed-loop supply chain network based on triple bottom line approach: A comparison of metaheuristics hybridization techniques," European Journal of Operational Research, Elsevier, vol. 235(3), pages 594-615.
    4. 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.

    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 & 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.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    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. 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.
    13. Wolsey, Laurence A., 1995. "Progress with single-item lot-sizing," European Journal of Operational Research, Elsevier, vol. 86(3), pages 395-401, November.
    14. 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.
    15. 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).
    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:214:y:2011:i:2:p:223-231. 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.