IDEAS home Printed from
   My bibliography  Save this article

Online Make-to-Order Joint Replenishment Model: Primal-Dual Competitive Algorithms


  • Niv Buchbinder

    () (Statistics and Operations Research Department, Tel Aviv University, Ramat Aviv 6997801, Israel)

  • Tracy Kimbrel

    () (National Science Foundation, Arlington, Virginia 22230)

  • Retsef Levi

    () (Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts, 02139)

  • Konstantin Makarychev

    () (Microsoft Research, Redmond, Washington 98052)

  • Maxim Sviridenko

    () (Department of Computer Science, University of Warwick, Coventry CV4 7AL, United Kingdom)


In this paper, we study an online make-to-order variant of the classical joint replenishment problem (JRP) that has been studied extensively over the years and plays a fundamental role in broader planning issues, such as the management of supply chains. In contrast to the traditional approaches of the stochastic inventory theory, we study the problem using competitive analysis against a worst-case adversary.Our main result is a 3-competitive deterministic algorithm for the online version of the JRP. We also prove a lower bound of approximately 2.64 on the competitiveness of any deterministic online algorithm for the problem. Our algorithm is based on a novel primal-dual approach using a new linear programming relaxation of the offline JRP model. The primal-dual approach that we propose departs from previous primal-dual and online algorithms in rather significant ways. We believe that this approach can extend the range of problems to which online and primal-dual algorithms can be applied and analyzed.

Suggested Citation

  • Niv Buchbinder & Tracy Kimbrel & Retsef Levi & Konstantin Makarychev & Maxim Sviridenko, 2013. "Online Make-to-Order Joint Replenishment Model: Primal-Dual Competitive Algorithms," Operations Research, INFORMS, vol. 61(4), pages 1014-1029, August.
  • Handle: RePEc:inm:oropre:v:61:y:2013:i:4:p:1014-1029

    Download full text from publisher

    File URL:
    Download Restriction: no

    References listed on IDEAS

    1. Wilco Van den Heuvel & Albert P. M. Wagelmans, 2010. "Worst-Case Analysis for a General Class of Online Lot-Sizing Heuristics," Operations Research, INFORMS, vol. 58(1), pages 59-67, February.
    2. Retsef Levi & Robin Roundy & David Shmoys & Maxim Sviridenko, 2008. "A Constant Approximation Algorithm for the One-Warehouse Multiretailer Problem," Management Science, INFORMS, vol. 54(4), pages 763-776, April.
    3. Michael R. Wagner, 2010. "Fully Distribution-Free Profit Maximization: The Inventory Management Case," Mathematics of Operations Research, INFORMS, vol. 35(4), pages 728-741, November.
    4. Wei-Min Lan & Tava Lennon Olsen, 2006. "Multiproduct Systems with Both Setup Times and Costs: Fluid Bounds and Schedules," Operations Research, INFORMS, vol. 54(3), pages 505-522, June.
    5. Woonghee Tim Huh & Retsef Levi & Paat Rusmevichientong & James B. Orlin, 2011. "Adaptive Data-Driven Inventory Control with Censored Demand Based on Kaplan-Meier Estimator," Operations Research, INFORMS, vol. 59(4), pages 929-941, August.
    6. 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.
    7. Pinar Keskinocak & R. Ravi & Sridhar Tayur, 2001. "Scheduling and Reliable Lead-Time Quotation for Orders with Availability Intervals and Lead-Time Sensitive Revenues," Management Science, INFORMS, vol. 47(2), pages 264-279, February.
    Full references (including those not matched with items on IDEAS)


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

    Cited by:

    1. repec:taf:tprsxx:v:55:y:2017:i:4:p:1065-1084 is not listed on IDEAS
    2. Adam N. Elmachtoub & Retsef Levi, 2016. "Supply Chain Management with Online Customer Selection," Operations Research, INFORMS, vol. 64(2), pages 458-473, April.


    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:61:y:2013:i:4:p:1014-1029. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Matthew Walls). General contact details of provider: .

    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 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.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.