(498a) A New Methodology for Integrated Planning and Scheduling Using Multi-Level Optimization

The objective of integrated planning and scheduling is to coordinate the planning and scheduling decision levels to avoid infeasible operations and guarantee consistent plant operations. The main challenges in the integration of planning and scheduling is the fact that the problems are at different time scales and that the resulted optimization model includes a very large number of variables and constraints. Although significant effort has been made towards the integration of planning and scheduling problems, development of consistent planning and scheduling model and efficient solution strategy is still being identified as one of the challenges in enterprise-wide optimization (Grossmann 2005).

Two main methodologies have been proposed in the literature for the integrated planning and scheduling. The first type of methods follows the simultaneous approach where the detailed scheduling problem is solved for the entire time horizon. The scheduling model is incorporated into the planning problem, which leads to very large scale multiperiod optimization problem. Different solution strategies based on aggregation and decomposition has been studied in the literature (Schilling and Pantelides 1999, Grossmann, Van den Heever et al. 2002). The other type of methods follow the hierarchical approach where the overall problem is decomposed into upper level planning and lower level scheduling problem that can be decoupled. In this method the upper level aggregate model is solved to set the production targets resulting in an upper bound to the original problem followed by a detailed scheduling problem solution whish is individually optimized with fixed targets, thus decreasing the computational effort. The challenge lies in developing an aggregated model that yields tight bounds to reduce the number of upper and lower level problems (Wilkinson, Shah et al. 1995, Orcun, Altinel et al. 2001, Zhu and Majozi 2001).

In this work, we propose a new formulation of the integrated planning and scheduling problem which is a bilevel hierarchical problem with multiple lower level problems (scheduling subproblems in different periods and same time horizon). Based on this formulation we then develop an alternative solution methodology which combines the application of parametric programming and convexification technique to improve the computational efficiency but still maintain the quality of the solution for the planning and scheduling integration problem. It should be noticed that each lower level scheduling subproblem is independent from the other subproblems and they are only linked through the upper lever planning decision variables (production target, inventory level). Thus by treating the upper level decision variables in the lower level scheduling problem as parameters, all the lower level problems correspond exactly to the same multiparametric problems and give rise to the same parametric solution. Thus solving only one parametric scheduling problem, the characteristics of different periods are captured through the parametric solution composed by a set of parametric objective functions and critical regions (Li and Ierapetritou 2007), which are further used to reformulate the integrated planning and scheduling problem.

Different strategies for solving the reformulated integrated planning and scheduling problem are further studied in this work. The first strategy adopts a direct reformulation of the problem through the use of big-M constraints, which transform the logic constraints representing the critical regions through introducing additional binary variables and consequently a new MILP problem is formulated. The main disadvantage of this method is brought by the number of critical regions in the parametric solution. It is shown that the number of binary variables is equal to the product of planning periods times the critical regions. Comparing with original planning and scheduling integration model, the problem complexity will be reduced only if the critical regions are less than the binary variables in the scheduling model. To avoid this limitation, a second strategy based on convexification of the parametric solutions (Sun, Luo et al. 2007) is proposed given that the parametric objective function of the scheduling subproblem is nonsmooth monotone function and the boundary of the feasible region can also be described with a nonsmooth monotone function (Li and Ierapetritou 2007). Thus the supporting hyperplane method for convex problems (Slyke and Wets 1969) can be applied and a new formulation is derived which contains only continuous variables of the planning level decision variables. The scale of the original bilevel integrated problem is greatly reduced because the scheduling subproblems are substituted with a set of support hyperplane constraints to describe the objective function and the feasible region. Furthermore, the method ensures the consistency between planning and scheduling problem without sacrificing the solution accuracy. Applications of the proposed methodology on several examples illustrate the effectiveness of the proposed methodology.

[1] Grossmann, I. (2005). "Enterprise-wide optimization: A new frontier in process systems engineering." AIChE J. 51: 1846-1857.

[2] Grossmann, I. E., S. A. Van den Heever, et al. (2002). "Discrete optimization methods and their role in the integration of planning and scheduling." AIChE Symp. Ser. 98: 150.

[3] Li, Z. and M. G. Ierapetritou (2007). "Process scheduling under uncertainty using multiparametric programming." AIChE J. 53: 3183-3203.

[4] Orcun, S., I. K. Altinel, et al. (2001). "General continuous-time models for production planning and scheduling of batch processing plants: Mixed Integer linear program formulations and computational issues." Comput. Chem. Eng. 25: 371-389.

[5] Schilling, G. and C. C. Pantelides (1999). "Optimal periodic scheduling of multipurpose plants." Comput. Chem. Eng. 23: 635-655.

[6] Sun, X. L., H. Z. Luo, et al. (2007). "Convexification of Nonsmooth Monotone Functions." J. Opt. Theor. Appl. 132: 339-351.

[7] Wilkinson, S. J., N. Shah, et al. (1995). "Aggregate modeling of multipurpose plant operation." Comput. Chem. Eng. 19: S583-S588.

[8] Zhu, X. X. and T. Majozi (2001). "Novel continuous-time MILP formulation for multipurpose batch plants. 2. Integrated planning and scheduling." Ind. Eng. Chem. Res. 40: 5621-5634.

[9] Slyke R. V. and R. J. Wets (1969). "L-shaped linear programs with applications to optimal control and stochastic linear programming", SIAM J. Appl. Math.,17: 638-663.