The Periodic Joint Replenishment Problem Is Strongly 𝒩𝒫-Hard

References

• Arkin E, Joneja D, Roundy R (1989) Computational complexity of uncapacitated multi-echelon production planning problems. Oper. Res. Lett. 8(2):61–66.Crossref, Google Scholar
• Fung RYK, Ma X (2001) A new method for joint replenishment problems. J. Oper. Res. Soc. 52(3):358–362.Crossref, Google Scholar
• Goyal SK (1973) Determination of economic packaging frequency for items jointly replenished. Management Sci. 20(2):232–235.Link, Google Scholar
• Goyal SK (1975) Analysis of joint replenishment inventory systems with resource restriction. Oper. Res. Quart. 26(1):197–203.Crossref, Google Scholar
• Goyal SK, Belton AS (1979) On “A simple method of determining order quantities in joint replenishments under deterministic demand.” (Note.) Management Sci. 25(6):604.Google Scholar
• Goyal SK, Deshmukh SG (1993) A note on “The economic ordering quantity for jointly replenishing items.” Internat. J. Production Res. 31(12):2959–2961.Crossref, Google Scholar
• Goyal SK, Satir AT (1989) Joint replenishment inventory control: Deterministic and stochastic models. Eur. J. Oper. Res. 38(1):2–13.Crossref, Google Scholar
• Guy RK (1994) Gaps between primes. Littlewood JE, ed. Unsolved Problems in Number Theory, 2nd ed. (Springer, New York), 19–23.Crossref, Google Scholar
• Hardy GH, Littlewood JE (1923) Some problems of “Partitio numerorum.” III. On the expression of a number as a sum of primes. Acta Math. 44(1):1–70.Crossref, Google Scholar
• Hardy GH, Wright EM (1979) An Introduction to the Theory of Numbers, 5th ed. (Clarendon Press, Oxford, UK).Google Scholar
• Jackson P, Maxwell W, Muckstadt J (1985) The joint replenishment problem with a powers-of-two restriction. IIE Trans. 17(1):25–32.Crossref, Google Scholar
• Joneja D (1990) The joint replenishment problem: New heuristics and worst case performance bounds. Oper. Res. 38(4):711–723.Link, Google Scholar
• Kaspi M, Rosenblatt MJ (1983) An improvement of Silver’s algorithm for the joint replenishment problem. AIIE Trans. 15(3):264–267.Google Scholar
• Kaspi M, Rosenblatt MJ (1991) On the economic ordering quantity for jointly replenished items. Internat. J. Production Res. 29(1):107–114.Crossref, Google Scholar
• Khouja M, Goyal S (2008) A review of the joint replenishment problem literature: 1989–2005. Eur. J. Oper. Res. 186(1):1–16.Crossref, Google Scholar
• Khouja M, Michalewicz Z, Satoskar SS (2000) A comparison between genetic algorithms and the RAND method for solving the joint replenishment problem. Production Planning Control 11(6):556–564.Crossref, Google Scholar
• Lee FC, Yao MJ (2003) A global optimum search algorithm for the joint replenishment problem under power-of-two policy. Comput. Oper. Res. 30(9):1319–1333.Crossref, Google Scholar
• Levi R, Roundy RO, Shmoys DB (2006) Primal-dual algorithms for deterministic inventory problems. Math. Oper. Res. 31(2):267–284.Link, Google Scholar
• Levi R, Roundy R, Shmoys D, Sviridenko M (2008) A constant approximation algorithm for the one-warehouse multiretailer problem. Management Sci. 54(4):763–776.Link, Google Scholar
• Lu L, Posner ME (1994) Approximation procedures for the one-warehouse multi-retailer system. Management Sci. 40(10):1305–1316.Link, Google Scholar
• Mertens F (1874) Ein Beitrag zur analytischen Zahlentheorie. J. Reine Angewandte Math. 78:46–62.Google Scholar
• Moon IK, Cha BC (2006) The joint replenishment problem with resource restriction. Eur. J. Oper. Res. 173(1):190–198.Crossref, Google Scholar
• Muckstadt JA, Roundy RO (1987) Multi-item, one-warehouse, multi-retailer distribution systems. Management Sci. 33(12):1613–1621.Link, Google Scholar
• Muckstadt JA, Roundy RO (1993) Analysis of multistage production systems. Graves SC, Rinnooy Kan AHG, Zipkin PH, eds. Logistics of Production and Inventory, Handbooks in Operations Research and Management Science, Vol. 4 (Elsevier, Amsterdam), 59–131.Crossref, Google Scholar
• Nahmias S (2001) Production and Operations Analysis (McGraw-Hill, New York).Google Scholar
• Nocturne DJ (1973) Economic ordering frequency for several items jointly replenished. Management Sci. 19(9):1093–1096.Link, Google Scholar
• Nonner T, Souza A (2009) A 5/3-approximation algorithm for joint replenishment with deadlines. Du DZ, Hu X, Pardalos PM, eds. Proc. 3rd Annual Internat. Conf. Combin. Optim. Appl. (Springer, Berlin), 24–35.Google Scholar
• Nonner T, Sviridenko M (2013) An efficient polynomial-time approximation scheme for the joint replenishment problem. Jünger M, Kaibel V, eds. Integer Programming and Combinatorial Optimization—11th International IPCO Conference, Lecture Notes in Computer Science, Vol. 3509 (Springer, Berlin), 314–323.Crossref, Google Scholar
• Olsen AL (2005) An evolutionary algorithm to solve the joint replenishment problem using direct grouping. Comput. Indust. Engrg. 48(2):223–235.Crossref, Google Scholar
• Papadimitriou C, Yannakakis M (1988) Optimization, approximation, and complexity classes. Proc. 20th Annual ACM Sympos. Theory Comput. (ACM, New York), 229–234.Google Scholar
• Polymath8 Project (2015) Bounded gaps between primes. Accessed May 27, 2018, http://michaelnielsen.org/polymath1/index.php?title=Bounded_gaps_between_primes.Google Scholar
• Porras EM, Dekker R (2004) On the efficiency of optimal algorithms for the joint replenishment problem: A comparative study. Econometric Institute Research Paper EI 2004-33, Erasmus University Rotterdam, Rotterdam, Netherlands.Google Scholar
• Porras EM, Dekker R (2005) Generalized solutions for the joint replenishment problem with correction factor. Econometric Institute Research Paper EI 2005-19, Erasmus University Rotterdam, Rotterdam, Netherlands.Google Scholar
• Porras EM, Dekker R (2006) An efficient optimal solution method for the joint replenishment problem with minimum order quantities. Eur. J. Oper. Res. 174(3):1595–1615.Crossref, Google Scholar
• Ribenboim P (1996) The New Book of Prime Number Records (Springer, New York).Crossref, Google Scholar
• Rosser JB, Schoenfeld L (1962) Approximate formulas for some functions of prime numbers. Illinois J. Math. 6(1):64–94.Crossref, Google Scholar
• Roundy R (1985) 98%-effective integer-ratio lot-sizing for one-warehouse multi-retailer systems. Management Sci. 31(11):1416–1430.Link, Google Scholar
• Schulz AS, Telha C (2011) Approximation algorithms and hardness results for the joint replenishment problem with constant demands. Demetrescu C, Halldórsson MM, eds. Algorithms—ESA 2011, Lecture Notes in Computer Science, Vol. 6942 (Springer, Berlin), 628–639.Crossref, Google Scholar
• Segev D (2013) An approximate dynamic-programming approach to the joint replenishment problem. Math. Oper. Res. 39(2):432–444.Link, Google Scholar
• Shanks D (1993) Solved and Unsolved Problems in Number Theory, 4th ed. (AMS Chelsea Publishing, Providence, RI).Google Scholar
• Shu FT (1971) Economic ordering frequency for two items jointly replenished. Management Sci. 17(6):B-406–B-410.Link, Google Scholar
• Silver EA (1976) A simple method of determining order quantities in joint replenishments under deterministic demand. Management Sci. 22(12):1351–1361.Link, Google Scholar
• Teo CP, Bertsimas D (2001) Multistage lot sizing problems via randomized rounding. Oper. Res. 49(4):599–608.Link, Google Scholar
• Van Eijs MJG (1993) A note on the joint replenishment problem under constant demand. J. Oper. Res. Soc. 44(2):185–191.Crossref, Google Scholar
• Viswanathan S (1996) A new optimal algorithm for the joint replenishment problem. J. Oper. Res. Soc. 47(7):936–944.Crossref, Google Scholar
• Viswanathan S (2002) On optimal algorithms for the joint replenishment problem. J. Oper. Res. Soc. 53(11):1286–1290.Crossref, Google Scholar
• Wildeman RE, Frenk JBG, Dekker R (1997) An efficient optimal solution method for the joint replenishment problem. Eur. J. Oper. Res. 99(2):433–444.Crossref, Google Scholar
• Zhang Y (2014) Bounded gaps between primes. Ann. Math. 179(3):1121–1174.Crossref, Google Scholar
• Zipkin PH (2000) Foundations of Inventory Management, Vol. 2 (McGraw-Hill, New York).Google Scholar