The complexity of the staggering problem, and other classical inventory problems

The authors consider a multi-item inventory system with a constraint or penalty associated with the peak usage of a single resource, such as warehouse volume, floor space, or working capital. A number of classical, deterministic, inventory problems have been developed for these systems. Embedded, in these classical inventory problems, is the staggering problem. The staggering problem, consists of time phasing the arrival of the orders to minimize the peak usage of the resource. The authors show that the staggering problem is NP-complete in the strong sense even if only one item has a different reorder interval. This result is used to prove that the above classical inventory problems are also NP-complete in the strong sense, thereby justifying the effort invested over the last three decades to develop effective heuristics for these problems.