skip to main content
10.5555/1347082.1347186acmconferencesArticle/Chapter ViewAbstractPublication PagessodaConference Proceedingsconference-collections
research-article

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

Published: 20 January 2008 Publication History

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]
N. Alon, B. Awerbuch, Y. Azar, N. Buchbinder, and J. Naor. The online set cover problem. In Proceedings of the 35th annual ACM Symposium on the Theory of Computation, pages 100--105, 2003.
[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 and Joseph (Seffi) Naor. Improved Bounds for Online Routing and Packing Via a Primal-Dual Approach. In 47th annual ieee Symposium on Foundations of Computer Science (FOCS 2006), 2006.
[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, and Stephen D. Scott. Tcp dynamic acknowledgment delay (extended abstract): theory and practice. In STOC '98: Proceedings of the thirtieth annual ACM symposium on Theory of computing, pages 389--398, 1998.
[9]
M. X. Goemans and D. P. Williamson. A general approximation technique for constrained forest problems. SIAM Journal on Computing, 24:296--317, 1995.
[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]
K. Jain and V. V. Vazirani. Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation. Journal of the ACM 48, pages 274--296, 2001.
[13]
Anna R. Karlin, Claire Kenyon, and Dana Randall. Dynamic TCP acknowledgement and other stories about e/(e-1). In ACM Symposium on Theory of Computing, pages 502--509, 2001.
[14]
Wei-Min Lan and Tava Lennon Olsen. Multiproduct systems with both setup times and costs: Fluid bounds and schedules. Operations Research, 54(3):505--522, 2006.
[15]
R. Levi, R. O. Roundy, and D. B. Shmoys. Primal-dual algorithms for deterministic inventory problems. Mathematics of Operations Research, 31:267--284, 2006.
[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]
A. Wächter and L. T. Biegler. On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Mathematical Programming, 106(1):25--57, 2006.
[18]
H. M. Wagner and T. M. Whitin. Dynamic version of the economic lot sizing model. Management Science, 5:89--96, 1958.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
SODA '08: Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms
January 2008
1289 pages
  • Program Chair:
  • Shang-Hua Teng

Sponsors

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 20 January 2008

Check for updates

Qualifiers

  • Research-article

Conference

SODA08
Sponsor:
SODA08: 19th ACM-SIAM Symposium on Discrete Algorithms
January 20 - 22, 2008
California, San Francisco

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 27 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2020)Adoption and Diffusion of Hi-Technology Product and Related Inventory PoliciesInternational Journal of E-Adoption10.4018/IJEA.202001010112:1(1-14)Online publication date: 1-Oct-2020
  • (2014)Better approximation bounds for the joint replenishment problemProceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms10.5555/2634074.2634078(42-54)Online publication date: 5-Jan-2014
  • (2014)Online aggregation problemsACM SIGACT News10.1145/2596583.259660345:1(91-102)Online publication date: 17-Mar-2014
  • (2013)Online control message aggregation in chain networksProceedings of the 13th international conference on Algorithms and Data Structures10.1007/978-3-642-40104-6_12(133-145)Online publication date: 12-Aug-2013
  • (2009)The Design of Competitive Online Algorithms via a PrimalFoundations and Trends® in Theoretical Computer Science10.1561/04000000243:2–3(93-263)Online publication date: 1-Feb-2009

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media