A comparison of inventory replenishment heuristics for minimizing maximum storage

Consider the problem of minimizing the maximum storage requirement resulting from the once-per-cycle replenishment of several items. Demand is assumed to be known and constant, and no backlogging is permitted. By contrast with previous models, replenishment may take place only at k discrete points in time. We prove that this problem is binary NP-hard for fixed k. Consequently, a natural heuristic based on the rounding of optimal continuous time solutions is described. This heuristic provides a worst case performance ratio of 1+ C/k, where C is a numerical constant, and 1/2 < C < 2. A heuristic borrowed from multiprocessor scheduling provides a worst case performance ratio of 2. Extensive computational testing indicates that the solutions delivered by the heuristics are, on average, very close to optimal in value.