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

Visentin A., Prestwich S., Rossi R., TARIM Ş. A.

Computers and Operations Research, cilt.158, 2023 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 158
  • Basım Tarihi: 2023
  • Doi Numarası: 10.1016/j.cor.2023.106289
  • Dergi Adı: Computers and Operations Research
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, PASCAL, ABI/INFORM, Aerospace Database, Applied Science & Technology Source, Business Source Elite, Business Source Premier, Communication Abstracts, Compendex, Computer & Applied Sciences, INSPEC, Metadex, zbMATH, Civil Engineering Abstracts
  • Anahtar Kelimeler: (R,s,S) policy, Demand uncertainty, Inventory, Stochastic lot sizing
  • Hacettepe Üniversitesi Adresli: Evet

Özet

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.