(288c) Reformulations and Branching Methods for Mixed-Integer Programming Models in Chemical Production Scheduling

In a broad sense, scheduling can be defined as the problem of allocating a set of limited resources to a set of tasks over time. In chemical production, these tasks involve the transformation of a set of materials into finished goods. The main approach that has been followed in order to model and solve the scheduling problem is the use of mixed-integer programming (MIP) techniques, which often result in challenging formulations that are hard to solve. Thus, improving the computational efficiency of such formulations has been a major research goal in recent years.

An especially challenging feature of time-indexed material-based MIP scheduling models for chemical production scheduling is the existence of many solutions with identical objective function values, but with different variable values. Specifically, schedules that have the same number of batches in each task and unit have the same or similar objective values. Equivalent solutions can be generated by shifting tasks that use idle resources forward or backward. Similarly, many nodes in the branch-and-bound tree will have the same relaxed objective function value even when many of the binary variables are fractional. Branching on individual binary variables often leads to solutions with the same objective, but with different values for individual variables. The algorithm must search through a large number of equivalent solutions before improving the bound.

A natural way to improve computational performance is to incorporate intrinsic problem characteristics into the MIP solution algorithm. In particular, a proper reformulation can induce a particular branching scheme that leads to smaller branch-and-bound trees, improved bounds and faster solution times. To that end, we propose to reformulate the MIP scheduling model to branch on solution characteristics instead of just binary variables. The number of batches in each task and unit is a major solution characteristic because solutions with the same number of batches are expected to have similar or identical objective function values.

In this work we introduce a reformulation strategy for the scheduling problem based on the definition and upper bounding of the number of times (batches) a task runs in a particular unit within a given horizon. Branching on this new variable quickly eliminates solutions with fractional numbers of batches without searching through thousands or even millions of solutions with the same number of batches for each task. In addition, these branching methods lead to fast improvements in the bounds on the objective. We study and compare different branching strategies and variable selection rules and their interaction with different problem characteristics.

We explore various methods to account for the number of batches of a particular task. On one hand, we explicitly define an integer variable that corresponds to the number of batches. On the other hand, we use the equivalence between general-integer and binary-integer programming to implicitly define such a number. For the latter, we also explore branching schemes for special-ordered sets (SOS) and formulations with logarithmic number of binary variables and/or constraints that have been recently proved to improve the computational performance of general disjunctive formulations [1].

This study includes different types of time-indexed models. Primarily we apply the proposed reformulations to both discrete-time and continuous-time models and compare their computational performance. In order to define the number of batches of a given task, the former uses the standard assignment binary variable, whereas for the latter we introduce variants of each method, depending on the whether the binary variable assigns the starting or the end of a task. We also explore a third variant that uses the two types of binary variables simultaneously and show that it introduces significant enhancements over the individual variables.

We test the proposed reformulations using a large collection of instances that include different models, objective functions, networks, and problem features. For the continuous-time framework we use the models developed by Maravelias and Grossmann [2], Sundaramoorthy and Karimi [3] and Gimenez et al. [4], whereas for the discrete-time representation we use the model proposed by Shah et al. [5]. We evaluate the performance of the proposed methods/variants when used in makespan and cost minimization as well as in profit and sales maximization. We present several networks that vary in complexity and size. We include different horizon values and discuss different problem features; in particular, we study variable processing times for the continuous-time models. Our methodologies can readily be extended to other type of models and to include other features that appear in chemical production scheduling.

The proposed reformulations have the advantage of keeping the relative size of the MIP model (variables and constraints), while drastically improving the computational efficiency. For continuous time formulations we obtain an average factor of two for the reduction in computational time, with some instances exhibiting one to two orders of magnitude in speed-up. For discrete-time formulations the results are even more dramatic, with an average improvement of two orders of magnitude in solution time, with some instances achieving reductions of up to four orders of magnitude. The overall percentage of instances solved to optimality is increased and the optimality gap is also decreased for the instances that are not solved within the time limit.

References

[1] Vielma, J.; Nemhauser, G., Modeling disjunctive constraints with a logarithmic number of binary variables and constraints. Math. Program. 2011, 128, 49-72.

[2] Maravelias, C.T.; Grosmann, I., New General Continuous-Time State-Task Network Formulation for Short-Term Scheduling of Multipurpose Batch Plants. Ind. Eng. Chem. Res. 2003, 42, 3056-3074.

[3] Sundaramoorthy, A.; Karimi, I., A simpler better slot-based continuous-time formulation for short-term scheduling in multipurpose batch plants. Chem. Eng. Sci. 2005, 60, 2679-2702.

[4] Gimenez, D.; Henning, G.; Maravelias, C.T., A novel network-based continuous-time representation for process scheduling: Part I. Main concepts and mathematical formulation. Comput. Chem. Eng. 2009, 1511-1528.

[5] Shah, N.; Pantelides, C.; Sargent, R., A general algorithm for short-term scheduling of batch operations –II; computational issues. Comput. Chem. Eng. 1993, 17(2), 229-244.