An accelerated scenario updating heuristic for stochastic production planning with set-up constraints in sawmills

摘要

In this article we propose an accelerated scenario updating heuristic to solve a real-world large-scale multistage stochastic mixed-integer model. Motivated from challenges we are facing in sawmills, the model corresponds to multi-period, multi-product production planning including setup constraints, with random yield and demand. While addressing real-life size instances of the problem, the resulting large-scale multi-stage stochastic mixed-integer model cannot be solved by commercial optimisation packages. Moreover, as the production planning model is a mixed-integer program without any special structure, developing decomposition and cutting plane algorithms to obtain good approximate solutions in reasonable time is not straightforward. We propose a successive approximation heuristic inspired from scenario updating heuristic which has been proposed for multi-stage stochastic models with partial recourse. The latter solves the problem by considering only a subset of scenarios which is updated at each iteration. We modify the scenario updating heuristic in two directions: (1) we modify the bounds on the optimal solution so as to make them valid for multi-stage stochastic models with full recourse, and (2) we propose a new scenario selection rule so as to increase the rate of convergence and the quality of solution. Computational experiments for a real-world large-scale sawmill production planning model verify the effectiveness of the proposed solution strategy in finding quickly good approximate solutions.