(61l) Reducing Solution Times of Continuous Production Scheduling MILP Models with Record Keeping Variables

In the context of chemical production facilities that convert raw materials into higher value products via processing tasks, scheduling involves assigning those tasks to specific units and establishing the times to execute the tasks in order to achieve a certain production goal. Scheduling is crucial to the design and operation of a manufacturing facility because assigning tasks to units and establishing their timing determine the overall performance of the plant. One key objective that researchers have focused on is reducing solution times of scheduling models, especially because even trivial scheduling problems can be computationally expensive. CPS problems generally possess many binary variables and, as such, are formulated as mixed-integer linear programming (MILP) models. The number of variables increases rapidly as the number of units/tasks in the network or the horizon length increases, which results in the problems becoming intractable. Several innovative solution methods have been developed to address the high computational costs of models; however, most of these efforts have been in the context of batch processes. One relevant example is the introduction of an integer variable that tracks the number of batches of each task that are executed. Branching on this variable quickly eliminates schedules that have the same number of batches, which, in turn, helps eliminate many symmetric solutions¹. In the literature, continuous production scheduling model developments have received far less attention. Notable features of continuous processes are that they simultaneously produce and consume materials, whereas batch processes consume material when a task is executed and produces material at the end of its processing time. Continuous operations possess additional flexibility in terms of the duration of time tasks are executed, which their batch process counterparts do not possess. Discovering new solution methods for continuous process scheduling problems can assist in optimizing manufacturing facilities across various industries by making intractable problem instances solvable.

In this paper, we present strategies for reformulating continuous production scheduling MILP models. We introduce several novel integer variables, which we refer to as record keeping variables (RKVs), that MILP solvers are able to exploit leading to a reduction in total solution times. RKVs are incorporated into the model by setting them equal to some summation of binary variables. In continuous process scheduling models, there are two main binary variables: X_i,j,n, which denotes a task i is processed on unit j at time n and 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. One example of an RKV is N^Y_i,j= ∑_n∈N Y^S_i,j,n ∀ i∈I, j∈J, which essentially keeps a record of the number of runs of task i that are processed on unit j over all time periods n. N^Y_i,j is bounded from zero to the maximum number of times a run can be executed during the scheduling horizon. Other RKVs can be implemented based on the total number of tasks i that are executed, the total number of times a unit j is utilized to process a task, and the total number of time periods n that tasks are executed during. There are 10 RKVs that can be created; five are based on the X_i,j,n binary variable, and five based on the Y^S_i,j,n binary variable.

Results were collected using each RKV individually as well as in combination with other RKVs in order to observe computational performance changes. Overall, models with RKVs based on Y^S_i,j,n perform better than the models using RKVs based on X_i,j,n. We observe that N^Y_i was the most impactful, and the formulation that included N^Y_i alone solved about 40% of the instances the fastest. The superscript “Y” denotes that it is keeping record of the Y^S_i,j,n binary variable since there are also RKVs with the superscript “X” that keep a record of the X_i,j,n binary variable. The subscript “i” denotes that it is written for every task i because it keeps record of the total number of runs of i processed over all units and time periods. There are other RKVs that are written for every unit j, every time point n, or a combination of these indices.

While implementing these RKVs into a model may seem trivial, their implementation leads to dramatic computational improvements. One possible explanation for these results is that by branching on N^Y_i, the solver is able to bound the number of runs of each task, thus efficiently eliminating suboptimal or infeasible schedules and closing the optimality gap more quickly. It is also worth noting that this reformulation technique is not limited to only continuous CPS models; it can also be extended to various other types of MILP models that utilize integer variables.

References:

[1] S. Velez and C. T. Maravelias, 2013, Reformulations and branching methods for mixed-integer programming chemical production scheduling models, Industrial and Engineering Chemistry Research 52, 10, 3832–3841.