IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v67y2019i5p1345-1361.html
   My bibliography  Save this article

The Replenishment Schedule to Minimize Peak Storage Problem: The Gap Between the Continuous and Discrete Versions of the Problem

Author

Listed:
  • Dorit S. Hochbaum

    (Department of Industrial Engineering and Operations Research, University of California, Berkeley, California 94709)

  • Xu Rao

    (Department of Industrial Engineering and Operations Research, University of California, Berkeley, California 94709)

Abstract

The replenishment storage problem (RSP) is to minimize the storage capacity requirement for a deterministic demand, multi-item inventory system, where each item has a given reorder size and cycle length. We consider the discrete RSP, where reorders can only take place at an integer time unit within the cycle. Discrete RSP was shown to be NP-hard for constant joint cycle length (the least common multiple of the length of all individual cycles). We show here that discrete RSP is weakly NP-hard for constant joint cycle length and prove that it is strongly NP-hard for nonconstant joint cycle length. For constant joint cycle-length discrete RSP, we further present a pseudopolynomial time algorithm that solves the problem optimally and the first known fully polynomial time approximation scheme (FPTAS) for the single-cycle RSP. The scheme is utilizing a new integer programming formulation of the problem that is introduced here. For the strongly NP-hard RSP with nonconstant joint cycle length, we provide a polynomial time approximation scheme (PTAS), which for any fixed ɛ , provides a linear time ɛ approximate solution. The continuous RSP, where reorders can take place at any time within a cycle, seems (with our results) to be easier than the respective discrete problem. We narrow the previously known complexity gap between the continuous and discrete versions of RSP for the multi-cycle RSP (with either constant or nonconstant cycle length) and the single-cycle RSP with constant cycle length and widen the gap for single-cycle RSP with nonconstant cycle length. For the multi-cycle case and constant joint cycle length, the complexity status of continuous RSP is open, whereas it is proved here that the discrete RSP is weakly NP-hard. Under our conjecture that the continuous RSP is easier than the discrete one, this implies that continuous RSP on multi-cycle and constant joint cycle length (currently of unknown complexity status) is at most weakly NP-hard.

Suggested Citation

  • Dorit S. Hochbaum & Xu Rao, 2019. "The Replenishment Schedule to Minimize Peak Storage Problem: The Gap Between the Continuous and Discrete Versions of the Problem," Operations Research, INFORMS, vol. 67(5), pages 1345-1361, September.
    • Handle: RePEc:inm:oropre:v:67:y:2019:i:5:p:1345-1361
    DOI: opre.2018.1839
    as

    Download full text from publisher

    File URL: https://doi.org/opre.2018.1839
    Download Restriction: no
    File URL: https://libkey.io/opre.2018.1839?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Boctor, Fayez F., 2010. "Offsetting inventory replenishment cycles to minimize storage space," European Journal of Operational Research, Elsevier, vol. 203(2), pages 321-325, June.
    2. Yao, Ming-Jong & Chu, Weng-Ming, 2008. "A genetic algorithm for determining optimal replenishment cycles to minimize maximum warehouse space requirements," Omega, Elsevier, vol. 36(4), pages 619-631, August.
    3. Ernest Croot & Kai Huang, 2013. "A class of random algorithms for inventory cycle offsetting," International Journal of Operational Research, Inderscience Enterprises Ltd, vol. 18(2), pages 201-217.
    4. Shoshana Anily, 1991. "Multi-Item Replenishment and Storage Problem (MIRSP): Heuristics and Bounds," Operations Research, INFORMS, vol. 39(2), pages 233-243, April.
    5. Murthy, Nagesh N. & Benton, W. C. & Rubin, Paul A., 2003. "Offsetting inventory cycles of items sharing storage," European Journal of Operational Research, Elsevier, vol. 150(2), pages 304-319, October.
    6. Klaus Zoller, 1977. "Deterministic Multi-Item Inventory Systems with Limited Capacity," Management Science, INFORMS, vol. 24(4), pages 451-455, December.
    7. Urban, Timothy L., 2016. "Offsetting inventory replenishment cyclesAuthor-Name: Russell, Robert A," European Journal of Operational Research, Elsevier, vol. 254(1), pages 105-112.
    8. Guillermo Gallego & Maurice Queyranne & David Simchi-Levi, 1996. "Single Resource Multi-Item Inventory Systems," Operations Research, INFORMS, vol. 44(4), pages 580-595, August.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Fayez F. Boctor & Marie-Claude Bolduc, 2018. "The inventory replenishment planning and staggering problem: a bi-objective approach," 4OR, Springer, vol. 16(2), pages 199-224, June.
    2. Boctor, Fayez F., 2010. "Offsetting inventory replenishment cycles to minimize storage space," European Journal of Operational Research, Elsevier, vol. 203(2), pages 321-325, June.
    3. Beemsterboer, Bart & Teunter, Ruud & Riezebos, Jan, 2016. "Two-product storage-capacitated inventory systems: A technical note," International Journal of Production Economics, Elsevier, vol. 176(C), pages 92-97.
    4. Sin-Hoon Hum & Moosa Sharafali & Chung-Piaw Teo, 2005. "Staggering Periodic Replenishment in Multivendor JIT Environments," Operations Research, INFORMS, vol. 53(4), pages 698-710, August.
    5. Haksever, Cengiz & Moussourakis, John, 2005. "A model for optimizing multi-product inventory systems with multiple constraints," International Journal of Production Economics, Elsevier, vol. 97(1), pages 18-30, July.
    6. D. Beyer & S. P. Sethi & R. Sridhar, 2001. "Stochastic Multiproduct Inventory Models with Limited Storage," Journal of Optimization Theory and Applications, Springer, vol. 111(3), pages 553-588, December.
    7. Favaretto, Daniela & Pesenti, Raffaele & Ukovich, Walter, 2001. "Discrete frequency models for inventory management - an introduction," International Journal of Production Economics, Elsevier, vol. 71(1-3), pages 331-342, May.
    8. Yao, Ming-Jong & Chu, Weng-Ming, 2008. "A genetic algorithm for determining optimal replenishment cycles to minimize maximum warehouse space requirements," Omega, Elsevier, vol. 36(4), pages 619-631, August.
    9. Zhang, Wei & Rajaram, Kumar, 2017. "Managing limited retail space for basic products: Space sharing vs. space dedication," European Journal of Operational Research, Elsevier, vol. 263(3), pages 768-781.
    10. Kaijie Zhu & Ulrich W. Thonemann, 2009. "Coordination of pricing and inventory control across products," Naval Research Logistics (NRL), John Wiley & Sons, vol. 56(2), pages 175-190, March.
    11. Ramesh Bollapragada & Uday Rao, 1999. "Single-Stage Resource Allocation and Economic Lot Scheduling on Multiple, Nonidentical Production Lines," Management Science, INFORMS, vol. 45(6), pages 889-904, June.
    12. Murthy, Nagesh N. & Benton, W. C. & Rubin, Paul A., 2003. "Offsetting inventory cycles of items sharing storage," European Journal of Operational Research, Elsevier, vol. 150(2), pages 304-319, October.
    13. Lin, Yi-Kuei & Yeh, Cheng-Ta, 2011. "Maximal network reliability for a stochastic power transmission network," Reliability Engineering and System Safety, Elsevier, vol. 96(10), pages 1332-1339.
    14. Cui, Yaodong & Gu, Tianlong & Hu, Wei, 2009. "A cutting-and-inventory control problem in the manufacturing industry of stainless steel wares," Omega, Elsevier, vol. 37(4), pages 864-875, August.
    15. Pesenti, Raffaele & Ukovich, Walter, 2003. "Economic lot scheduling on multiple production lines with resource constraints," International Journal of Production Economics, Elsevier, vol. 81(1), pages 469-481, January.
    16. Zhao, Ze & Wang, Jianzhou & Zhao, Jing & Su, Zhongyue, 2012. "Using a Grey model optimized by Differential Evolution algorithm to forecast the per capita annual net income of rural households in China," Omega, Elsevier, vol. 40(5), pages 525-532.
    17. Minner, Stefan & Silver, Edward A., 2007. "Replenishment policies for multiple products with compound-Poisson demand that share a common warehouse," International Journal of Production Economics, Elsevier, vol. 108(1-2), pages 388-398, July.
    18. Ming-Jong Yao & Jia-Yen Huang, 2017. "Optimal lot-sizing and joint replenishment strategy under a piecewise linear warehousing cost structure," Journal of Intelligent Manufacturing, Springer, vol. 28(3), pages 791-803, March.
    19. Naiming Xie & Alan Pearman, 2014. "Forecasting energy consumption in China following instigation of an energy-saving policy," Natural Hazards: Journal of the International Society for the Prevention and Mitigation of Natural Hazards, Springer;International Society for the Prevention and Mitigation of Natural Hazards, vol. 74(2), pages 639-659, November.
    20. Lin, Yi-Kuei & Yeh, Cheng-Ta, 2012. "Determining the optimal double-component assignment for a stochastic computer network," Omega, Elsevier, vol. 40(1), pages 120-130, January.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:67:y:2019:i:5:p:1345-1361. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.