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

Niv Buchbinder (), Tracy Kimbrel (), Retsef Levi (), Konstantin Makarychev () and Maxim Sviridenko ()
Additional contact information
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

Operations Research, 2013, vol. 61, issue 4, 1014-1029

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

Keywords: joint replenishment problem; online algorithm; competitive analysis; primal dual (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2013.1188 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:61:y:2013:i:4:p:1014-1029

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().