IDEAS home Printed from https://ideas.repec.org/a/eee/proeco/v140y2012i1p249-255.html
   My bibliography  Save this article

A Lagrangian relaxation based approach for the capacitated lot sizing problem in closed-loop supply chain

Author

Listed:
  • Zhang, Zhi-Hai
  • Jiang, Hai
  • Pan, Xunzhang

Abstract

This paper investigates the capacitated lot sizing problem in closed-loop supply chain considering setup costs, product returns, and remanufacturing. We formulate the problem as a mixed integer program and propose a Lagrangian relaxation-based solution approach. The resulting Lagrangian subproblems are then solved by polynomial time algorithms. Compared to existing solution methods in the literature, our Lagrangian relaxation based approach is advantageous in that it naturally provides a lower bound on the optimal objective function value, which allows us to assess the quality of solutions found. Numerical experiments using synthesized data demonstrate that our approach can find quality solutions efficiently.

Suggested Citation

  • Zhang, Zhi-Hai & Jiang, Hai & Pan, Xunzhang, 2012. "A Lagrangian relaxation based approach for the capacitated lot sizing problem in closed-loop supply chain," International Journal of Production Economics, Elsevier, vol. 140(1), pages 249-255.
    • Handle: RePEc:eee:proeco:v:140:y:2012:i:1:p:249-255
    DOI: 10.1016/j.ijpe.2012.01.018
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0925527312000205
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ijpe.2012.01.018?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. Hop, Nguyen Van & Tabucanon, Mario T., 2005. "Adaptive genetic algorithm for lot-sizing problem with self-adjustment operation rate," International Journal of Production Economics, Elsevier, vol. 98(2), pages 129-135, November.
    2. William W. Trigeiro & L. Joseph Thomas & John O. McClain, 1989. "Capacitated Lot Sizing with Setup Times," Management Science, INFORMS, vol. 35(3), pages 353-366, March.
    3. 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.
    4. Marshall L. Fisher, 2004. "The Lagrangian Relaxation Method for Solving Integer Programming Problems," Management Science, INFORMS, vol. 50(12_supple), pages 1861-1871, December.
    5. 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.
    6. Cárdenas-Barrón, Leopoldo Eduardo, 2010. "Adaptive genetic algorithm for lot-sizing problem with self-adjustment operation rate: A discussion," International Journal of Production Economics, Elsevier, vol. 123(1), pages 243-245, January.
    7. Harvey M. Wagner & Thomson M. Whitin, 1958. "Dynamic Version of the Economic Lot Size Model," Management Science, INFORMS, vol. 5(1), pages 89-96, October.
    8. 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.
    9. Li, Yongjian & Chen, Jian & Cai, Xiaoqiang, 2007. "Heuristic genetic algorithm for capacitated production planning problems with batch processing and remanufacturing," International Journal of Production Economics, Elsevier, vol. 105(2), pages 301-317, February.
    10. Sancak, Emre & Salman, F. Sibel, 2011. "Multi-item dynamic lot-sizing with delayed transportation policy," International Journal of Production Economics, Elsevier, vol. 131(2), pages 595-603, June.
    11. Toledo, Franklina Maria Bragion & Armentano, Vinicius Amaral, 2006. "A Lagrangian-based heuristic for the capacitated lot-sizing problem in parallel machines," European Journal of Operational Research, Elsevier, vol. 175(2), pages 1070-1083, December.
    12. Brahimi, Nadjib & Dauzere-Peres, Stephane & Najid, Najib M. & Nordli, Atle, 2006. "Single item lot sizing problems," European Journal of Operational Research, Elsevier, vol. 168(1), pages 1-16, January.
    13. Süral, Haldun & Denizel, Meltem & Van Wassenhove, Luk N., 2009. "Lagrangean relaxation based heuristics for lot sizing with setup times," European Journal of Operational Research, Elsevier, vol. 194(1), pages 51-63, April.
    14. Awi Federgruen & Michal Tzur, 1991. "A Simple Forward Algorithm to Solve General Dynamic Lot Sizing Models with n Periods in 0(n log n) or 0(n) Time," Management Science, INFORMS, vol. 37(8), pages 909-925, August.
    15. Marshall L. Fisher, 2004. "Comments on ÜThe Lagrangian Relaxation Method for Solving Integer Programming ProblemsÝ," Management Science, INFORMS, vol. 50(12_supple), pages 1872-1874, December.
    16. Alok Aggarwal & James K. Park, 1993. "Improved Algorithms for Economic Lot Size Problems," Operations Research, INFORMS, vol. 41(3), pages 549-571, June.
    17. Pan, Zhendong & Tang, Jiafu & Liu, Ou, 2009. "Capacitated dynamic lot sizing problems in closed-loop supply chain," European Journal of Operational Research, Elsevier, vol. 198(3), pages 810-821, November.
    18. Piñeyro, Pedro & Viera, Omar, 2010. "The economic lot-sizing problem with remanufacturing and one-way substitution," International Journal of Production Economics, Elsevier, vol. 124(2), pages 482-488, April.
    19. van den Heuvel, W. & Wagelmans, A.P.M., 2007. "Four equivalent lot-sizing models," Econometric Institute Research Papers EI 2007-30, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    20. Liu, Tieming, 2008. "Economic lot sizing problem with inventory bounds," European Journal of Operational Research, Elsevier, vol. 185(1), pages 204-215, February.
    21. M. Florian & J. K. Lenstra & A. H. G. Rinnooy Kan, 1980. "Deterministic Production Planning: Algorithms and Complexity," Management Science, INFORMS, vol. 26(7), pages 669-679, July.
    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. Wu, Xin & Nie, Lei & Xu, Meng & Zhao, Lili, 2019. "Distribution planning problem for a high-speed rail catering service considering time-varying demands and pedestrian congestion: A lot-sizing-based model and decomposition algorithm," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 123(C), pages 61-89.
    2. Rowshannahad, Mehdi & Absi, Nabil & Dauzère-Pérès, Stéphane & Cassini, Bernard, 2018. "Multi-item bi-level supply chain planning with multiple remanufacturing of reusable by-products," International Journal of Production Economics, Elsevier, vol. 198(C), pages 25-37.
    3. Brahimi, Nadjib & Absi, Nabil & Dauzère-Pérès, Stéphane & Nordli, Atle, 2017. "Single-item dynamic lot-sizing problems: An updated survey," European Journal of Operational Research, Elsevier, vol. 263(3), pages 838-863.
    4. G. Rius-Sorolla & J. Maheut & Jairo R. Coronado-Hernandez & J. P. Garcia-Sabater, 2020. "Lagrangian relaxation of the generic materials and operations planning model," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 28(1), pages 105-123, March.
    5. Andreas Goerler & Stefan Voß, 2016. "Dynamic lot-sizing with rework of defective items and minimum lot-size constraints," International Journal of Production Research, Taylor & Francis Journals, vol. 54(8), pages 2284-2297, April.
    6. Felix T.S. Chan & Nan Li & S.H. Chung & Mozafar Saadat, 2017. "Management of sustainable manufacturing systems-a review on mathematical problems," International Journal of Production Research, Taylor & Francis Journals, vol. 55(4), pages 1210-1225, February.
    7. Özceylan, Eren & Paksoy, Turan & Bektaş, Tolga, 2014. "Modeling and optimizing the integrated problem of closed-loop supply chain network design and disassembly line balancing," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 61(C), pages 142-164.
    8. Liu, Kanglin & Zhang, Zhi-Hai, 2018. "Capacitated disassembly scheduling under stochastic yield and demand," European Journal of Operational Research, Elsevier, vol. 269(1), pages 244-257.
    9. Dhahri, Akrem & Gharbi, Ali & Ouhimmou, Mustapha, 2022. "Integrated production-delivery control policy for an unreliable manufacturing system and multiple retailers," International Journal of Production Economics, Elsevier, vol. 245(C).
    10. Suzanne, Elodie & Absi, Nabil & Borodin, Valeria, 2020. "Towards circular economy in production planning: Challenges and opportunities," European Journal of Operational Research, Elsevier, vol. 287(1), pages 168-190.
    11. Chen, Jen-Ming & Chang, Chia-I, 2013. "Dynamic pricing for new and remanufactured products in a closed-loop supply chain," International Journal of Production Economics, Elsevier, vol. 146(1), pages 153-160.
    12. S. Saha & S.P. Sarmah & Ilkyeong Moon, 2016. "Dual channel closed-loop supply chain coordination with a reward-driven remanufacturing policy," International Journal of Production Research, Taylor & Francis Journals, vol. 54(5), pages 1503-1517, March.
    13. Huang, Min & Song, Min & Lee, Loo Hay & Ching, Wai Ki, 2013. "Analysis for strategy of closed-loop supply chain with dual recycling channel," International Journal of Production Economics, Elsevier, vol. 144(2), pages 510-520.
    14. Yongjian Li & Xiaoqiang Cai & Lei Xu & Wenxia Yang, 2016. "Heuristic approach on dynamic lot-sizing model for durable products with end-of-use constraints," Annals of Operations Research, Springer, vol. 242(2), pages 265-283, July.

    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. Chung-Lun Li & Qingying Li, 2016. "Polynomial-Time Solvability of Dynamic Lot Size Problems," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 33(03), pages 1-20, June.
    2. Brahimi, Nadjib & Absi, Nabil & Dauzère-Pérès, Stéphane & Nordli, Atle, 2017. "Single-item dynamic lot-sizing problems: An updated survey," European Journal of Operational Research, Elsevier, vol. 263(3), pages 838-863.
    3. 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.
    4. Fink, Jiří & Hurink, Johann L., 2015. "Minimizing costs is easier than minimizing peaks when supplying the heat demand of a group of houses," European Journal of Operational Research, Elsevier, vol. 242(2), pages 644-650.
    5. 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.
    6. 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.
    7. 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.
    8. Brahimi, Nadjib & Dauzere-Peres, Stephane & Najid, Najib M. & Nordli, Atle, 2006. "Single item lot sizing problems," European Journal of Operational Research, Elsevier, vol. 168(1), pages 1-16, January.
    9. 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.
    10. Ming Zhao & Minjiao Zhang, 2020. "Multiechelon Lot Sizing: New Complexities and Inequalities," Operations Research, INFORMS, vol. 68(2), pages 534-551, March.
    11. Stan van Hoesel & H. Edwin Romeijn & Dolores Romero Morales & Albert P. M. Wagelmans, 2005. "Integrated Lot Sizing in Serial Supply Chains with Production Capacities," Management Science, INFORMS, vol. 51(11), pages 1706-1719, November.
    12. 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.
    13. Hark‐Chin Hwang & Wilco van den Heuvel, 2012. "Improved algorithms for a lot‐sizing problem with inventory bounds and backlogging," Naval Research Logistics (NRL), John Wiley & Sons, vol. 59(3‐4), pages 244-253, April.
    14. 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.
    15. Goisque, Guillaume & Rapine, Christophe, 2017. "An efficient algorithm for the 2-level capacitated lot-sizing problem with identical capacities at both levels," European Journal of Operational Research, Elsevier, vol. 261(3), pages 918-928.
    16. van Hoesel, C.P.M. & Romeijn, H.E. & Romero Morales, M.D. & Wagelmans, A., 2002. "Polynomial time algorithms for some multi-level lot-sizing problems with production capacities," Research Memorandum 018, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    17. 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.
    18. Alper Atamtürk & Dorit S. Hochbaum, 2001. "Capacity Acquisition, Subcontracting, and Lot Sizing," Management Science, INFORMS, vol. 47(8), pages 1081-1100, August.
    19. Jean-Philippe Gayon & Guillaume Massonnet & Christophe Rapine & Gautier Stauffer, 2017. "Fast Approximation Algorithms for the One-Warehouse Multi-Retailer Problem Under General Cost Structures and Capacity Constraints," Mathematics of Operations Research, INFORMS, vol. 42(3), pages 854-875, August.
    20. José M. Gutiérrez & Beatriz Abdul-Jalbar & Joaquín Sicilia & Inmaculada Rodríguez-Martín, 2021. "Effective Algorithms for the Economic Lot-Sizing Problem with Bounded Inventory and Linear Fixed-Charge Cost Structure," Mathematics, MDPI, vol. 9(6), pages 1-21, 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:proeco:v:140:y:2012:i:1:p:249-255. 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/ijpe .

    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.