(440b) Tightening Methods for Continuous Production Scheduling Milps

Chemical processing facilities convert low value raw materials into higher value products by executing different tasks. Chemical production scheduling (CPS) involves assigning those tasks to specific units and establishing the times to execute them to achieve a certain production goal such as maximizing profit or minimizing cost. Since these task-unit assignments and timing decisions determine the overall performance of the plant, scheduling is a vital step in designing and optimizing the operations of manufacturing facilities. Research in the field of CPS has addressed numerous processing characteristics such as batch mixing/splitting, changeovers, utilities, and material transfer restrictions because generalized models can be implemented in a wide range of industrial applications. While problem generality is an important goal, another challenge researchers have also been tackling is computationally enhancing scheduling models.

CPS problems are typically formulated as mixed-integer linear programming (MILP) models, and even trivial scheduling problems are computationally expensive. As the numbers of tasks and units, and the horizon length increase, these problems can quickly become intractable. Efforts to reduce the computational costs have led to the development of reformulations, parallel computing tools, decomposition-based algorithms, and tightening methods. These innovative solution methods have been developed to decrease the solve times of scheduling models, however, most of these efforts have been in the context of batch processes. Continuous production scheduling model developments have received less attention in the literature. Key features of continuous processes relative to batch processes are that they simultaneously produce and consume materials, and these operations possess the flexibility to choose the duration of time tasks are executed. Discovering methods to solve continuous process scheduling problems more efficiently can aid in the optimization of production facilities across various industries by converting intractable problem instances into tractable ones.

In this work, we propose a demand propagation algorithm (DPA), implemented as a preprocessing step, that utilizes demand information, network connectivity, conversion coefficients, and other known system parameters to calculate minimum bounds on production. We start with the demand of all final products, calculate the minimum amount of each material k needed to satisfy that demand (ω_k), and the amount upstream tasks i must process to produce adequate material (μ_i). Due to processing limitations such as production rates and run length restrictions, the production amount may not be attainable. In these cases, μ_i can be tightened even further (ū_i) to fall within the attainable production range. The algorithm propagates backwards until ω_k and ū_i have been calculated for all materials and tasks, respectively. These parameters are then used to bound the binary variable X_i,j,n, which denotes a task i is processed on unit j at time n, or to bound the binary variable Y^S_i,j,n, which denotes a run of task i is started on unit j at time n; runs are a string of consecutive task executions. Two classes of constraints can subsequently be written. One is based on the minimum number of runs or task executions required to satisfy demand, and the other is based on the minimum amount of production required to satisfy demand. When these four sets of tightening constraints and various combinations of them are implemented into the model, they generate bounds on the binary variables and tightens the feasible space of the linear programming (LP) relaxation of the MILP problem. This reduces the branching required to close the optimality gap and consequently yields significant reductions in computational times. All of the models incorporating tightening constraints outperformed the original model, but the tightening constraints bounding the Y^S_i,j,n binary variable clearly performed the best. The ^NY^S formulation, which relates to the number of runs a task must at least execute, solved 36.2% of the instances the fastest, and the ^AY^S formulation, which relates to the amount runs must at least produce, solved the remaining 63.8% of instances faster than all of the other formulations For approximately 80% of the instances we tested, the ^NY^S and ^AY^S formulations improved solution times by an order of magnitude relative to the original formulation. This demonstrates the power of augmenting a model with tightening constraints because a significant amount of time is spent branching on the binary variables. This technique is not restricted to continuous process models or even CPS models; it can be applied to any time-based scheduling models to aid in solving larger scale networks or schedules with long-term horizons.