(12e) On Multiple Heterogeneous Time Grids for Continuous Production Scheduling Milps

Multiproduct facilities convert low value raw materials into higher value final products through the execution of tasks, and chemical production scheduling (CPS) involves assigning those tasks to specific units while determining the best times to execute them in order to achieve specific production goals. Scheduling is crucial in the optimization of manufacturing operations because the overall performance of a facility depends on timing decisions and task-unit assignments. Research in the field of CPS has aimed to improve the computational efficiency of mixed-integer linear programming (MILP) models because an increase in the number of constraints and variables rapidly increases computational complexity, especially in discrete-time models. Several innovative solution methods have been proposed to reduce the solution times of discrete-time scheduling models such as decomposition-based algorithms, parallel computing tools, reformulations, and tightening methods, however, most of these efforts have been in the context of batch processes¹. Continuous processes have received less attention in the literature. Modeling continuous processes, particularly with startups, shutdowns, and direct transitions, has been a challenge because the approaches that involve integrated scheduling–dynamic optimization usually lead to accurate models but can only be applied to small systems with few tasks/units due to computational limitations. To address these challenges, we propose implementing multiple discrete-time grids where tasks, units, and materials each possess their own time grid, and spacing between time points is nonuniform (i.e., heterogeneous).

Since multi-grid models have been shown to be computationally more effective than single, uniform grids in batch production scheduling models ^2–5, we extend this concept to continuous production scheduling MILP models by employing heterogeneous time grids for each material, task, and unit. Integrating multiple discrete‐time grids within a model is readily implementable because the locations of all time points are predetermined, a feature not available in continuous‐time models. First, we describe how to reformulate the original constraints and define the required subsets, enabling users to select a unique heterogeneous time grid for specific materials, tasks, units, or any combination thereof. We also outline the parameter adjustments needed to accurately capture the original process characteristics. Given that transient operations are an inherent aspect of continuous processes, we demonstrate how subtasks (building blocks used to model continuous tasks) are handled across varying levels of time grid granularity. Because different sections of a process may operate on different time scales, one may wish to impose heterogeneous time grids based on the processing stage of a task/unit. In CPS applications, upstream units – often larger and operating in a batch-like fashion with higher processing rates and reduced flexibility – contrast with downstream units that typically require finer control due to precision demands. For example, in pharmaceutical processes upstream fermenters and bioreactors produce large volumes of biological material, while downstream purification systems handle smaller, more precisely controlled quantities. Consequently, applying a fine time grid to the upstream operations is less critical, prompting users to adopt heterogeneous grids that better reflect the natural time scales of each process stage. The same principle is applied to materials, considering how upstream materials are oftentimes produced/consumed in larger quantities relative to downstream materials. Thus, we describe the constraints needed to employ material-specific time grids. Furthermore, the schedule for immediate operations holds greater significance than the uncertain schedule further into the future due to the higher likelihood of needing to re-optimize the model in the future, so the time grid near the end of the horizon could reasonably be coarser than the time grid at the beginning. We discuss how this time grid heterogeneity can easily be incorporated. Since the number of binary variables and constraints is proportional to the number of time points, these modifications can reduce model size and significantly decrease its computational resource requirements.

We perform a computational study to illustrate the significant computational enhancements that can be achieved with this reformulation technique, obtaining results for material-specific, task-specific, and unit-specific grids. Combinations of the aforementioned grids were also employed as well as heterogeneous grids that have coarser discretizations near the end of the horizon. Our results indicate that applying multiple, heterogeneous grids can yield solution times that are an average of over four times faster than the original model, substantially decreasing the computational resources required to solve instances. Additionally, after the time points in the grids are specified, the resulting model consists of the same types of constraints as the original model with uniformly spaced time grids. Thus, reformulation techniques, such as record keeping variables (RKVs), developed for production scheduling models can still easily be applied. Preliminary results confirm that RKVs can be readily integrated in conjunction with multiple, heterogeneous time grids. Notably, this technique is not restricted to continuous production scheduling models or even CPS models; it can be applied to other classes of discrete-time-based scheduling models.

References

1. Harjunkoski I, Maravelias CT, Bongers P, et al. Scope for industrial applications of production scheduling models and solution methods. Comput Chem Eng. 2014;62:161-193. doi:10.1016/J.COMPCHEMENG.2013.12.001
2. Velez S, Maravelias CT. Multiple and nonuniform time grids in discrete-time MIP models for chemical production scheduling. Comput Chem Eng. 2013;53:70-85. doi:10.1016/j.compchemeng.2013.01.014
3. Velez S, Maravelias CT. Theoretical framework for formulating MIP scheduling models with multiple and non-uniform discrete-time grids. Comput Chem Eng. 2015;72:233-254. doi:10.1016/j.compchemeng.2014.03.003
4. Lagzi S, Lee DY, Fukasawa R, Ricardez-Sandoval L. A Computational Study of Continuous and Discrete Time Formulations for a Class of Short-Term Scheduling Problems for Multipurpose Plants. Ind Eng Chem Res. 2017;56(31):8940-8953. doi:10.1021/acs.iecr.7b01718
5. Stevenson Z, Fukasawa R, Ricardez-Sandoval L. A dynamic approach to selecting time points for short-term scheduling with application to multipurpose facilities. Ind Eng Chem Res. 2020;59(19):9180-9197. doi:10.1021/ACS.IECR.0C00472