A Benders decomposition-based procedure to solve a finite horizon, multi-product, capacitated production planning problem with stochastic demand.

摘要

The focus of this research was the development of a solution procedure to solve a “finite horizon, multi-product, capacitated production-planning problem with stochastic demand.” The motivation for this study was an aggregate planning problem faced by a leading foundry. This problem was formulated as a nonlinear program with the following properties: (1) The objective function is the sum of continuous convex functions each involving only one variable. (2) The feasible region is convex and formed by a set of linear constraints.; Even though this research focuses on a specific problem, the solution procedure can be used for other models with these same properties. The solution procedure was based on the decomposition technique of Benders (1962). Applying the Benders decomposition technique separates the aggregate planning problem into a linear programming sub-problem that is easy to solve and a nonlinear programming master problem with a linear objective function and nonlinear constraints. The resulting master problem is at least as difficult to solve as the original aggregate planning problem. The primary contribution of this research effort was the development of a solution procedure to solve this master problem.; The Benders master problem was analyzed in detail and reformulated such that the non-linearity is restricted to the objective function. A solution procedure to solve this reformulated master problem was then developed. This procedure is based on the gradient projection method of Rosen (1964). Results that are useful to identify the initial starting solution for the master problem were also developed.; Finally, the solution procedure was extensively tested to determine how various factors such as problem size affect the solution time. Experiments revealed that the solution time of the algorithm was exponentially related to the problem size. This was further validated by a stress test that revealed that the algorithm failed to solve large problems with more than 16,000 variables and constraints. To benchmark the performance of the algorithm, the solution times were also compared with those of a commercial solver. The mean solution time of the commercial solver was two orders of magnitude larger than that of the algorithm. As a third validation step, the algorithm was used to solve some instances of the real-world problem faced by the foundry.