Multi-Item Replenishment and Storage Problem (MIRSP): Heuristics and Bounds

Automated warehouses are often faced with the problem of smoothing their stock volume over time in order to minimize the cost due to space acquisition. In this paper, we consider an infinite-horizon, multi-item replenishment problem: In addition to the usual setup and holding costs incurred by each item, an extra charge proportional to the peak stock volume at the warehouse is due. This last cost raises the need for careful coordination while making decisions on the individual item order policies. We restrict ourselves to the class of policies that follows a stationary rule for each item separately. We derive a lower bound on the optimal average cost over all policies in this class. Then we investigate the worst case of the Rotation Cycle policy. We show that depending on the problem's parameters, the Rotation Cycle policy may yield an extremely good solution but in other settings this heuristic may generate an extremely poor policy. We also develop a new heuristic whose performance is at least as good as that of the Rotation Cycle procedure, and moreover, it is guaranteed to come, independently of the problem's parameters, within no more than 41% of the optimal solution!