(301b) Hybrid Bilevel-Lagrangean Decomposition Scheme for the Integration of Planning and Scheduling of a Network of Batch Plants

The Process Systems Engineering (PSE) and Operations Research (OR) communities have contributed with models and solution strategies to tackle the decision-making on three different time scales in Enterprise-Wide Optimization (EWO) problems. The long-term decisions (years) belong to the strategic level and are usually related to investments, plant capacity expansion and retrofit; the medium-term decisions (months, years) pertain to planning and commonly refer to production planning and inventory control; the short-term decisions (days, weeks) represent the scheduling of operations, i.e. determining the detailed timing and sequencing of operations.

The focus of this work is on integrated planning and scheduling for batch processes. Excellent reviews for these problems are available in the literature, Kallrath (2002) and Méndez et al. (2006). However, when attempting to solve large-scale industrial problems, some authors have identified the need to decompose the problem in smaller and sometimes independent subproblems. For instance, Iyer & Grossmann (1998) proposed a Bilevel Decomposition algorithm, which involves solving an aggregate formulation in the upper level and a detailed formulation in the lower level with some decisions fixed by the upper level. Lagrangean Decomposition, a particular case of Lagrangean Relaxation (Guignard, 2003), has also been investigated by Terrazas-Moreno et al. (2011) who decomposed their planning problem temporally and spatially in order to solve large instances.

This work deals with the integration of planning and scheduling of a network of batch plants that arises in industrial practice. The network consists of single-stage, multiproduct batch plants located in different sites, which can exchange intermediate products in order to blend them to obtain final products. The time horizon is given and divided into multiple time periods, at the end of which the customer demands have to be exactly satisfied. The planning model is based on the detailed planning model proposed by Erdirik-Dogan & Grossmann (2007), which incorporates Traveling Salesman Problem constraints to predict the sequence-dependent changeovers between products, within and across time periods, without capturing the detailed timing of operations. The scheduling model is based on the unit-specific general precedence (USGP) model proposed by Kopanos, Laínez, & Puigjaner (2009) with two new features: (1) number of batches is allowed to be variable, so it becomes part of the optimization problem, and (2) sequence-dependent changeovers are allowed to occur across time periods.

The solution of the full-space problem, i.e. scheduling formulation, for large-scale industrial problems becomes impractical mainly due to the problem size. Therefore, we investigate the combination of two decomposition schemes. The Bilevel Decomposition (BD) framework comprises the solution of an upper-level planning problem, which is an aggregate formulation of the scheduling model, and the solution of a lower-level scheduling problem by fixing some decisions from the solution of the upper level problem. The main motivation behind this approach is to attempt to match the planning and scheduling solutions in a loop structure. For real world applications, the planning problem can still be challenging to solve; hence, we further decompose it using Temporal Lagrangean Decomposition (TLD) by taking advantage of the multiperiod aspect of the problem and dualizing the inventory and assignment constraints. This decomposition yields smaller and independent subproblems for each time period, which are solved in parallel. The TLD of the planning problem is solved in an inner loop of the BD loop. The proposed hybrid decomposition framework is illustrated with three examples of increasing size; the first is a motivating small example in which the optimal schedule obtained by solving the full-space problem is compared with the one obtained by solving the decomposed problem; the second and third examples are medium- and large-scale problems and the computational advantage of the decomposition approach is demonstrated against the solution of the respective full-space problems.

References

Erdirik-Dogan, M., & Grossmann, I. E. (2007). Planning Models for Parallel Batch Reactors with Sequence-Dependent Changeovers. AIChE Journal, 53(9), 2284-2300.

Guignard, M. (2003). Lagrangean Relaxation. Top, 11(2), 151-228.

Iyer, R. R., & Grossmann, I. E. (1998). A Bilevel Decomposition Algorithm for Long-Range Planning of Process Networks. Industrial & Engineering Chemistry Research, 37(2), 474-481.

Kallrath, J. (2002). Planning and scheduling in the process industry. OR Spectrum, 24(3), 219-250.

Kopanos, G. M., Laínez, M. J., & Puigjaner, L. (2009). An Efficient Mixed-Integer Linear Programming Scheduling Framework for Addressing Sequence-Dependent Setup Issues in Batch Plants. Industrial & Engineering Chemistry Research, 48(13), 6346-6357.

Méndez, C. A., Cerdá, J., Grossmann, I. E., Harjunkoski, I., & Fahl, M. (2006). State-of-the-art review of optimization methods for short-term scheduling of batch processes. Computers & Chemical Engineering, 30(6-7), 913-946.

Terrazas-Moreno, S., Trotter, P. A., & Grossmann, I. E. (2011). Temporal and spatial Lagrangean decompositions in multi-site, multi-period production planning problems with sequence-dependent changeovers. Computers & Chemical Engineering. http://dx.doi.org/10.1016/j.compchemeng.2011.01.004.