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, an infinite-horizon, multi-item replenishment problem is considered: 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. The paper is restricted to the class of policies that follows a stationary rule for each item separately. It derives a lower bound on the optimal average cost over all policies in this class. Then the paper investigates the worst case of the Rotation Cycle policy. It shows 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. The paper also develops 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!