The inventory packing problem

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.