A State Space Augmentation Algorithm for the Replenishment Cycle Inventory Policy

R. Rossi, S.A. Tarim, B. Hnich, S.D. Prestwich

Research output: Contribution to journalArticleAcademicpeer-review

10 Citations (Scopus)


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.
Original languageEnglish
Pages (from-to)377-384
JournalInternational Journal of Production Economics
Issue number1
Publication statusPublished - 2011


  • service-level constraints
  • shortest-path problem
  • lot-sizing problem
  • strategies

Fingerprint Dive into the research topics of 'A State Space Augmentation Algorithm for the Replenishment Cycle Inventory Policy'. Together they form a unique fingerprint.

Cite this