(62e) Discrete-Continuous Scheduling Algorithm: A Branch and Cut Approach

Production scheduling is one of the most active research fields within the process systems engineering community over the last three decades, and several exact and approximate solution approaches are proposed over the years (Méndez et al. 2006; Harjunkoski et al. 2014). The time representation techniques used in these approaches, especially in the mathematical programming-based methods, are extremely crucial as the tractability of the model and accuracy of the solution heavily depend on them (Floudas and Lin 2004, Sundaramoorthy and Maravelias 2011). Both continuous and discrete time grid representations have distinct advantages and disadvantages. In the case of discrete time representation, the number and location of the time points are known a priori, which facilitates straightforward modeling of time-varying constraints (e.g., utility prices), profiles (e.g., inventory and resource consumption), and other features (e.g., intermediate material deliveries and orders). However, there is a trade-off between accuracy and tractability in the case of discrete time models. In contrast, continuous time formulations are known for their solution accuracy and smaller model sizes; however, they require an iterative procedure to calculate the required number of time points and they become computationally expensive. Recently, Merchan et al. (Merchan, Lee, and Maravelias 2016), for sequential environments, and Lee and Maravelias (Lee and Maravelias 2018), for the network environments, proposed a framework that combines the advantages of both discrete and continuous time representations (discrete continuous algorithm or DCA). The proposed framework contains mainly two stages. In the first stage, a discrete time model is solved using a coarse time grid to obtain a solution. In the second stage, with the assignment and sequencing binaries fixed, the timing of the batches are recalculated using a continuous time formulation (solution refinement step). It has been shown that DCA provides highly accurate solutions in a computationally efficient manner.

However, the main disadvantage of DCA is that the algorithm cannot guarantee the optimality of the solution. As the batch unit assignments and sequencing decisions are based on a model with coarsely discretized time grids, the first stage solution can become suboptimal when accurate process timings are considered in the second stage. Furthermore, the performance of DCA heavily depends on a user-defined due date relaxation employed in the first stage (Lee and Maravelias 2019). While Lee and Maravelias provided some methods for determining good relaxation, their method cannot guarantee that the optimal assignment will not be cut off.

To solve the issue of optimality, in this work, we propose a systematic methodology for the calculation of appropriate due date relaxations and a novel branch and cut approach for the implementation of the discrete-continuous algorithm. The due dates used in the discrete time model should be relaxed sufficiently so that the optimal batch unit assignments that will result in minimum cost or maximum profit do not get excluded. On the contrary, highly relaxed due dates would produce several infeasible solutions (infeasible when actual timings are considered), removal of which through cut generation increases the computational burden. We propose a mixed integer programming-based model, used in a pre-processing step, to calculate sufficient relaxations in the due dates for each task in each unit that is required for a given discretization time step. The due date relaxation calculation step is crucial, as both the optimality of the solution and the computational efficiency of the proposed algorithm depends on it.

The discrete time mixed integer programming (MIP) model used in the proposed branch and cut approach uses the relaxed due dates calculated using the abovementioned relaxation calculation model. Whenever integer batch unit assignments are found at some node of the search tree, we calculate the sequence among those batches on the assigned unit. The batch assignments and sequence are then fed to a continuous time-based linear programming (LP) sub-model, solved at each node with integer assignments using the accurate release, due, and processing timings. The submodel calculates the actual batch end dates (solution refinement step) and thus an accurate objective function. It needs to be noted that the LP sub-model is solved for each unit with integer batch assignments and basically checks whether the assigned batches can be scheduled on that unit (in the same sequence as found by the discrete MIP model) when the actual timings are considered. If any of the LP sub-model becomes infeasible at a give node, a cut is added to exclude the corresponding solution. To enhance the computational efficiency of the method, we propose a novel cut that excludes an infeasible batch sequence; however, it does not adversely affect the batch assignment decisions. The proposed branch and cut approach is tested upon multiple instances of single stage scheduling problems. It is shown to speedup solution times by at least one order of magnitude compared to discrete-time models and two orders of magnitude compared with continuous time models.

References:

Floudas, Christodoulos a., and Xiaoxia Lin. 2004. “Continuous-Time versus Discrete-Time Approaches for Scheduling of Chemical Processes: A Review.” Computers and Chemical Engineering 28: 2109–29. https://doi.org/10.1016/j.compchemeng.2004.05.002.

Harjunkoski, Iiro, Christos T Maravelias, Peter Bongers, Pedro M Castro, Sebastian Engell, Ignacio E Grossmann, John Hooker, Carlos Méndez, Guido Sand, and John Wassick. 2014. “Scope for Industrial Applications of Production Scheduling Models and Solution Methods.” Computers & Chemical Engineering 62: 161–93. https://doi.org/https://doi.org/10.1016/j.compchemeng.2013.12.001.

Lee, Hojae, and Christos T Maravelias. 2018. “Combining the Advantages of Discrete- and Continuous-Time Scheduling Models: Part 1. Framework and Mathematical Formulations.” Computers & Chemical Engineering 116: 176–90. https://doi.org/https://doi.org/10.1016/j.compchemeng.2017.12.003.

Lee, Hojae, and Christos T Maravelias. 2019. “Combining the Advantages of Discrete- and Continuous-Time Scheduling Models: Part 2. Systematic Methods for Determining Model Parameters.” Computers & Chemical Engineering 128: 557–73. https://doi.org/https://doi.org/10.1016/j.compchemeng.2018.10.020.

Méndez, Carlos A, Jaime Cerdá, Ignacio E Grossmann, Iiro Harjunkoski, and Marco Fahl. 2006. “State-of-the-Art Review of Optimization Methods for Short-Term Scheduling of Batch Processes.” Computers & Chemical Engineering 30 (6): 913–46. https://doi.org/https://doi.org/10.1016/j.compchemeng.2006.02.008.

Merchan, Andres F, Hojae Lee, and Christos T Maravelias. 2016. “Discrete-Time Mixed-Integer Programming Models and Solution Methods for Production Scheduling in Multistage Facilities.” Computers & Chemical Engineering 94: 387–410. https://doi.org/https://doi.org/10.1016/j.compchemeng.2016.04.034.

Sundaramoorthy, Arul, and Christos T Maravelias. 2011. “Computational Study of Network-Based Mixed-Integer Programming Approaches for Chemical Production Scheduling.” Industrial & Engineering Chemistry Research 50 (9): 5023–40. https://doi.org/10.1021/ie101419z.