[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

The submodular joint replenishment problem

  • Full Length Paper
  • Series A
  • Published:
Mathematical Programming Submit manuscript

Abstract

The joint replenishment problem is a fundamental model in supply chain management theory that has applications in inventory management, logistics, and maintenance scheduling. In this problem, there are multiple item types, each having a given time-dependent sequence of demands that need to be satisfied. In order to satisfy demand, orders of the item types must be placed in advance of the due dates for each demand. Every time an order of item types is placed, there is an associated joint setup cost depending on the subset of item types ordered. This ordering cost can be due to machine, transportation, or labor costs, for example. In addition, there is a cost to holding inventory for demand that has yet to be served. The overall goal is to minimize the total ordering costs plus inventory holding costs. In this paper, the cost of an order, also known as a joint setup cost, is a monotonically increasing, submodular function over the item types. For this general problem, we show that a greedy approach provides an approximation guarantee that is logarithmic in the number of demands. Then we consider three special cases of submodular functions which we call the laminar, tree, and cardinality cases, each of which can model real world scenarios that previously have not been captured. For each of these cases, we provide a constant factor approximation algorithm. Specifically, we show that the laminar case can be solved optimally in polynomial time via a dynamic programming approach. For the tree and cardinality cases, we provide two different linear programming based approximation algorithms that provide guarantees of three and five, respectively.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

References

  1. Arkin, E., Joneja, D., Roundy, R.: Computational complexity of uncapacitated multi-echelon production planning problems. Oper. Res. Lett. 8(2), 61–66 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  2. Becchetti, L., Korteweg, P., Marchetti-Spaccamela, A., Skutella, M., Stougie, L., Vitaletti, A.: Latency Constrained Aggregation in Sensor Networks. Springer, Berlin (2006)

    Book  MATH  Google Scholar 

  3. Bertsimas, D., Weismantel, R.: Optimization Over Integers, vol. 13. Dynamic Ideas, Belmont (2005)

    Google Scholar 

  4. Bienkowski, M., Byrka, J., Chrobak, M., Jez, L., Sgall, J.: Better approximation bounds for the joint replenishment problem. arXiv preprint arXiv:1307.2531 (2013)

  5. Chan L, Muriel, A., Shen, Z., Simchi-Levi, D., Teo, C.: Effective zero-inventory-ordering policies for the single-warehouse multiretailer problem with piecewise linear cost structures. Manag. Sci. 48(11), 1446–1460 (2002)

  6. Chvatal, V.: A greedy heuristic for the set-covering problem. Math. Oper. Res. 4(3), 233–235 (1979)

    Article  MathSciNet  MATH  Google Scholar 

  7. Federgruen, A., Tzur, M.: The joint replenishment problem with time-varying costs and demands: efficient, asymptotic and \(\varepsilon \)-optimal solutions. Oper. Res. 42(6), 1067–1086 (1994)

  8. Federgruen, A., Zheng, Y.: The joint replenishment problem with general joint cost structures. Oper. Res. 40(2), 384–403 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  9. Federgruen, A., Queyranne, M., Zheng, Y.S.: Simple power-of-two policies are close to optimal in a general class of production/distribution networks with general joint setup costs. Math. Oper. Res. 17(4), 951–963 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  10. Herer, Y., Roundy, R.: Heuristics for a one-warehouse multiretailer distribution problem with performance bounds. Oper. Res. 45(1), 102–115 (1997)

    Article  MATH  Google Scholar 

  11. Joneja, D.: The joint replenishment problem: new heuristics and worst case performance bounds. Oper. Res. 38(4), 711–723 (1990)

    Article  MATH  Google Scholar 

  12. Kao, E.: A multi-product dynamic lot-size model with individual and joint set-up costs. Oper. Res. 27(2), 279–289 (1979)

  13. Khanna, S., Naor, J.S., Raz, D.: Control message aggregation in group communication protocols. In: Automata, Languages and Programming, pp. 135–146. Springer, Berlin (2002)

  14. Levi, R., Roundy, R., Shmoys, D.: Primal-dual algorithms for deterministic inventory problems. Math. Oper. Res. 31(2), 267–284 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  15. Levi, R., Roundy, R., Shmoys, D., Sviridenko, M.: A constant approximation algorithm for the one-warehouse multiretailer problem. Manag. Sci. 54(4), 763 (2008)

    Article  MATH  Google Scholar 

  16. Levi, R., Magnanti, T., Zarybnisky, E.: Maintenance scheduling for modular systems-models and algorithms. PhD thesis, Massachusetts Institute of Technology (2011)

  17. Nagarajan, V., Shi, C.: Approximation algorithms for inventory problems with submodular or routing costs. arXiv preprint arXiv:1504.06560 (2015)

  18. Nonner, T., Souza, A.: A 5/3-approximation algorithm for joint replenishment with deadlines. In: Combinatorial Optimization and Applications, pp 24–35. Springer, Berlin (2009)

  19. Nonner, T., Sviridenko, M.: An efficient polynomial-time approximation scheme for the joint replenishment problem. In: Integer Programming and Combinatorial Optimization, pp 314–323. Springer, Berlin (2013)

  20. Orlin, J.B.: A faster strongly polynomial time algorithm for submodular function minimization. Math. Program. 118(2), 237–251 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  21. Queyranne, M.: A polynomial-time, submodular extension to roundy’s 98% effective heuristic for production/inventory. In: Robotics and Automation. Proceedings. 1986 IEEE International Conference on, IEEE, vol 3, pp. 1640–1640. (1986)

  22. Roundy, R.: 98%-effective integer-ratio lot-sizing for one-warehouse multi-retailer systems. Manag. Sci. 31(11), 1416–1430 (1985)

  23. Schrijver, A.: Theory of Linear and Integer Programming. Wiley, New York (1998)

    MATH  Google Scholar 

  24. Schulz, A.S., Telha, C.: Approximation algorithms and hardness results for the joint replenishment problem with constant demands. In: Algorithms-ESA 2011, pp. 628–639. Springer, Berlin (2011)

  25. Segev, D.: An approximate dynamic-programming approach to the joint replenishment problem. Math. Oper. Res. 39(2), 432–444 (2013)

  26. Stauffer, G., Massonnet, G., Rapine, C., Gayon, J.: A simple and fast 2-approximation algorithm for the one-warehouse multi-retailers problem. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics (2011)

  27. Svitkina, Z., Tardos, E.: Facility location with hierarchical facility costs. ACM Trans. Algorithms (TALG) 6(2), 37 (2010)

    MathSciNet  MATH  Google Scholar 

  28. Teo, C., Bertsimas, D.: Multistage lot sizing problems via randomized rounding. Oper. Res. 49(4), 599–608 (2001)

  29. Veinott, Jr A.: Minimum concave-cost solution of leontief substitution models of multi-facility inventory systems. Oper. Res. 17(2), 262–291 (1969)

  30. Viswanathan, S.: An algorithm for determining the best lower bound for the stochastic joint replenishment problem. Oper. Res. 55(5), 992–996 (2007)

    Article  MATH  Google Scholar 

  31. Wagner, H., Whitin, T.: Dynamic version of the economic lot size model. Manag.Sci. 5(1), 89–96 (1958)

    Article  MathSciNet  MATH  Google Scholar 

  32. Zangwill, W.: A backlogging model and a multi-echelon model of a dynamic economic lot size production system-a network approach. Manag. Sci. 15(9), 506–527 (1969)

Download references

Acknowledgments

We thank the refereeing team for their numerous insightful comments that significantly improved the quality and exposition of the paper. The research of the first author was supported by NSF grants CCF-0832782, CCF-1017688 and NSERC grant PGS-358528. The research of the second author was partially conducted while he was a student at the Operations Research Center at Massachusetts Institute of Technology and was supported by a National Defense Science and Engineering Graduate Fellowship from the Air Force Office of Scientific Research. The research of the third author was partially supported by NSF grant CMMI-0846554 (CAREER Award), an AFOSR award FA9550-11-1-0150, an SMA grant and the Buschbaum Research Fund of MIT. The research of the fourth author was supported by NSF grants CCF-0832782 and CCF-1017688.

Author information

Authors and Affiliations

  1. School of Operations Research and Information Engineering, Cornell University, Ithaca, NY, USA

    Maurice Cheung

  2. Department of Industrial Engineering and Operations Research, Columbia University, New York, NY, USA

    Adam N. Elmachtoub

  3. Sloan School of Management, Massachusetts Institute of Technology, Cambridge, MA, USA

    Retsef Levi

  4. Department of Computer Science and School of Operations Research and Information Engineering, Cornell University, Ithaca, NY, USA

    David B. Shmoys

Authors
  1. Maurice Cheung
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Adam N. Elmachtoub
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Retsef Levi
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. David B. Shmoys
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Adam N. Elmachtoub.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Cheung, M., Elmachtoub, A.N., Levi, R. et al. The submodular joint replenishment problem. Math. Program. 158, 207–233 (2016). https://doi.org/10.1007/s10107-015-0920-3

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-015-0920-3

Keywords

Mathematics Subject Classification

Search

Navigation