A Fully Polynomial Time Approximation Scheme for Single-Item Stochastic Lot-Sizing Problems with Discrete Demand

The single-item stochastic lot-sizing problem is to find an inventory replenishment policy in the presence of a stochastic demand under periodic review and finite time horizon. The computational intractability of computing an optimal policy is widely believed and therefore approximation algorithms should be considered. To the best of our knowledge, this is the first work that develops a fully polynomial time approximation scheme for this problem. In other words, we design a tractable polynomial time algorithm that finds a policy that is arbitrarily close in the relative sense to the value of an optimal policy. In addition, we formally prove that finding an optimal policy is intractable in the standard sense