(648a) Decomposition of Integrated Scheduling and Dynamic Optimization Problems Using Community Detection and Centrality Analysis

Scheduling and control form the basis for the optimal economic process operation. Although the goal of these tasks is different, their integration can have an important impact on the economics of the process [1]. The direct integration of these tasks involves the incorporation of the equations that describe the dynamic behavior of the system into the scheduling calculations [2]. The resulting integrated problem is a mixed integer dynamic optimization problem which upon discretization is transformed into a mixed integer nonlinear program which is challenging to solve. Decomposition based solution algorithms can in principle be used to solve such integrated problems [3-6] in reduced computational time, however, the decomposition of the optimization problem itself is a necessary first step and one that affects strongly the solution algorithm. A systematic framework for determining such a decomposition is currently lacking.

In this work, a method is proposed to decompose the integrated cyclic scheduling and dynamic optimization problems for a broad class of production systems using community detection and centrality analysis. This approach enables the systematic identification of a hybrid hierarchical/community structure. Specifically, we employ the DeCODe software tool [7] to create the constraint graph of the integrated optimization problem and apply community detection. The detection results indicate a block structure in the graph, where one block is the scheduling problem and the other blocks are the dynamic optimization subproblems for each slot. Each dynamic optimization subproblem is connected only with the scheduling subproblem through continuous variables. The block structure is examined further by applying centrality analysis, i.e. quantification of the importance of a node in the graph. From this analysis, the community that corresponds tο the scheduling subproblem is shown to have the highest average centrality while the communities of the dynamic optimization subproblems have equal average centralities. These results indicate that the constraint graph and hence the integrated optimization problem has a two-level hierarchical structure. This decomposition is used as the basis for the application of Generalized Benders decomposition and the problem is solved in reduced computational time compared to the monolithic solution. It is also shown that the same structure is present for different discretization schemes of the process dynamic model.

References:

[1]. Daoutidis, P., Lee, J. H., Harjunkoski, I., Skogestad, S., Baldea, M., & Georgakis, C. (2018). Integrating operations and control: A perspective and roadmap for future research. Computers & Chemical Engineering, 115, 179-184.

[2]. Flores-Tlacuahuac, A., & Grossmann, I. E. (2006). Simultaneous cyclic scheduling and control of a multiproduct CSTR. Industrial & Engineering Chemistry Research, 45(20), 6698-6712.

[3]. Terrazas‐Moreno, S., Flores‐Tlacuahuac, A., & Grossmann, I. E. (2008). Lagrangean heuristic for the scheduling and control of polymerization reactors. AIChE Journal, 54(1), 163-182.

[4]. Chu, Y., & You, F. (2013). Integration of production scheduling and dynamic optimization for multi-product CSTRs: Generalized Benders decomposition coupled with global mixed-integer fractional programming. Computers & Chemical Engineering, 58, 315-333.

[5]. Nie, Y., Biegler, L. T., Villa, C. M., & Wassick, J. M. (2015). Discrete time formulation for the integration of scheduling and dynamic optimization. Industrial & Engineering Chemistry Research, 54(16), 4303-4315.

[6]. Chu, Y., & You, F. (2012). Integration of scheduling and control with online closed-loop implementation: Fast computational strategy and large-scale global optimization algorithm. Computers & Chemical Engineering, 47, 248-268.

[7]. Allman, A., Tang, W., & Daoutidis, P. (2019). DeCODe: a community-based algorithm for generating high-quality decompositions of optimization problems. Optimization and Engineering, 20(4), 1067-1084.