IDEAS home Printed from https://ideas.repec.org/a/wly/navres/v36y1989i4p399-418.html
   My bibliography  Save this article

The inventory packing problem

Author

Listed:
  • Nicholas G. Hall

Abstract

We study the problem of finding the minimum number of identical storage areas required to hold n items for which demand is known and constant. The replenishments of the items within a single storage area may be time phased so as to minimize the maximum total storage capacity required at any time. This is the inventory‐packing problem, which can be considered as a variant of the well‐known bin‐packing problem, where one constraint is nonlinear. We study the worst‐case performance of six heuristics used for that earlier problem since the recognition version of the inventory‐packing problem is shown to be NP complete. In addition, we describe several new heuristics developed specifically for the inventory‐packing problem, and also study their worst‐case performance. Any heuristic which only opens a bin when an item will not fit in any (respectively, the last) open bin needs, asymptotically, no more than 25/12 (resp., 9/4) times the optimal number of bins. Improved performance bounds are obtainable if the range from which item sizes are taken is known to be restricted. Extensive computational testing indicates that the solutions delivered by these heuristics are, for most problems, very close to optimal in value.

Suggested Citation

  • Nicholas G. Hall, 1989. "The inventory packing problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 36(4), pages 399-418, August.
    • Handle: RePEc:wly:navres:v:36:y:1989:i:4:p:399-418
    DOI: 10.1002/1520-6750(198908)36:43.0.CO;2-M
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/1520-6750(198908)36:43.0.CO;2-M
    Download Restriction: no
    File URL: https://libkey.io/10.1002/1520-6750(198908)36:43.0.CO;2-M?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. Marshall L. Fisher, 1980. "Worst-Case Analysis of Heuristic Algorithms," Management Science, INFORMS, vol. 26(1), pages 1-17, January.
    2. Dominique J. Nocturne, 1973. "Note--Economic Ordering Frequency for Several Items Jointly Replenished," Management Science, INFORMS, vol. 19(9), pages 1093-1096, May.
    3. Salah E. Elmaghraby, 1978. "The Economic Lot Scheduling Problem (ELSP): Review and Extensions," Management Science, INFORMS, vol. 24(6), pages 587-598, February.
    4. Hall, Nicholas G., 1988. "Separate vs. joint replenishment policies with maximum storage requirement costs," European Journal of Operational Research, Elsevier, vol. 36(2), pages 180-185, August.
    5. Frank T. Shu, 1971. "Economic Ordering Frequency for two Items Jointly Replenished," Management Science, INFORMS, vol. 17(6), pages 406-410, February.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Kurt R. Heidelberg & Gregory S. Parnell & James E. Ames, 1998. "Automated air load planning," Naval Research Logistics (NRL), John Wiley & Sons, vol. 45(8), pages 751-768, December.

    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. Tsai, Chi-Yang & Yeh, Szu-Wei, 2008. "A multiple objective particle swarm optimization approach for inventory classification," International Journal of Production Economics, Elsevier, vol. 114(2), pages 656-666, August.
    2. Tamar Cohen-Hillel & Liron Yedidsion, 2018. "The Periodic Joint Replenishment Problem Is Strongly 𝒩𝒫-Hard," Mathematics of Operations Research, INFORMS, vol. 43(4), pages 1269-1289, November.
    3. 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.
    4. E A Silver, 2004. "An overview of heuristic solution methods," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(9), pages 936-956, September.
    5. Heuts, R.M.J. & Nederstigt, P. & Roebroek, W. & Selen, W.J., 1992. "Multi-product cycling with packaging in the process industry," Other publications TiSEM 533d6bbb-e61a-4e4b-a44e-1, Tilburg University, School of Economics and Management.
    6. Robert R. Inman & Philip C. Jones & Guillermo M. Gallego, 1991. "Economic lot scheduling of fully loaded processes with external setups," Naval Research Logistics (NRL), John Wiley & Sons, vol. 38(5), pages 699-713, October.
    7. Hein, Fanny & Almeder, Christian, 2016. "Quantitative insights into the integrated supply vehicle routing and production planning problem," International Journal of Production Economics, Elsevier, vol. 177(C), pages 66-76.
    8. Bautista, Joaquín & Alfaro, Rocío & Batalla, Cristina, 2015. "Modeling and solving the mixed-model sequencing problem to improve productivity," International Journal of Production Economics, Elsevier, vol. 161(C), pages 83-95.
    9. Siddhartha Syam & Bala Shetty, 1998. "Coordinated replenishments from multiple suppliers with price discounts," Naval Research Logistics (NRL), John Wiley & Sons, vol. 45(6), pages 579-598, September.
    10. Coelho, Leandro C. & Laporte, Gilbert, 2014. "Improved solutions for inventory-routing problems through valid inequalities and input ordering," International Journal of Production Economics, Elsevier, vol. 155(C), pages 391-397.
    11. Hauser, John R. & Urban, Glen L. & Weinberg, Bruce D., 1992. "Time flies when you're having fun : how consumers allocate their time when evaluating products," Working papers 3439-92., Massachusetts Institute of Technology (MIT), Sloan School of Management.
    12. Sharma, R.R.K. & Berry, V., 2007. "Developing new formulations and relaxations of single stage capacitated warehouse location problem (SSCWLP): Empirical investigation for assessing relative strengths and computational effort," European Journal of Operational Research, Elsevier, vol. 177(2), pages 803-812, March.
    13. Heuts, R.M.J. & Nederstigt, P. & Roebroek, W. & Selen, W.J., 1992. "Multi-product cycling with packaging in the process industry," Research Memorandum FEW 544, Tilburg University, School of Economics and Management.
    14. Olsen, Anne L., 2008. "Inventory replenishment with interdependent ordering costs: An evolutionary algorithm solution," International Journal of Production Economics, Elsevier, vol. 113(1), pages 359-369, May.
    15. Brander, Par & Forsberg, Rolf, 2006. "Determination of safety stocks for cyclic schedules with stochastic demands," International Journal of Production Economics, Elsevier, vol. 104(2), pages 271-295, December.
    16. He-Yau Kang & Amy H.I. Lee & Chien-Wei Wu & Cheng-Han Lee, 2017. "An efficient method for dynamic-demand joint replenishment problem with multiple suppliers and multiple vehicles," International Journal of Production Research, Taylor & Francis Journals, vol. 55(4), pages 1065-1084, February.
    17. Lopez de Haro, Santiago & Gershwin, Stanley B. & Rosenfield, Donald B., 2009. "Schedule evaluation in unstable manufacturing environments," International Journal of Production Economics, Elsevier, vol. 121(1), pages 183-194, September.
    18. Vaughan, Timothy S., 2007. "Cyclical schedules vs. dynamic sequencing: Replenishment dynamics and inventory efficiency," International Journal of Production Economics, Elsevier, vol. 107(2), pages 518-527, June.
    19. Guillermo Gallego & Robin Roundy, 1992. "The economic lot scheduling problem with finite backorder costs," Naval Research Logistics (NRL), John Wiley & Sons, vol. 39(5), pages 729-739, August.
    20. Brander, Par & Leven, Erik & Segerstedt, Anders, 2005. "Lot sizes in a capacity constrained facility--a simulation study of stationary stochastic demand," International Journal of Production Economics, Elsevier, vol. 93(1), pages 375-386, January.

    More about this item

    Statistics

    Access and download statistics

    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:wly:navres:v:36:y:1989:i:4:p:399-418. 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: Wiley Content Delivery (email available below). General contact details of provider: https://doi.org/10.1002/(ISSN)1520-6750 .

    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.