برنامه ریزی تولید و یکپارچه سازی برنامه ریزی از طریق تقویت لاگرانژی بهینه سازی

To improve the quality of decision making in the process operations, it is essential to implement integrated planning and scheduling optimization. Major challenge for the integration lies in that the corresponding optimization problem is generally hard to solve because of the intractable model size. In this paper, augmented Lagrangian method is applied to solve the full-space integration problem which takes a block angular structure. To resolve the non-separability issue in the augmented Lagrangian relaxation, we study the traditional method which approximates the cross-product term through linearization and also propose a new decomposition strategy based on two-level optimization. The results from case study 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.

Production planning and scheduling belong to different decision making levels in process operations, they are also closely related since the result of planning problem is the production target of scheduling problem. In process industry, the commonly used planning and scheduling decision making strategy generally follows a hierarchical approach, in which the planning problem is solved first to define the production targets and the scheduling problem is solved next to meet these targets. However, there exists a big disadvantage in this traditional strategy since there is no interaction between the two decision levels, i.e., the planning decisions generated might cause infeasible scheduling subproblems. At the planning level, the effects of changeovers and daily inventories are neglected, which tends to produce optimistic estimates that cannot be realized at the scheduling level, i.e., a solution determined at the planning level does not necessarily lead to feasible schedules. Moreover, the optimality of the planning solution cannot be ensured because the planning level problem might not provide an accurate estimation of the production cost, which should be calculated from detailed tasks determined by the scheduling problem. Therefore, it is important and necessary to develop methodologies that can effectively integrate production planning and scheduling. However, since production planning and scheduling are dealing with different time scales, the major challenge for the integration lies in the large problem size of the resulted optimization model. A direct way for addressing the integrated planning and scheduling problems is to formulate a single simultaneous planning and scheduling model that spans the entire planning horizon of interest. However, when typical planning horizons are considered, the size of this detailed model becomes intractable, because of the potential exponential increase in the computation time. To overcome the above difficulty, most of the work appeared in the literature aim at decreasing the problem scale through different types of problem reduction methodologies and developing efficient solution strategies as summarized by Grossmann, Van Den Heever, and Harjunkoski (2002) and Maravelias and Sung (2008). Generally, the existing work in the area of planning and scheduling integration can be summarized as follows. The first type of methods is based on decomposition in a hierarchical way through iterative solution procedure. Through a hierarchical decomposition of the integration problem, detailed scheduling constraints are not incorporated into the upper level aggregate planning model, on the other hand, information is passed from the aggregate planning problem to a set of detailed scheduling problems and these scheduling problems are separated based on the 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 (Bassett et al., 1996, Erdirik-Dogan and Grossmann, 2006, Munawar and Gudi, 2005 and Papageorgiou and Pantelides, 1996). The second type of method, which is also called rolling horizon approach, considers a relative rough model for the far future planning periods in the integrated planning and scheduling model, i.e., 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. Applications of this kind of strategy can be found in Dimitriadis, Shah, and Pantelides (1997), Sand, Engell, Märkert, Schultz, and Schultz (2000), Wu and Ierapetritou (2007), and 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 (Castro et al., 2003, Wu and Ierapetritou, 2004 and Zhu and Majozi, 2001). 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 & Maravelias, 2007). Except the different methods for the integrated planning and scheduling summarized above, another approach is based on the study of the special structure of the mathematical programming model for the integration problem and aims at developing efficient decomposition techniques to solve the optimization problem directly. Lagrangian relaxation is an approach that is often applied to models with a block angular structure. In such models, distinct blocks of variables and constraints can be identified and they are linked through a few “linking” constraints and variables. To our knowledge, Lagrangian relaxation has been widely applied onto planning and scheduling problems for different applications including unit commitment in power industry (Padhy, 2004), midterm production planning (Gupta & Maranas, 1999), and combined transportation and scheduling (Equi, Gallo, Marziale, & Weintraub, 1997), etc. However, the major drawback of Lagrangian relaxation method is that there is duality gap between the solution of the Lagrangian dual problem and the solution of original problem, and often the feasibility of the solution needs to be recovered through heuristic steps. So it is often only used as the bounding step in the branch and bound framework. The disadvantage of Lagrangian relaxation can be avoided by augmented Lagrangian relaxation (ALR) method, which has been used in several applications in areas such as power generation scheduling (Carpentier, Cohen, Culioli, & Renaud, 1996), multidisciplinary design (Tosserams, Etman, & Rooda, 2008), etc. One drawback of ALR method is the non-separability of the relaxed problem, which has also received wide attention in the literature. In this paper, we propose to apply the ALR method on the planning and scheduling integration problem which takes a block angular model structure, and also propose a new decomposition strategy to address the non-separability issue in the ALR solution procedure, which can be used to decompose the relaxed problem exactly without any approximation technique as presented in the literature. The content of this paper is organized as follows. The problem formulation of the integrated planning and scheduling problem is first presented in Section 2. The general augmented Lagrangian solution method is presented in Section 3. Detail reformulation and decomposition strategies for the planning and scheduling integration problem are presented in Section 4. The proposed method is studied in Section 5 through a case study and the paper concludes in Section 6.

To address the problem of integrated production planning and scheduling, a decomposition algorithm based on augmented Lagrangian is proposed in this paper. Based on the special structure of the optimization model, auxiliary variables and coupling constraints for the linking variables are first introduced, the coupling constraints are then relaxed and the resulted augmented Lagrangian relaxation problem is solved through decomposition technique. We also propose a new decomposition strategy based on two-level optimization of the relaxation problem and compare its performance with traditional approximation based decomposition strategy. The results from a case study show that the augmented Lagrangian method can effectively generate feasible solution for the original problem, and the new decomposition strategy can generate better feasible solution than the traditional approximation based method with the trade-off of using more or comparable computation efforts. Furthermore, it is also worth noticing that the computation time in the method is mostly spent on the solution of scheduling subproblems. By realizing that the subproblems can be further solved in parallel, we can reduce further the computation time through parallel computing. The main advantages of the augmented Lagrangian method are: (a) the convergence of the algorithm is ensured without the need to solve the relaxation problem to optimality; (b) it can be easily parallelized; and (c) it is able to avoid the duality gap. Furthermore, it can be also used within a bounding procedure since a feasible solution is always ensured. In summary, the augmented Lagrangian method is appropriate for the solution of the planning and scheduling integration problem. Future work will include improving the solution of the relaxation problem to find the global optimal solution of the original problem.