Stochastic Dual Dynamic Programming for Multiechelon Lot Sizing with Component Substitution
Résumé
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 relevant not only 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 multistage 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. The proposed method can plan with up to 10 decision stages and 20 scenarios per stage, which results in 20 10 scenario paths in total. Moreover, as the heuristic version of SDDP can replan to account for new information in less than a second, it is convenient in a dynamic context.
Fichier principal
Thevenin_Adulyasak_Cordeau_2022_IJOC_Final (1).pdf (423.59 Ko)
Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)