Theory & Solution Methods

Theory

Since solving MIP scheduling models can be computationally expensive, we study the structure of MIP models to derive combinatorial insights for these formulations that would allow us to develop better solution methods. For example, we investigate how chemical manufacturing facilities can be represented as dynamic networks and then converted into time-expanded networks with side constraints (Maravelias, 2012), as well as the tightness of various formulations accounting for sequence-dependent changeovers (Velez et al., 2017).  

Solution Methods

Figure 1. Representation of chemical facility as a dynamic network and then time-expanded network. The assignment constraints are written as the side constraints in the time-expanded network.

Reproduced from (Maravelias, 2012), with permission from Elsevier

References

Maravelias CT. On the combinatorial structure of discrete-time MIP formulations for chemical production scheduling. Computers & Chemical Engineering. 38, 204-212, 2012.

Velez S, Dong Y, Maravelias CT. Changeover Formulations for Discrete-Time Mixed-integer Programming Scheduling Models. European Journal of Operational Research, 260 (3), 949-963, 2017.

Solution Methods

Despite advances in computer hardware and optimization software, the scheduling of chemical processes remains a hard problem. One of the goals of our research is to formulate mixed-integer programming (MIP) models for a wide range of scheduling problems. Since the solution of MIP scheduling models is computationally challenging, we aim to develop advanced solution methods:

  1. Tightening methods: Based on customer demand, process network characteristics and time related data, we calculate the total amount of material and number of batches each task must produce, as well as the number of times subsets of tasks can be executed in a feasible solution. Based on these amounts, we generate tightening constraints (Velez et al., 2013a; Merchan and Maravelias, 2016).
  2. Multi-grid discrete-time models: We formulate models based on separate grids for each task, processing unit, material, and utility. The proposed models have fewer binary variables and constraints than models based on a single and uniform time grid, thereby leading to faster solution times (Velez and Maravelias, 2015).
  3. Parallel branch-and-bound: We develop methods where (1) the full MIP is partitioned into many smaller MIPs by fixing or bounding the number of times each task runs, and (2) each smaller MIP is solved in parallel (Velez and Maravelias, 2013b).
  4. Reformulations: We study extended reformulations where a new integer variable representing the total number of batches for each task is introduced. Branching on this new variable prevents the search from looking at many equivalent solutions and improves the bound on the optimal solution quickly (Velez and Maravelias, 2013c; Merchan et al., 2016).
  5. Discrete Continuous Algorithm: We study a scheduling method that harness the advantages of both discrete and continuous time models, in which we: 1) obtain an approximate (in terms of event timings) solution using a coarse grid discrete time formulation, 2) map this solution to material and unit specific grids, 3) re-optimize the time of events using a continuous model based on the grids generated by step 2. The large discretization step used in discrete time model helps in finding high quality solution quickly and also effectively captures various time sensitive problem characteristics. (Lee and Maravelias, 2018, 2019 and 2020).   

Discrete Continuous algorithm can improve solution times by several orders of magnitude thereby allowing us to solve in minutes’ large-scale problems that were intractable by traditional methods (Figures 2, 3 and 4).

Solution refinement method

Figure 2. An illustration of the three stages of solution refinement method.

Reproduced from (Lee and Maravelias2018), with permission from Elsevier

Performance comparison

Figure 3. The performance of DCA, DM (discrete time model), CM (continuous time model) compared in terms of CPU and objective value for cost minimization.

Reproduced from (Lee and Maravelias2018), with permission from Elsevier

DCA compared to DM and CM

Figure 4. Proportion of instances in which DCA found better/same/worse objective value compared to DM and CM combined. Percentiles represent average difference in objective value; numbers represent average speedup.

Reproduced from (Lee and Maravelias2018), with permission from Elsevier

References

Lee H, Maravelias CT. Combining the Advantages of Discrete- and Continuous-time Scheduling Models. Part 3: General Algorithm. Computers and Chemical Engineering, 139, 106848, 2020.

Lee H, Maravelias CT. Combining the Advantages of Discrete- and Continuous-time Scheduling Models. Part 2: Systematic Methods for Determining Model Parameters. Computers and Chemical Engineering, 128, 557-573, 2019.

Lee H, Maravelias CT. Combining the Advantages of Discrete- and Continuous-Time Scheduling Models: Part 1: Framework and Mathematical Formulations. Computers & Chemical Engineering, 116, 176-190, 2018.

Maravelias CT. On the Combinatorial Structure of Discrete-time MIP Formulations for Chemical Production Scheduling. Computers and Chemical Engineering, 38, 204-212, 2012.

Merchan, A. F., Lee, H. and Maravelias, C. T. Discrete-Time Mixed-Integer Programming Models and Solution Methods for Production Scheduling in Multistage Facilities. Computers and Chemical Engineering, 94, 387-410, 2016.

Merchan, A. F. and Maravelias, C. T.  Preprocessing and tightening methods for time-indexed MIP chemical production scheduling models. Computers and Chemical Engineering, 84, 516-535, 2016.

Velez, S. and Maravelias, C. T.  Theoretical framework for formulating MIP scheduling models with multiple and non-uniform discrete-time grids. Computers and Chemical Engineering, 72, 233-254, 2015.

Velez, S., Sundaramoorthy, A. and Maravelias, C. T. Valid Inequalities Based on Demand Propagation for Chemical Production Scheduling MIP Models. AIChE Journal, 59, 872-887, 2013a.

Velez, S. and Maravelias, C. T. A branch-and-bound algorithm for the solution of chemical production scheduling MIP models using parallel computing. Computers and Chemical Engineering, 55, 28-39, 2013b.

Velez, S. and Maravelias, C. T. Reformulations and Branching Methods for Mixed-Integer Programming Chemical Production Scheduling Models. Industrial and Engineering Chemistry Research, 52, 3832-3841, 2013c.