Formulations arc-flots pour un problème de découpe avec restes réutilisables et incertitudes sur les demandes

Nous étudions un problème de découpe avec restes réutilisables et incertitudes sur les demandes. Dans la littérature, une formulation stochastique à deux étapes du problème a était proposé. Nous introduisons une formalisation du problème avec un nombre arbitraire d'étapes. Puis, nous introduisons des méthodes de résolutions exactes axées sur la reformulation du problème en problème de flots dans des graphes ou hypergraphes. Pour les instances du problème avec un grand nombre de scénarios, nous proposons des méthodes de relaxation afin de calculer des bornes inférieures quand la relaxation linéaire ne peux être obtenue. Enfin, nous testons la pertinence de l’approche stochastique à l'aide d'un horizon roulant et en testant différents types d'oracle. Nous comparons nos différentes formulations pour des instances à deux étapes avec les instances de la littérature. Nous comparons également nos bornes inférieures introduites et nous montrons que certaines permettent d'aller plus loin en nombre d'étapes que la relaxation linéaire. Enfin, nous montrons qu'effectuer un horizon roulant avec un oracle à trois étapes permet de faire plus d'économies comparé à un oracle à deux étapes sur les instances de la littérature.