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

The Joint Replenishment Problem: New Heuristics and Worst Case Performance Bounds

Author

Listed:
  • Dev Joneja

    (Columbia University, New York, New York)

Abstract

The joint replenishment problem involves the lot sizing of several items with nonstationary demand in discrete time. The items have individual ordering costs and linear inventory holding costs. In addition, a joint ordering cost is incurred whenever one or more items is ordered together. This problem often arises when economies can be affected by coordinated ordering or setup of the items, both in distribution and in manufacturing environments. This problem is known to be NP-complete. In this paper, we analyze the worst case performance of an existing multipass heuristic for the problem. Then a new single pass forward heuristic is proposed, and it is proved that it has a uniformly bounded worst case performance. Furthermore, a lower bound on the cost of the optimal solution is obtained once the heuristic has been used. We then discuss a number of related heuristic algorithms and their worst case performance. The behavior of our heuristics for a randomly generated set of problems is also studied.

Suggested Citation

  • Dev Joneja, 1990. "The Joint Replenishment Problem: New Heuristics and Worst Case Performance Bounds," Operations Research, INFORMS, vol. 38(4), pages 711-723, August.
  • Handle: RePEc:inm:oropre:v:38:y:1990:i:4:p:711-723
    DOI: 10.1287/opre.38.4.711
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.38.4.711
    Download Restriction: no

    File URL: https://libkey.io/10.1287/opre.38.4.711?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
    ---><---

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Danny Segev, 2014. "An Approximate Dynamic-Programming Approach to the Joint Replenishment Problem," Mathematics of Operations Research, INFORMS, vol. 39(2), pages 432-444, May.
    2. Jans, R.F. & Degraeve, Z., 2005. "Modeling Industrial Lot Sizing Problems: A Review," ERIM Report Series Research in Management ERS-2005-049-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.
    3. Yue Jin & Ana Muriel, 2009. "Single‐warehouse multi‐retailer inventory systems with full truckload shipments," Naval Research Logistics (NRL), John Wiley & Sons, vol. 56(5), pages 450-464, August.
    4. Monalisha Pattnaik & Padmabati Gahan, 2021. "Preservation effort effects on retailers and manufacturers in integrated multi-deteriorating item discrete supply chain model," OPSEARCH, Springer;Operational Research Society of India, vol. 58(2), pages 276-329, June.
    5. E P Robinson & A Narayanan & L-L Gao, 2007. "Effective heuristics for the dynamic demand joint replenishment problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(6), pages 808-815, June.
    6. Robinson, Powell & Narayanan, Arunachalam & Sahin, Funda, 2009. "Coordinated deterministic dynamic demand lot-sizing problem: A review of models and algorithms," Omega, Elsevier, vol. 37(1), pages 3-15, February.
    7. Lap Mui Ann Chan & Ana Muriel & Zuo-Jun Max Shen & David Simchi-Levi & Chung-Piaw Teo, 2002. "Effective Zero-Inventory-Ordering Policies for the Single-Warehouse Multiretailer Problem with Piecewise Linear Cost Structures," Management Science, INFORMS, vol. 48(11), pages 1446-1460, November.
    8. Narayanan, Arunachalam & Robinson, Powell, 2010. "Efficient and effective heuristics for the coordinated capacitated lot-size problem," European Journal of Operational Research, Elsevier, vol. 203(3), pages 583-592, June.
    9. Yunxia Zhu & Milind Dawande & Chelliah Sriskandarajah, 2011. "Value of Local Cash Reuse: Inventory Models for Medium-Size Depository Institutions Under the New Federal Reserve Policy," Manufacturing & Service Operations Management, INFORMS, vol. 13(4), pages 508-524, October.
    10. Awi Federgruen & Michal Tzur, 1996. "Detection of minimal forecast horizons in dynamic programs with multiple indicators of the future," Naval Research Logistics (NRL), John Wiley & Sons, vol. 43(2), pages 169-189, March.
    11. Retsef Levi & Robin O. Roundy & David B. Shmoys, 2006. "Primal-Dual Algorithms for Deterministic Inventory Problems," Mathematics of Operations Research, INFORMS, vol. 31(2), pages 267-284, May.
    12. Tamar Cohen-Hillel & Liron Yedidsion, 2018. "The Periodic Joint Replenishment Problem Is Strongly 𝒩𝒫-Hard," Mathematics of Operations Research, INFORMS, vol. 43(4), pages 1269-1289, November.
    13. Chung, Chia-Shin & Hum, Sin-Hoon & Kirca, Omer, 1996. "The coordinated replenishment dynamic lot-sizing problem with quantity discounts," European Journal of Operational Research, Elsevier, vol. 94(1), pages 122-133, October.
    14. J-M Chen & T-H Chen, 2005. "Effects of joint replenishment and channel coordination for managing multiple deteriorating products in a supply chain," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 56(10), pages 1224-1234, October.
    15. Retsef Levi & Martin Pál & Robin O. Roundy & David B. Shmoys, 2007. "Approximation Algorithms for Stochastic Inventory Control Models," Mathematics of Operations Research, INFORMS, vol. 32(2), pages 284-302, May.
    16. Ömer Kirca, 1995. "A primal‐dual algorithm for the dynamic lotsizing problem with joint set‐up costs," Naval Research Logistics (NRL), John Wiley & Sons, vol. 42(5), pages 791-806, August.
    17. Awi Federgruen & Michal Tzur, 1999. "Time‐partitioning heuristics: Application to one warehouse, multiitem, multiretailer lot‐sizing problems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 46(5), pages 463-486, August.
    18. Yale T. Herer & Michal Tzur, 2001. "The dynamic transshipment problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 48(5), pages 386-408, August.

    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:38:y:1990:i:4:p:711-723. 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.

    We have no bibliographic references for this item. You can help adding them by using 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.