(423c) Production Planning and Scheduling Integration through Augmented Lagrangian Optimization

The objective of planning and scheduling integration is to coordinate the production planning and scheduling decision levels to avoid infeasible operations and guarantee consistent plant operations. The direct way for addressing the integrated planning and scheduling problems is to formulate a single simultaneous planning and scheduling model (also called full-space model) that spans the entire planning horizon of interest. However, when typical planning horizons are considered, the size of this detailed model becomes intractable, due to the exponential increase in computational time. To overcome the above difficulty, most of the work appeared in the literature aim at decreasing the problem size using problem reduction methodologies and developing efficient solution strategies, which can be further classified to the following types.

The first type of methods is based on decomposition in a hierarchical way through iterative solution procedure, where information is passed from the aggregate planning problem to a set of detailed scheduling problems which are solved independently using temporal decomposition. Thus, the problems that need to be solved include a relative simple planning problem and a series of scheduling subproblems. To ensure the feasibility and optimality of the solution, it is further necessary to develop effective algorithms to improve the solution using additional cuts in the planning level within an iterative solution framework (e.g., Dogan and Grossmann, 2006). The second type of methods, which is also called rolling horizon approach, consider a relative rough model for the far future planning periods in the integrated planning and scheduling model, whereas detailed scheduling models are only used for a few early periods and aggregate models are used for later periods. The production targets for the early periods are directly implemented, while the production targets for the later periods are updated along with the rolling horizon (e.g., Verderame and Floudas, 2008). Thirdly, for the cases where there is no plant and market variability, campaign mode can be applied to generate an easy-to-implement and profitable process operations plan. In a periodic scheduling framework, the planning and scheduling integration problem is replaced by establishing an operation schedule and executing it repeatedly (e.g., Wu and Ierapetritou, 2004). Finally, other than using the detailed scheduling model in the integrated planning, surrogate methods aim at deriving the scheduling feasibility and production cost function first and then incorporating them into the integrated problem. This avoids the disadvantage of large scale and complex model which directly incorporate the detailed scheduling model into aggregating planning model as shown in (Sung and Maravelias, 2007).

Although significant efforts, summarized above, have 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 (Maravelias and Sung, 2008). Different from the above methods, in this work, we propose an approach based on augmented Lagrangian relaxation method and aim to solve the full-space integration problem.

First, it is shown that the full-space integration problem takes a block-angular similar structure where distinct blocks of variables and constraints can be identified that are linked with a few ?linking? constraints and variables. Thus, through the introduction of auxiliary variables and coupling constraints related to those planning decision variables that link scheduling constraints of different planning periods, relaxation method can be used to decompose the integration problem. The main drawback of classical Lagrangian relaxation method is that there is duality gap and the feasibility of the solution needs to be recovered through heuristic steps. In order to avoid this problem we propose to apply augmented Lagrangian relaxation method, which has retrieved several applications in areas such as multidisciplinary design, power generation scheduling, etc.

The main disadvantage of the augmented Lagrangian method is the non-separability of the augmented Lagrangian relaxation problem. To resolve the non-separability issue, we study the traditional method which approximates the cross product term through linearization (Ruszczynski, 1995), and also propose a new decomposition strategy based on two-level optimization, where the augmented Lagrangian relaxation problem is reformulated into two levels. In the first level, the relaxation problem is solved only with respect to the planning decision variables through an iterative algorithm via continuous local solver to get an approximate solution which is feasible but not necessary optimal. In the second level, a set of scheduling subproblems is solved at every iteration with fixed planning decision variables. The proposed strategy is supported by the work of Andreani et al., 2008, which provides theoretic proof that even if the augmented Lagrangian relaxation problem is not solved to optimality at every iteration, Constant Positive Linear Dependence (CPLD) based convergence property are still ensured under certain conditions: the objective function and those constraints to be relaxed admit continuous first derivatives and the rest constraints from a close set.

A case study is used in this work to illustrate the results of the proposed methodology and compare with the most commonly used approximation methods. The results show that the augmented Lagrangian method is effective in solving the large integration problem and generating a feasible solution. Furthermore, the proposed decomposition strategy based on two-level optimization can get better feasible solution than the traditional linearization method with the trade-off of spending relative more computational effort mainly due to the solution of scheduling subproblems. By realizing that these subproblems can be further solved in parallel, we can reduce further the computation time through parallel computing.

Dogan, M.E., Grossmann, I.E., 2006. A Decomposition Method for the Simultaneous Planning and Scheduling of Single-Stage Continuous Multiproduct Plants. Ind. Eng. Chem. Res. 45, 299-315.

Verderame, P.M., Floudas, C.A., 2008. Integrated operational planning and medium-term scheduling of a large-scale industrial batch plants. Ind. Eng. Chem. Res 47, 4845-4860.

Wu, D., Ierapetritou, M.G., 2004. Cyclic short-term scheduling of multiproduct batch plants using continuous-time representation. Computers & Chemical Engineering 28, 2271-2286.

Sung, C., Maravelias, C.T., 2007. An attainable region approach for effective production planning of multi-product processes. AIChE Journal 53, 1298-1315.

Maravelias, C.T., Sung, C., 2008. Integration of production planning and scheduling: overview, challenges and opportunities. Proceedings Foundations of Computer-Aided Process Operations (FOCAPO 2008) 13-22.

Ruszczynski, A., 1995. On convergence of an augmented Lagrangian decomposition method for sparse convex optimization. Mathematics of Operations Research 20, 634-656.

Andreani, R., Birgin, E.G., Martinez, J.M., Schuverdt, M.L., 2008. On Augmented Lagrangian methods with general lower-level constraints. SIAM Journal on Optimization 18, 1286-1309.