(185c) Data-Driven Feasibility and Performance Prediction of Production Scheduling MIP Models

Scheduling is an important decision-making function in manufacturing. In chemical production scheduling, the main goal is to find a schedule that meets production targets and all resource constraints at minimum cost/makespan or maximum profit. Since the incumbent schedule can become suboptimal or even infeasible with disruptions or arrival of new information, there is a need for online scheduling, where prompt re-optimization with updated information can lead to high-quality closed-loop performance (Gupta et al., 2016; Gupta & Maravelias, 2019). However, finding good, and even feasible in some cases, solutions can become challenging when the re-optimization time-step is too short. Moreover, state-of-the-art algorithms for mixed-integer progamming (MIP) models exhibit high, often unexplainable, runtime variation while problem size is held costant (Hutter et al., 2014; Leyton-Brown et al., 2009). Therefore, there is a need for developing methods that would allow us to predict whether a given instance is feasible and what is the runtime to solve a feasible instance.

Accordingly, we employ supervised learning techniques to develop feasibility and performance prediction models for scheduling MIP models. We address the problem of short-term scheduling in single-stage multiple-unit batch plants and consider two objective functions, i.e., makespan minimization and cost minimization. We gather solution quality and runtime data of a large number of instances generated considering a wide range of instance characteristics. One of the important challenges in supervised learning is identifying a set of significant instance features (Smith-Miles & Lopes, 2012). To achieve this, we introduce domain-specific features (related to, for example, problem size, and processing times and costs) for each objective function. Then, we train a logistic regression model that classifies the feasibility of scheduling MIP instances, and a random forest model that predicts the computational requirement for a feasible instance.

The trained classifiers and regressors show good predictive performances: F1 score ~0.90 and AUC ~0.98 for the feasibility classification, and MSE ~0.7 for the runtime prediction. For makespan minimization, load, representing how much units would be utilized in terms of time for processing all given batches, is the most significant feature of the trained classifier; the batch-to-unit ratio is also selected as a significant feature for both the classifier and regressor; and a number of other features have significant but smaller impact. For cost minimization, due date-related features are shown to be significant. The developed models can support the decisions in online scheduling, such as deciding re-optimization time step and horizon length. Finally, we discuss how the obtained insights into what features make a scheduling MIP instance computationally expensive can be used to guide the development of a range of problem-specific solution algorithms.

Reference

Gupta, D., & Maravelias, C. T. (2019). On the design of online production scheduling algorithms. Computers and Chemical Engineering, 129. https://doi.org/10.1016/j.compchemeng.2019.106517

Gupta, D., Maravelias, C. T., & Wassick, J. M. (2016). From rescheduling to online scheduling. Chemical Engineering Research and Design, 116, 83–97. https://doi.org/10.1016/j.cherd.2016.10.035

Hutter, F., Xu, L., Hoos, H. H., & Leyton-Brown, K. (2014). Algorithm runtime prediction: Methods & evaluation. Artificial Intelligence, 206(1), 79–111. https://doi.org/10.1016/j.artint.2013.10.003

Leyton-Brown, K., Nudelman, E., & Shoham, Y. (2009). Empirical hardness models: Methodology and a case study on combinatorial auctions. Journal of the ACM, 56(4). https://doi.org/10.1145/1538902.1538906

Smith-Miles, K., & Lopes, L. (2012). Measuring instance difficulty for combinatorial optimization problems. Computers and Operations Research, 39(5), 875–889. https://doi.org/10.1016/j.cor.2011.07.006