Stochastic dynamic programming heuristic for the (R, s, S) policy parameters computation

Andrea Visentin, Steven Prestwich, Roberto Rossi, S Armagan Tarim

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

This paper introduces a new stochastic dynamic program (SDP) based heuristic to compute the (R, s, S) policy parameters for the non-stationary stochastic lot-sizing problem with backlogging of the excessive demand, fixed order and review costs, and linear holding and penalty costs. Our model combines a greedy relaxation of the problem that considers replenishment cycles independent with a modified version of Scarf’s (s, S) SDP. A simple model implementation requires a prohibitive computational effort to compute the parameters. However, leveraging the K-convexity property and deploying memoisation techniques strongly reduce the computational effort required. The resulting algorithm is considerably faster than the state-of-the-art, extending its applicability by practitioners. An extensive computational study shows that our approach computes the optimal policy in more than 97% of the analysed instances, with a 0.02% average optimality gap.
Original languageEnglish
JournalComputers and Operations Research
Early online date27 May 2023
Publication statusPublished - Oct 2023

Keywords / Materials (for Non-textual outputs)

  • inventory
  • (R,s,S) policy
  • demand uncertainty
  • stochastic lot sizing


Dive into the research topics of 'Stochastic dynamic programming heuristic for the (R, s, S) policy parameters computation'. Together they form a unique fingerprint.

Cite this