(104a) Hybrid Mixed-Integer Programming/Constraint Programming Solution Strategies for Single-Stage Scheduling Problems Using a Discrete-Time Grid

Production scheduling is an extremely active research field within the process systems engineering community. In the past two decades, several works have emerged that combine the advantages of mathematical programming-based methods and constraint programming-based methods for solving single-stage scheduling problems (Jain and Grossman 2001, Bockmayr and Pisaruk, Maravelias and Grossman 2004, Sadykov and Wolsey 2006). However, all of these works utilize a continuous time grid representation. While these continuous time formulations work well due to their solution accuracy and relatively small model sizes, they cannot be used to model time-varying constraints (e.g., utility prices), profiles (e.g., inventory and resource consumption), and other features (e.g., intermediate material deliveries and orders) that can be easily incorporated into formulations that employ a discrete time grid representation. In this work, we present a new solution strategy for solving single-stage scheduling problems that employs a discrete time grid representation and also simultaneously exploits the benefits of mathematical programming and constraint programming.

The major drawback to using a discrete time grid when solving production scheduling problems is that one must often sacrifice solution accuracy in order to obtain a model that is sufficiently small and can be solved in reasonable time. For this reason, the discrete continuous algorithm (DCA) of Merchan et al. (Merchan, Lee, and Maravelias 2016) serves as the foundation for the solution methodology presented herein. The DCA is a two-phase approach. In the first phase, an initial solution is obtained using a discrete time model that employs a coarse time grid. The assignment and sequencing binaries are then fixed in the second phase and a continuous time model is used to recalculate and refine the timing of the batches. While the DCA is able to quickly produce high quality solutions in many cases, it has two major drawbacks: (i) the solution obtained from DCA is not provably optimal and may, in some cases, be infeasible; and (ii) the quality and feasibility of the solution obtained from DCA depends on relaxed batch due times that are user-selected (Lee and Maravelias 2019).

In order to eliminate the abovementioned drawbacks of DCA, we embed the DCA within a branch-and-cut solution strategy. The model passed to our branch-and-cut is the phase one DCA model, i.e., the model in which a coarse time grid is employed and batch due times have been relaxed. The refinement phase of DCA is then carried out whenever a solution is discovered that is integer-feasible for this phase one model. Thus, throughout the course of branch-and-cut we are able to eliminate solutions that are not truly feasible when due times are strictly enforced. Moreover, we can also use appropriately computed bounds in order to guarantee that the optimal schedule is found prior to termination. Prior to the start of our branch-and-cut procedure, we employ a preprocessing phase in order to guarantee that due times are sufficiently relaxed. We note, however, that relaxing due times too much can significantly increase solution time. For this reason, we consider five variants of the preprocessing phase and discuss the strengths and weaknesses of each.

Allow us to now elaborate on the specifics of our proposed branch-and-cut strategy. Throughout execution, each time a solution is found that is integer-feasible on the original coarse time grid, we check the feasibility of the batching assignments and sequencing for each unit with the original due times strictly enforced. If it is determined that for a given unit, processing the assigned batches in the specified order will result in the completion time of some batch exceeding its due time, we do two things. First, we add a cut to the model that eliminates from consideration any other solution for which the given unit is assigned the same batches in the same sequence. After this, we employ a constraint programming model to determine if the there exists any feasible sequencing of the batches assigned to the given unit. If the constraint program is infeasible, we add another cut to the model that eliminates from consideration any other solution for which the given unit is assigned the same batches, regardless of the sequence. On the other hand, if the constraint program is feasible, we record the start times of each batch computed by the constraint program and map them back to the original coarse time grid. Then, after we have carried out all the aforementioned procedures for each unit, if we have determined that the assignments made to every unit are feasible, but that some of the sequencing decisions were not feasible, we use the updated start times computed from the constraint programming solutions to construct a new integer-feasible solution and pass it to the optimizer.

We present the results of several computational tests in which we compare the performance of our proposed branch-and-cut strategy with that of more traditional solution strategies (standard discrete time and continuous time formulations), a pure constraint programming approach, and a state-of-the-art hybrid mixed-integer programming/constraint programming approach that employs a continuous time grid. The results of our tests demonstrate that in most cases our proposed approach results in significant reductions in run time when compared to the standard discrete time and continuous time models as well as the pure constraint programming model. The results further show that our proposed approach is competitive with the state-of-the-art continuous time-based hybrid mixed-integer programming/constraint programming approach.

References:

A. Bockmayr, N. Pisaruk, “Detecting infeasibility and generating cuts for MIP using CP.” Proceedings of CP-AI-OR 2003 (2003), 24-34.

V. Jain, I. E. Grossmann, “Algorithms for hybrid MILP/CP Model for a class of optimization problems.” INFORMS Journal on Computing, 13 (2001), 258-276.

H. Lee and C. T. Maravelias. "Combining the advantages of discrete-and continuous-time scheduling models: Part 2. systematic methods for determining model parameters." Computers & Chemical Engineering 128 (2019), 557-573.

C. T. Maravelias, I. E. Grossmann, “A hybrid MILP/CP decomposition approach for the short term scheduling of multipurpose batch plants.” Computers & Chemical Engineering, 28 (2004) 1921-1949.

A. F. Merchan, H. Lee, and C. T. Maravelias. "Discrete-time mixed-integer programming models and solution methods for production scheduling in multistage facilities." Computers & Chemical Engineering, 94 (2016) 387-410.

R. Sadykov, L. A. Wolsey. "Integer programming and constraint programming in solving a multimachine assignment scheduling problem with deadlines and release dates." INFORMS Journal on Computing, 18.2 (2006) 209-217.