A state space augmentation algorithm for the replenishment cycle inventory policy

In this work we propose an efficient dynamic programming approach for computing replenishment cycle policy parameters under non‐stationary stochastic demand and service level constraints. The replenishment cycle policy is a popular inventory control policy typically employed for dampening planning instability. The approach proposed in this work achieves a significant computational efficiency and it can solve any relevant size instance in trivial time. Our method exploits the well known concept of state space relaxation. A filtering procedure and an augmenting procedure for the state space graph are proposed. Starting from a relaxed state space graph our method tries to remove provably suboptimal arcs and states (filtering) and then it tries to efficiently build up (augmenting) a reduced state space graph representing the original problem. Our experimental results show that the filtering procedure and the augmenting procedure often generate a small filtered state space graph, which can be easily processed using dynamic programming in order to produce a solution for the original problem.