(733b) Combining the Strengths of Continuous and Discrete Time Representations: A General Solution Refinement Method for Discrete-Time MIP Models

Production planning and scheduling of batch processes have received considerable attention in the process systems engineering community in the last 20 years (Harjunkoski et al., 2014). Mainly, two different time representation have been adopted for the mathematical programming models developed: discrete and continuous. Both representations have pros and cons (Floudas and Lin, 2004; Sundaramoorthy and Maravelias, 2011). Specifically, discrete-time formulations are tighter and can readily account for limited shared resources and intermediate shipments/deliveries, but suffer from large model size and inaccuracy of the solution. On the other hand, continuous-time formulations are more accurate and can easily model variable processing time, but exhibit large solution times when the number of periods increases, and cannot be readily extended to linearly account for inventory and resource costs. Although models may benefit from the advantages of the time representation adopted, the short comings that follow are unavoidable.

In this work, we propose a solution method that allows to harness the advantages of both modeling approaches while overcoming their limitations. Specifically, we discuss a “refinement” method for discrete-time MIP models, applicable to all types of production environments. In this method, we solve the problem in two stages: solve for an approximated solution using discrete-time formulation in the first stage, which is refined to a more accurate solution in the second stage using a continuous-time LP formulation. The information transfer from the discrete-time solution (i.e. task assignment and sequencing) to the continuous-time model is achieved through a mapping algorithm we propose. The continuous-time model adopts material-specific grid to ensure material balances and unit-specific grids to ensure unit utilization constraints, while additional utility-specific grids can be adopted, if needed, for shared utilities. The discrete-time model used in the first stage allows us to obtain a good solution faster, as well as consider limited shared resources with time-varying resource availability and costs, as well as intermediate shipments/deliveries. The continuous-time model used in the second stage refines the solution to enhance solution accuracy as well as model variable processing time, while maintaining the feasibility of the solution. We investigate three objective functions, namely minimization of makespan/cost and maximization of production.

Furthermore, since the optimal solution obtained by the discrete-time model in the first stage may not be the optimal for the continuous-time model, we propose a method that allow us to generate a solution pool during the first stage. By collecting non-degenerate solutions, we increase the chance of obtaining the optimal solution during the second stage, which is extremely fast because it involves the solution of LPs.

Finally, we perform a thorough computational study to show that discrete-time models with the proposed solution refinement method are computationally superior when compared to standalone discrete- and continuous-time models. In terms of solution quality, the proposed method is shown to obtain the optimal solution in the majority of instances. The proposed method enable us to solve instances that were considered intractable with continuous-time models, while accounting for process features that only continuous-time models can handle efficiently (e.g., variable processing times).

 

Reference

1.  Floudas, C. A. and Lin, X. X. (2004) Continuous-time versus discrete-time approaches for scheduling of chemical processes: a review. Computers & Chemical Engineering. 28, 2109-2129.
2.  Harjunkoski, I., Maravelias, C. T., Bongers, P., Castro, P. M., Engell, S., Grossmann, I. E., Hooker, J., Mendez, C., Sand, G. and Wassick, J. (2014) Scope for industrial applications of production scheduling models and solution methods. Computers & Chemical Engineering. 62, 161-193.
3.  Sundaramoorthy, A. and Maravelias, C. T. (2011) Computational Study of Network-Based Mixed-Integer Programming Approaches for Chemical Production Scheduling. Industrial & Engineering Chemistry Research. 50, 5023-5040.