(530e) An Algorithm Combining the Strengths of Discrete- and Continuous-Time Scheduling Models

While a wide variety of approaches have been proposed for chemical production scheduling, mathematical-programming-based methods are the most popular (Harjunkoski et al., 2014). One of the most important attributes of the modeling approaches adopted in mathematical programming formulations is the representation of time. Mainly two different time approaches have been adopted: discrete and continuous. While the two representations have some distinct advantages, they are also limited in some different ways (Sundaramoorthy and Maravelias, 2011). Specifically, discrete-time models may provide inaccurate solutions if the discretization step is not chosen appropriately. Continuous-time models, on the other hand, are slower than their discrete-time counterparts for large-scale instances and have limited modeling flexibility.

In order to overcome this issue, a framework that allows to harness the advantages of both modeling approaches while overcoming their limitations was recently proposed (Lee and Maravelias, 2017). The framework consists of three stages: (1) obtain an approximate solution using a discrete-time MIP model with a relatively large discretization step, (2) map the solution obtained in the first stage onto multiple unit-specific and material-specific continuous-time grids, and (3) obtain an accurate solution containing the number of batches found in the first stage, by solving a continuous-time LP model. The framework is shown to offer the modeling flexibility and computational efficiency of discrete-time models, while retaining the accuracy of continuous-time models.

The goal of this work is to discuss how to enhance the three-stage algorithm. Specifically, after briefly reviewing the overall framework, we describe how to select some key user-defined parameters, namely, the discretization step and the relaxation of the scheduling horizon, both used in the 1^st stage model. We show that the selection of these two parameters is nontrivial but, nonetheless, very important because the choice of these parameters impacts both the computational performance and solution quality. In particular, a larger discretization that well approximates time-related data leads to significantly smaller models as well as accurate solutions, while appropriately chosen horizon relaxation compensates for solutions that may be cut off due to discretization errors.

Specifically, we provide a way to systematically predict the best parameters, and show that it is applicable to a wide range of scheduling instances. To achieve this, we introduce several error schemes that account for various aspects, including importance of tasks, busyness of units, etc. By evaluating these errors, the best set of parameters can be determined. Through several case studies, we show that seemingly obvious parameter choices may lead to very low quality solutions, while highly counterintuitive choices result in surprisingly good solutions. We show that our method accurately identifies the best set of parameters, which in turn enhances the performance of the framework. We present computational results for a large library of instances.

Finally, we note that the proposed methods are applicable not only to the 3-stage discrete-continuous algorithm but also to any discrete-time scheduling model. In particular, we provide a method for the selection of the “optimal” fixed discretization step, which can in fact be rather different from what would have been chosen using previously proposed heuristic guidelines. Thus, our methods address one of the major limitations of the discrete-time models, namely, the selection of the discretization step when coarse steps are necessary for computational tractability.

Reference

1. 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.
2. 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.
3. Lee, H. and Maravelias, C. T. (2017) Combining the advantages of discrete- and continuous-time scheduling models: Part 1. Framework and mathematical formulations, Computers & Chemical Engineering (in press)