IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v60y2012i4p918-935.html
   My bibliography  Save this article

A Polyhedral Study of Multiechelon Lot Sizing with Intermediate Demands

Author

Listed:
  • Minjiao Zhang

    (Department of Integrated Systems Engineering, The Ohio State University, Columbus, Ohio 43210)

  • Simge Küçükyavuz

    (Department of Integrated Systems Engineering, The Ohio State University, Columbus, Ohio 43210)

  • Hande Yaman

    (Department of Industrial Engineering, Bilkent University, Ankara, Turkey)

Abstract

In this paper, we study a multiechelon uncapacitated lot-sizing problem in series ( m -ULS), where the output of the intermediate echelons has its own external demand and is also an input to the next echelon. We propose a polynomial-time dynamic programming algorithm, which gives a tight, compact extended formulation for the two-echelon case (2-ULS). Next, we present a family of valid inequalities for m -ULS, show its strength, and give a polynomial-time separation algorithm. We establish a hierarchy between the alternative formulations for 2-ULS. In particular, we show that our valid inequalities can be obtained from the projection of the multicommodity formulation. Our computational results show that this extended formulation is very effective in solving our uncapacitated multi-item two-echelon test problems. In addition, for capacitated multi-item, multiechelon problems, we demonstrate the effectiveness of a branch-and-cut algorithm using the proposed inequalities.

Suggested Citation

  • Minjiao Zhang & Simge Küçükyavuz & Hande Yaman, 2012. "A Polyhedral Study of Multiechelon Lot Sizing with Intermediate Demands," Operations Research, INFORMS, vol. 60(4), pages 918-935, August.
    • Handle: RePEc:inm:oropre:v:60:y:2012:i:4:p:918-935
    DOI: 10.1287/opre.1120.1058
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1120.1058
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.1120.1058?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
    ---><---

    References listed on IDEAS

    as
    1. 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.
    2. 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).
    3. POCHET, Yves & WOLSEY, Laurence A., 1988. "Lot-size models with backlogging: strong reformulations and cutting planes," LIDAM Reprints CORE 791, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    4. Francesco Gaglioppa & Lisa A. Miller & Saif Benjaafar, 2008. "Multitask and Multistage Production Planning and Scheduling for Process Industries," Operations Research, INFORMS, vol. 56(4), pages 1010-1025, August.
    5. Albert Wagelmans & Stan van Hoesel & Antoon Kolen, 1992. "Economic Lot Sizing: An O(n log n) Algorithm That Runs in Linear Time in the Wagner-Whitin Case," Operations Research, INFORMS, vol. 40(1-supplem), pages 145-156, February.
    6. WOLSEY, Laurence A., 2002. "Solving multi-item lot-sizing problems with an MIP solver using classification and reformulation," LIDAM Reprints CORE 1605, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    7. Willard I. Zangwill, 1968. "Minimum Concave Cost Flows in Certain Networks," Management Science, INFORMS, vol. 14(7), pages 429-450, March.
    8. BARANY, Imre & VAN ROY, Tony & WOLSEY, Laurence A., 1984. "Uncapacitated lot-sizing: the convex hull of solutions," LIDAM Reprints CORE 605, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    9. BELVAUX, Gaëtan & WOLSEY, Laurence A., 2000. "bc-prod: A specialized branch-and-cut system for lot-sizing problems," LIDAM Reprints CORE 1455, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    10. WOLSEY, Laurence, 2002. "Solving multi-item lot-sizing problems with an MIP solver using classification and reformulation," LIDAM Discussion Papers CORE 2002012, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    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. 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.
    13. 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.
    14. POCHET, Yves & WOLSEY, Laurence A., 1993. "Lot-sizing with constant batches: formulation and valid inequalities," LIDAM Reprints CORE 1066, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    15. Laurence A. Wolsey, 2002. "Solving Multi-Item Lot-Sizing Problems with an MIP Solver Using Classification and Reformulation," Management Science, INFORMS, vol. 48(12), pages 1587-1602, December.
    16. Arthur F. Veinott, 1969. "Minimum Concave-Cost Solution of Leontief Substitution Models of Multi-Facility Inventory Systems," Operations Research, INFORMS, vol. 17(2), pages 262-291, April.
    17. Rardin, Ronald L. & Wolsey, Laurence A., 1993. "Valid inequalities and projecting the multicommodity extended formulation for uncapacitated fixed charge network flow problems," European Journal of Operational Research, Elsevier, vol. 71(1), pages 95-109, November.
    18. R. Kipp Martin, 1987. "Generating Alternative Mixed-Integer Programming Models Using Variable Redefinition," Operations Research, INFORMS, vol. 35(6), pages 820-831, December.
    19. Gaetan Belvaux & Laurence A. Wolsey, 2000. "bc --- prod: A Specialized Branch-and-Cut System for Lot-Sizing Problems," Management Science, INFORMS, vol. 46(5), pages 724-738, May.
    20. 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.
    21. Stephen F. Love, 1972. "A Facilities in Series Inventory Model with Nested Schedules," Management Science, INFORMS, vol. 18(5-Part-1), pages 327-338, January.
    22. 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.
    23. MELO, Rafael A. & WOLSEY, Laurence A., 2010. "Uncapacitated two-level lot-sizing," LIDAM Reprints CORE 2235, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    24. Alok Aggarwal & James K. Park, 1993. "Improved Algorithms for Economic Lot Size Problems," Operations Research, INFORMS, vol. 41(3), pages 549-571, June.
    25. Chung-Yee Lee & Sila Çetinkaya & Wikrom Jaruphongsa, 2003. "A Dynamic Model for Inventory Lot Sizing and Outbound Shipment Scheduling at a Third-Party Warehouse," Operations Research, INFORMS, vol. 51(5), pages 735-747, October.
    26. 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.
    27. Yves Pochet & Laurence A. Wolsey, 1993. "Lot-Sizing with Constant Batches: Formulation and Valid Inequalities," Mathematics of Operations Research, INFORMS, vol. 18(4), pages 767-785, November.
    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. 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.
    2. Siao-Leu Phouratsamay & Safia Kedad-Sidhoum & Fanny Pascual, 2021. "Coordination of a two-level supply chain with contracts," 4OR, Springer, vol. 19(2), pages 235-264, June.
    3. Cunha, Jesus O. & Melo, Rafael A., 2021. "Valid inequalities, preprocessing, and an effective heuristic for the uncapacitated three-level lot-sizing and replenishment problem with a distribution structure," European Journal of Operational Research, Elsevier, vol. 295(3), pages 874-892.
    4. Jesus Cunha & Rafael Melo, 2016. "On reformulations for the one-warehouse multi-retailer problem," Annals of Operations Research, Springer, vol. 238(1), pages 99-122, March.
    5. Pham, An & Jin, Tongdan & Novoa, Clara & Qin, Jin, 2019. "A multi-site production and microgrid planning model for net-zero energy operations," International Journal of Production Economics, Elsevier, vol. 218(C), pages 260-274.
    6. Kajjoune, Oussama & Aouam, Tarik & Zouadi, Tarik & Ranjan, Ravi Prakash, 2023. "Dynamic lot-sizing in a two-stage supply chain with liquidity constraints and financing options," International Journal of Production Economics, Elsevier, vol. 258(C).
    7. Farhat, Mlouka & Akbalik, Ayse & Hadj-Alouane, Atidel B. & Sauer, Nathalie, 2019. "Lot sizing problem with batch ordering under periodic buyback contract and lost sales," International Journal of Production Economics, Elsevier, vol. 208(C), pages 500-511.
    8. Ming Zhao & Minjiao Zhang, 2020. "Multiechelon Lot Sizing: New Complexities and Inequalities," Operations Research, INFORMS, vol. 68(2), pages 534-551, March.
    9. Chitsaz, Masoud & Cordeau, Jean-François & Jans, Raf, 2020. "A branch-and-cut algorithm for an assembly routing problem," European Journal of Operational Research, Elsevier, vol. 282(3), pages 896-910.
    10. 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.
    11. 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.
    12. Jesus O. Cunha & Rafael A. Melo, 2016. "On reformulations for the one-warehouse multi-retailer problem," Annals of Operations Research, Springer, vol. 238(1), pages 99-122, March.
    13. Wolfgang Albrecht & Martin Steinrücke, 2020. "Continuous-time scheduling of production, distribution and sales in photovoltaic supply chains with declining prices," Flexible Services and Manufacturing Journal, Springer, vol. 32(3), pages 629-667, September.
    14. 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.
    15. Gajpal, Yuvraj & Nourelfath, Mustapha, 2015. "Two efficient heuristics to solve the integrated load distribution and production planning problem," Reliability Engineering and System Safety, Elsevier, vol. 144(C), pages 204-214.
    16. 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.

    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. 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.
    2. 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.
    3. 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.
    4. Ming Zhao & Minjiao Zhang, 2020. "Multiechelon Lot Sizing: New Complexities and Inequalities," Operations Research, INFORMS, vol. 68(2), pages 534-551, March.
    5. Alper Atamtürk & Simge Küçükyavuz, 2005. "Lot Sizing with Inventory Bounds and Fixed Costs: Polyhedral Study and Computation," Operations Research, INFORMS, vol. 53(4), pages 711-730, August.
    6. Laurence A. Wolsey, 2002. "Solving Multi-Item Lot-Sizing Problems with an MIP Solver Using Classification and Reformulation," Management Science, INFORMS, vol. 48(12), pages 1587-1602, December.
    7. 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.
    8. 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.
    9. Wolsey, Laurence A., 1995. "Progress with single-item lot-sizing," European Journal of Operational Research, Elsevier, vol. 86(3), pages 395-401, November.
    10. 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.
    11. 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.
    12. Yongpei Guan & Andrew J. Miller, 2008. "Polynomial-Time Algorithms for Stochastic Uncapacitated Lot-Sizing Problems," Operations Research, INFORMS, vol. 56(5), pages 1172-1183, October.
    13. VAN VYVE, Mathieu & WOLSEY, Laurence & YAMAN, Hande, 2012. "Relaxations for two-level multi-item lot-sizing problem," LIDAM Discussion Papers CORE 2012031, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    14. Hark-Chin Hwang, 2010. "Economic Lot-Sizing for Integrated Production and Transportation," Operations Research, INFORMS, vol. 58(2), pages 428-444, April.
    15. 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.
    16. Hark-Chin Hwang, 2009. "Inventory Replenishment and Inbound Shipment Scheduling Under a Minimum Replenishment Policy," Transportation Science, INFORMS, vol. 43(2), pages 244-264, May.
    17. Francesco Gaglioppa & Lisa A. Miller & Saif Benjaafar, 2008. "Multitask and Multistage Production Planning and Scheduling for Process Industries," Operations Research, INFORMS, vol. 56(4), pages 1010-1025, August.
    18. 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.
    19. Hark-Chin Hwang & Wilco van den Heuvel & Albert P. M. Wagelmans, 2023. "Multilevel Lot-Sizing with Inventory Bounds," INFORMS Journal on Computing, INFORMS, vol. 35(6), pages 1470-1490, November.
    20. Jans, R.F., 2006. "Solving Lotsizing Problems on Parallel Identical Machines Using Symmetry Breaking Constraints," ERIM Report Series Research in Management ERS-2006-051-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.

    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:inm:oropre:v:60:y:2012:i:4:p:918-935. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.