(195d) A Disjunct Generation and Elimination Algorithm for Discrete-Time Network Scheduling with Variable Processing Times

The effective solution of many large-scale scheduling problems still requires the development of reliable algorithms to increase the adoption of scheduling solutions by the industry [1]. Production scheduling is often performed daily in many chemical and manufacturing plants; hence, solution algorithms should cope with computational limitations. The State Task Network (STN) representation is a graphical depiction of processing network environments in chemical process scheduling, which has been used to develop several scheduling models. Multiple implementations of discrete-time STN-based models are available in both academy and industry, thanks to their versatility and success in addressing large-scale scheduling instances [1]. A key scheduling variable often overlooked in discrete-time STN scheduling is the processing times of tasks. Identifying optimal processing times is key to further improve process economics and productivity, e.g., by reducing the time requirement of costly tasks, or increasing the processing time of those tasks generating finished products that generate a revenue. The consideration of variable processing times is also helpful to avoid infeasible scheduling scenarios, e.g., situations where due dates could not be met due to lengthy tasks that could not be accommodated within a finite scheduling horizon. Nonetheless, previous studies have highlighted the difficulties that arise when trying to solve discrete-time network scheduling problems with variable processing times, due to the combinatorial complexity introduced by these variables [2], [3]. The main difficulty is that dense time grids are needed to accurately model tasks with variable processing times leading to large formulations that cannot be solve to optimality within reasonable computational times using general purpose mathematical programming methods [3].

This study addresses a discrete-time STN scheduling problem, where variable processing times are incorporated using a Generalized Disjunctive Programming (GDP) formulation proposed in a previous work [4]. This study brings novelty by introducing a new solution approach for the discrete-time STN scheduling problem with variable processing times. The proposed solution strategy is inspired by Column Generation (CG) techniques [5], which are often used to solve large-scale Linear Programming (LP) problems and heuristically solve large-scale Mixed Integer Programming (MIP) problems. The key principle behind CG is to sequentially solve reduced-size optimization problems that only consider a subset of the variables that appear in the original optimization problem formulation. At each CG iteration, new columns (i.e., a column is a group of variables) are included in the reduced problem until a stopping criterion is met. CG relies on the solution of a subproblem to decide which variables are added to the reduced problem at each iteration. Although CG techniques have been extensively applied to solve MIP scheduling problems, to the authors’ knowledge, CG techniques have not been studied to address STN scheduling problems. Based on the above, using a CG strategy to iteratively decide which variable processing time options will be considered in the reduced problem is a promising strategy to tackle discrete-time STN scheduling problems with variable task durations.

This work extends the CG idea to tackle GDP problem whose disjunction elements (i.e., disjuncts) follow an ordered structure, e.g., disjunctions are defined over a set that represents points in time, positions in the space, etc. This requirement is satisfied by the GDP formulation under consideration [4], where multiple disjunctions (each containing multiple disjuncts) are used to model variable processing times, e.g., the different processing time options for a reaction task are encoded as disjuncts in a disjunction. Borrowing the iterative generation of columns from CG, this study proposes a disjunct generation (DG) algorithm, i.e., the reduced problem is initially solved with only some of the disjuncts from the original formulation; then, the reduced GDP is repeatedly solved with newly added columns of disjuncts. Furthermore, DG is improved by not only adding new disjuncts at every iteration, but also eliminating previously added disjuncts that are no longer expected to improve the objective function, which keeps the size of the reduced GDP problem tractable. The steps of the proposed DG and elimination (DGE) algorithm are illustrated with the GDP scheduling formulation under consideration. The proposed DGE approach can be used to address problems where multiple tasks have variable processing times; however, we will consider the case where only two tasks A and B have a variable duration for illustrative purposes. The variable processing time of tasks A and B is modeled with disjuncts defined over ordered sets D_A={1,2,...,n_A} and D_B={1,2,...,n_B}, e.g., activating disjuncts 1∈D_A and 1∈D_B means selecting the shortest processing times, while activating disjuncts n_A∈D_A and n_B∈D_B means selecting the longest processing times. Thanks to the ordered nature of the disjuncts, columns can be defined as local neighborhoods, where each local neighborhood contains those disjunct surrounding an incumbent group of disjuncts, e.g., a column surrounding incumbent disjuncts 2∈D_A and 3∈D_B comprises disjuncts {1,2,3}⊆D_A and {2,3,4}⊆D_B. In the first step, DGE is initialized with a single column comprising feasible incumbent disjuncts and their neighborhood, e.g., the shortest processing times 1∈D_A and 1∈D_B are used as incumbent solutions, while their neighborhoods {1,2}⊆D_A and {1,2}⊆D_B are used to initialize the reduced GDP problem. In the second step, the reduced GDP problem is solved to global optimality to identify a new incumbent solution, e.g., assume that the reduced GDP problem found optimal to increase both processing times, leading to incumbent solution 2∈D_A and 2∈D_B. In the third step, a new column of disjuncts surrounding the current incumbent solution is included in the reduced GDP problem, e.g., columns {1,2,3}⊆D_A and {1,2,3}⊆D_B. Furthermore, those columns that are known to deteriorate the objective function can be eliminated, by only keeping the current incumbent solution and its neighborhood in the reduced GDP problem. Then, the algorithm goes back to the second step and a new iteration begins. DGE terminates if the incumbent solution does not change in consecutive iterations. Similarly to any CG algorithm for MIP, there are no guarantees that the solution obtained with DGE is a global optimum; nevertheless, DGE guarantees local optimality within the last neighborhood evaluated. Also, DGE shares a key advantage with CG strategies, namely its ability to heuristically identify good quality solutions quickly for large-scale GDP problems such as the discrete-time scheduling of STNs with variable processing times. Additionally, DGE does not need to solve a subproblem to identify new columns, which represents an improvement with respect to the standard CG technique.

The performance of the proposed DGE strategy was tested using a discrete-time STN involving one heat exchanging task performed in a heat exchanger, two batch reactors that may perform three different reaction tasks, and a purification task performed in a separation unit. The objective function considered is the maximization of profits. Variable processing times were considered for all the task-unit pairs in the problem, resulting in 8 disjunctions, each containing 8 disjuncts, i.e., 64 disjuncts in total. Furthermore, the scheduling horizon was discretized using 20 discretization points, resulting in a fine scheduling time grid. DGE was compared to the direct solution of the GDP problem using a Big-M reformulation and MIP solver CPLEX, with a time limit of 86400 seconds. In this case, DGE was able to converge to a solution with a profit of 458.59$ after 54 seconds, while CPLEX found the same objective function value after 10843 seconds, resulting in a computational time improvement of 3 orders of magnitude. Furthermore, CPLEX was only able to find a slightly better objective function of 459.57$, which could not be improved further after reaching the time limit. The DGE solution found is thus only 0.21% worse relative to the CPLEX solution. Other case studies showing similar results were also tested, but their results are not summarized here for brevity. Note that GDP formulations with ordered disjuncts not only appear in process scheduling, but also in many other chemical engineering applications, e.g., superstructure synthesis and design problems, planning problems, etc. Therefore, this study opens a new research direction aiming to efficiently solve the large-scale GDP problems through DGE or other CG-based strategies.

References

[1] S. Velez and C. T. Maravelias, “Advances in mixed-integer programming methods for chemical production scheduling,” Annu Rev Chem Biomol Eng, vol. 5, pp. 97–121, 2014.

[2] I. Harjunkoski et al., “Scope for industrial applications of production scheduling models and solution methods,” Computers & Chemical Engineering, vol. 62, pp. 161–193, Mar. 2014.

[3] A. Sundaramoorthy and C. T. Maravelias, “Computational Study of Network-Based Mixed-Integer Programming Approaches for Chemical Production Scheduling,” Ind. Eng. Chem. Res., vol. 50, no. 9, pp. 5023–5040, May 2011.

[4] D. A. Liñán and L. A. Ricardez-Sandoval, “Discrete-Time Network Scheduling and Dynamic Optimization of Batch Processes with Variable Processing Times through Discrete-Steepest Descent Optimization,” Ind. Eng. Chem. Res., vol. 63, no. 10, pp. 4478–4495, Mar. 2024, doi: 10.1021/acs.iecr.3c03455.

[5] J. Desrosiers and M. E. Lübbecke, “A Primer in Column Generation,” in Column Generation, G. Desaulniers, J. Desrosiers, and M. M. Solomon, Eds., Boston, MA: Springer US, 2005, pp. 1–32. doi: 10.1007/0-387-25486-2_1.