(610a) Optimal Scheduling of Multistage Batch Plants with Sequence Dependent Changeovers: a Comparative Study

Scheduling problems can be tackled by a variety of optimization approaches as well as other solution methods (Méndez et al., Comp. Chem. Eng., in press). Mathematical programming (MP) models, usually leading to mixed integer linear programs (MILPs) have received considerable attention in the literature. The focus has ranged essentially from specific to more general types of network configuration and from discrete to continuous representations of time. Constraint programming (CP), originally developed to solve feasibility problems, has also been extended to solve optimization problems. CP and MP approaches have complementary strengths and some researchers have already taken advantage of this, by developing hybrid methods that are considerable more efficient than the standalone approaches. While recent reviews have appeared in the literature that discuss the relative merits of the various MP and CP approaches, they rely on performance data that often involve different problems and distinct hardware and software tools. This paper avoids such limitations by following a more hands-on approach, where as much as six alternative models are tested on the solution of a large set (39) of example problems concerning the short-term scheduling of single/multistage, multiproduct batch plants featuring sequence dependent changeovers. Also analyzed, is the influence of the objective function on model performance. This paper goes beyond a mere comparison between different methods since two of them are new. Both are continuous-time models that are extensions of the one presented by Castro and Grossmann (Ind. Eng. Chem. Res. 2005, 44, 9175) with respect to the handling of sequence dependent changeovers. They are conceptually different on how changeover tasks are handled: either explicitly, which is a more general approach in terms of variety of objective functions that can be handled efficiently, or implicitly in the model constraints, which has the advantage of generating smaller sized models. Another important novel aspect is the combination of processing and changeover tasks into a single set of tasks, which contributes to both reduction in the number of model variables and solution degeneracy, and this is done for one of the new continuous-time models, as well as for a discrete-time model. The other approaches involved in the comparison include a continuous-time model with global precedence sequencing variables (Harjunkoski & Grossmann 2002, Comp. Chem. Eng., 1533), a CP model based on OPL Studio modeling language and a hybrid MILP/CP model (single stage only). The results have shown that the two new formulations are very efficient in single stage problems with the most surprising result coming from the fact that the model that features a number of variables that can be up to one order of magnitude larger than its counterpart, is in fact slightly better. In addition, it is more versatile since besides the objectives of total cost and makespan minimization can also handle the objective of total earliness minimization efficiently. As the number of stages increases, the performance of the developed multiple time grid formulations decrease steadily and feasibility may even be compromised. Overall, the continuous-time formulation with global precedence sequencing variables (SV) can be considered the best approach. Even though other approaches may perform significantly better in some problems, in particular the multiple time grid formulation when minimizing total earliness, the hybrid model when minimizing total cost and the constraint programming model when minimizing makespan, the ability of the SV model to always find very good solutions with modest computational effort (even though optimality may be impossible to prove) gives it an edge over the others.