(475d) In-Depth Study and Comparison of S-Graph Framework and Precedence Based MILP Formulations for Batch Process Scheduling

Several review papers have been published on batch process scheduling (see, e.g., Floudas and Lin, 2004; Mendez et. al., 2006; Hegyhati and Friedler, 2010), nevertheless, an in-depth study of specific approaches that can enhance each other’s performance is yet to be done. It is especially interesting for the approaches based on task precedences: they are the so-called precedence based MILP formulations and the S-graph framework.

In the S-graph framework, batch process scheduling problems are modeled by a special class of directed graphs, where precedence of tasks is represented by an arc (Sanmarti et. al., 1998). While it is natural for the MILP formulation based techniques that they need the complete mathematical programming formulation prior to solving the problem, it is not the case for the S-graph framework; the input is practically the graph representation of the recipe. The combinatorial algorithms extend this graph by so-called schedule-arcs as far as the allocation and sequencing decisions are made (Sanmarti et. al., 2002). In the precedence based MILP models, binary variables are assigned to each pair of tasks that can be performed in the same unit (Mendez et. al., 2001). The absence or existence of a schedule-arc on an S-graph is modeled by a binary variable in the MILP model.

The precedence based MILP approaches and the S-graph framework have some common features based on the one-to-one relation between a schedule-arc and a variable of sequencing. For example, limited wait storage policies, sequence dependent setup times can be addressed in a similar and straightforward way in both models (Hegyhati et. al., 2011; Kopanos et. al., 2009). The origin of the two mathematical representations are the same, nevertheless, the solution procedures are fundamentally different. While it is easier to avoid the so-called cross transfer in case of the S-graph framework (Hegyhati et. al., 2009; Ferrer-Nadal et. al., 2008), finite intermediate storage policy can be addressed more easily in the precedence based models (Mendez and Cerda, 2003; Romero et. al., 2004). Despite the important difference between the applied optimization procedures, recent study has shown, that the two approaches have similar demands in terms of CPU time (Hegyhati and Friedler, 2011).

Present work summarizes the similarities and differences of these methods, and investigates, how they can contribute to each other’s performance.

References

Ferrer-Nadal, S.; Capón-García, E.; Méndez, C. A. and Puigjaner, L., Material transfer operations in batch scheduling. A critical modeling issue, Industrial & Engineering Chemistry Research, 2008, 47, 7721-7732

Floudas, C. A. and Lin, X., Continuous-time versus discrete-time approaches for scheduling of chemical processes: a review, Computers & Chemical Engineering, 2004, 28, 2109-2129

Hegyhati, M. and Friedler, F., Overview of Industrial Batch Process Scheduling, Chemical Engineering Transactions, 2010, 21, 895-900

Hegyhati, M. and Friedler, F., Combinatorial Algorithms of the S-graph Framework for Batch Scheduling, Industrial & Engineering Chemistry Research, 2011, 50 (9), 5169-5174

Hegyhati, M.; Holczinger, T.; Szoldatics, A. and Friedler, F., Combinatorial Approach to Address Batch Scheduling Problems with Limited Storage Time, Chemical Engineering Transactions, 2011, in press.

Hegyhati, M.; Majozi, T.; Holczinger, T. and Friedler, F., Practical infeasibility of cross-transfer in batch plants with complex recipes: S-graph vs MILP methods, Chemical Engineering Science, 2009, 64, 605 – 610

Kopanos, G. M.; Lainez, J. M. and Puigjaner, L., An Efficient Mixed-Integer Linear Programming Scheduling Framework for Addressing Sequence-Dependent Setup Issues in Batch Plants, Industrial & Engineering Chemistry Research, 2009, 48, 6346-6357

Mendez, C. A. and Cerda, J., An MILP Continuous-Time Framework for Short-Term Scheduling of Multipurpose Batch Processes Under Different Operation Strategies, Optimization and Engineering, 2003, 4, 7-22

Mendez, C. A.; Cerda, J.; Grossmann, I. E.; Harjunkoski, I. and Fahl, M., State-of-the-art review of optimization methods for short-term scheduling of batch processes, Computers & Chemical Engineering, 2006, 30, 913-946

Mendez, C. A.; Henning, G. P. and Cerda, J., An MILP continuous-time approach to short-term scheduling of resource-constrained multistage flowshop batch facilities, Computers & Chemical Engineering, 2001, 25, 701-711

Romero, J.; Puigjaner, L.; Holczinger, T. and Friedler, F., Scheduling Intermediate Storage Multipurpose Batch Plants Using the S-Graph, AIChE Journal, 2004, 50(2), 403-417

Sanmarti, E.; Friedler, F. and Puigjaner, L., Combinatorial Technique for Short Term Scheduling of Multipurpose Batch Plants Based on Schedule-Graph Representation, Computer Aided Chemical Engineering, 1998, 22, S847-850

Sanmarti, E.; Holczinger, T.; Puigjaner, L. and Friedler, F., Combinatorial framework for effective scheduling of multipurpose batch plants, AIChE Journal, 2002, 48(11), 2557-2570