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

On the Effectiveness of Zero-Inventory-Ordering Policies for the Economic Lot-Sizing Model with a Class of Piecewise Linear Cost Structures

Author

Listed:
  • Lap Mui Ann Chan

    (School of Management, University of Toronto, Toronto, Ontario, Canada M5S 3E6)

  • Ana Muriel

    (Department of Mechanical and Industrial Engineering, University of Massachusetts, Amherst, Massachusetts 01106)

  • Zuo-Jun Shen

    (Department of Industrial and Systems Engineering, University of Florida, Gainesville, Florida 32611)

  • David Simchi-Levi

    (The Engineering Systems Division and the Department of Civil and Environmental Engineering, Massachusetts Institute of Technology, Cambridge, Massachusetts 02142)

Abstract

We consider an economic lot-sizing problem with a special class of piecewise linear ordering costs, which we refer to as the class of modified all-unit discount cost functions. Such an ordering cost function represents transportation costs charged by many less-than truckload carriers. We show that even special cases of the lot-sizing problem are NP-hard and therefore analyze the effectiveness of easily implementable policies. In particular, we demonstrate that there exists a zero-inventory-ordering(ZIO) policy, i.e., a policy in which an order is placed only when the inventory level drops to zero, whose total inventory and ordering cost is no more than 4/3 times the optimal cost. Furthermore, if the ordering cost function does not vary over time, then the cost of the best ZIO policy is no more than 5.6/4.6 times the optimal cost. These results hold for any transportation and holding cost functions that satisfy the following properties: (i) they are non decreasing functions, and (ii) the associated cost per unit is non increasing. Finally, we report on a numerical study that shows the effectiveness of ZIO policies on a set of test problems.

Suggested Citation

  • Lap Mui Ann Chan & Ana Muriel & Zuo-Jun Shen & David Simchi-Levi, 2002. "On the Effectiveness of Zero-Inventory-Ordering Policies for the Economic Lot-Sizing Model with a Class of Piecewise Linear Cost Structures," Operations Research, INFORMS, vol. 50(6), pages 1058-1067, December.
    • Handle: RePEc:inm:oropre:v:50:y:2002:i:6:p:1058-1067
    DOI: 10.1287/opre.50.6.1058.350
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.50.6.1058.350
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.50.6.1058.350?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. Dong X. Shaw & Albert P. M. Wagelmans, 1998. "An Algorithm for Single-Item Capacitated Economic Lot Sizing with Piecewise Linear Production Costs and General Holding Costs," Management Science, INFORMS, vol. 44(6), pages 831-838, June.
    2. 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.
    3. Jiefeng Xu & Leonard L. Lu, 1998. "The dynamic lot size model with quantity discount: Counterexamples and correction," Naval Research Logistics (NRL), John Wiley & Sons, vol. 45(4), pages 419-422, June.
    4. Awi Federgruen & Chung‐Yee Lee, 1990. "The dynamic lot size model with quantity discount," Naval Research Logistics (NRL), John Wiley & Sons, vol. 37(5), pages 707-713, October.
    5. Alok Aggarwal & James K. Park, 1993. "Improved Algorithms for Economic Lot Size Problems," Operations Research, INFORMS, vol. 41(3), pages 549-571, June.
    6. C. P. M. van Hoesel & A. P. M. Wagelmans, 2001. "Fully Polynomial Approximation Schemes for Single-Item Capacitated Economic Lot-Sizing Problems," Mathematics of Operations Research, INFORMS, vol. 26(2), pages 339-357, May.
    Full references (including those not matched with items on IDEAS)

    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 & Vernon Ning Hsu & Wen-Qiang Xiao, 2004. "Dynamic Lot Sizing with Batch Ordering and Truckload Discounts," Operations Research, INFORMS, vol. 52(4), pages 639-654, August.
    2. 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.
    3. 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.
    4. Leon Yang Chu & Vernon Ning Hsu & Zuo‐Jun Max Shen, 2005. "An economic lot‐sizing problem with perishable inventory and economies of scale costs: Approximation solutions and worst case analysis," Naval Research Logistics (NRL), John Wiley & Sons, vol. 52(6), pages 536-548, September.
    5. Chung-Yee Lee & Sila Çetinkaya & Albert P.M. Wagelmans, 1999. "A Dynamic Lot-Sizing Model with Demand Time Windows," Tinbergen Institute Discussion Papers 99-095/4, Tinbergen Institute.
    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. van den Heuvel, W.J. & Wagelmans, A.P.M., 2003. "A geometric algorithm to solve the NI/G/NI/ND capacitated lot-sizing problem in O(T2) time," Econometric Institute Research Papers EI 2003-24, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    8. Lee, C.Y. & Cetinkaya, S. & Wagelmans, A.P.M., 1999. "A dynamic lot-sizing model with demand time windows," Econometric Institute Research Papers EI 9948-/A, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    9. Chung-Yee Lee & Sila Çetinkaya & Albert P. M. Wagelmans, 2001. "A Dynamic Lot-Sizing Model with Demand Time Windows," Management Science, INFORMS, vol. 47(10), pages 1384-1395, October.
    10. 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.
    11. 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.
    12. 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.
    13. Wolosewicz, Cathy & Dauzère-Pérès, Stéphane & Aggoune, Riad, 2015. "A Lagrangian heuristic for an integrated lot-sizing and fixed scheduling problem," European Journal of Operational Research, Elsevier, vol. 244(1), pages 3-12.
    14. 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.
    15. 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.
    16. Martel, Alain & Gascon, Andre, 1998. "Dynamic lot-sizing with price changes and price-dependent holding costs," European Journal of Operational Research, Elsevier, vol. 111(1), pages 114-128, November.
    17. Vernon Ning Hsu, 2000. "Dynamic Economic Lot Size Model with Perishable Inventory," Management Science, INFORMS, vol. 46(8), pages 1159-1169, August.
    18. 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.
    19. Yongpei Guan, 2011. "Stochastic lot-sizing with backlogging: computational complexity analysis," Journal of Global Optimization, Springer, vol. 49(4), pages 651-678, April.
    20. van den Heuvel, Wilco & Wagelmans, Albert P.M., 2006. "A polynomial time algorithm for a deterministic joint pricing and inventory model," European Journal of Operational Research, Elsevier, vol. 170(2), pages 463-480, 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:inm:oropre:v:50:y:2002:i:6:p:1058-1067. 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.