Groupe d’études et de recherche en analyse des décisions


Stochastic dual dynamic programming for multi-echelon lot-sizing with component substitution

, et

This work investigates lot-sizing with component substitution under demand uncertainty. The integration of component substitution with lot-sizing in an uncertain demand context is important because the consolidation of the demand for components naturally allows risk pooling and reduces operating costs. The considered problem is not only relevant in a production context, but also in the context of distribution planning. We propose a stochastic programming formulation for the static-dynamic type of uncertainty, where the setup decisions are frozen, but the production and consumption quantities are decided dynamically. To tackle the scalability issues commonly encountered in multi-stage stochastic optimization, this paper investigates the use of stochastic dual dynamic programming (SDDP). In addition, we consider various improvements of SDDP, including the use of strong cuts, the fast generation of cuts by solving the linear relaxation of the problem, and retaining the average demand scenarios. Finally, we propose two heuristics, namely, a hybrid of progressive hedging with SDDP, and a heuristic version of SDDP. Computational experiments conducted on well-known instances from the literature show that the heuristic version of SDDP outperforms other methods. Indeed, the proposed method can plan with up to ten decision stages and 20 scenarios per stage, which results in \(20^{10}\) possible scenarios in total. Finally, as the heuristic version of SDDP can re-plan to account for new information in less than a second, it is convenient in a dynamic context.

, 25 pages