Online make-to-order joint replenishment model: primal dual competitive algorithms

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.

REFERENCES

• 1: Noga Alon , Baruch Awerbuch , Yossi Azar, The online set cover problem, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780558]
• 2: E. Arkin, D. Joneja, and R. Roundy. Computational complexity of uncapacitated multi-echelon production planning problems. Operations Research Letters, 8:61--66, 1989.
• 3: Y. Askoy and S. S. Erenguk. Multi-item inventory models with coordinated replenishment: a survey. International Journal of Operations and Production Management, 8:63--73, 1988.
• 4: Niv Buchbinder, Kamal Jain, and Joseph (Seffi) Naor. Online primal-dual algorithms for maximizing adauctions revenue. In 15th Annual European Symposium on Algorithms (ESA 2007), 2007.
• 5: Niv Buchbinder and Joseph (Seffi) Naor. Online primal-dual algorithms for covering and packing problems. In 13th Annual European Symposium on Algorithms -- ESA 2005, 2005.
• 6: Niv Buchbinder , Joseph (Seffit) Naor, Improved Bounds for Online Routing and Packing Via a Primal-Dual Approach, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.293-304, October 21-24, 2006 [doi>10.1109/FOCS.2006.39]
• 7: N. P. Dellaert1 and M. T. Melo. Heuristic procedures for a stochastic lot-sizing problem in make-to-order manufacturing. Annals of Operations Research, 59(1):227--258, 2005.
• 8: Daniel R. Dooly , Sally A. Goldman , Stephen D. Scott, TCP dynamic acknowledgment delay (extended abstract): theory and practice, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.389-398, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276792]
• 9: Michel X. Goemans , David P. Williamson, A General Approximation Technique for Constrained Forest Problems, SIAM Journal on Computing, v.24 n.2, p.296-317, April 1995 [doi>10.1137/S0097539793242618]
• 10: Qi-Ming He, E. M. Jewkes, and J. Buzacott. The value of information used in inventory control of a make-to-order inventory-production system. IIE Transactions, 34(11):999--1013, 2002.
• 11: S. Van Hoesel and A. Wagelmans. A dual algorithm for the economic lot-sizing problem. European Journal of Operatioms Research, 52:315--325, 1991.
• 12: Kamal Jain , Vijay V. Vazirani, Approximation algorithms for metric facility location and k-Median problems using the primal-dual schema and Lagrangian relaxation, Journal of the ACM (JACM), v.48 n.2, p.274-296, March 2001 [doi>10.1145/375827.375845]
• 13: Anna R. Karlin , Claire Kenyon , Dana Randall, Dynamic TCP acknowledgement and other stories about e/(e-1), Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.502-509, July 2001, Hersonissos, Greece [doi>10.1145/380752.380845]
• 14: Wei-Min Lan , Tava Lennon Olsen, Multiproduct Systems with Both Setup Times and Costs: Fluid Bounds and Schedules, Operations Research, v.54 n.3, p.505-522, May-June 2006 [doi>10.1287/opre.1060.0298]
• 15: Retsef Levi , Robin O. Roundy , David B. Shmoys, Primal-Dual Algorithms for Deterministic Inventory Problems, Mathematics of Operations Research, v.31 n.2, p.267-284, February 2006 [doi>10.1287/moor.1050.0178]
• 16: R. Levi, R. O. Roundy, D. B. Shmoys, and M. Sviridenko. First constant approximation algorithm for the single-warehouse multi-retailer problem. To appear in Management Science, extended abstracts appeared in SODA 2005 and APPROX 2006., 2004.
• 17: Andreas Wächter , Lorenz T. Biegler, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Mathematical Programming: Series A and B, v.106 n.1, p.25-57, May 2006 [doi>10.1007/s10107-004-0559-y]
• 18: Harvey M. Wagner , Thomson M. Whitin, Dynamic Version of the Economic Lot Size Model, Management Science, v.50 n.12 Supplement, p.1770-1774, December 2004 [doi>10.1287/mnsc.1040.0262]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Online computation

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis

General Terms:
Performance