(728h) Parameter Prediction for Stochastic Job Shop Scheduling Using Probabilistic Machine Learning

Modern industrial job shop processes generate significantly large amount of scheduling and sensor data; the number of sensors in these processes is in the order of hundreds or even thousands (Gungor and Hancke, 2009). By applying machine learning algorithms to the data, the operators have the potential to extract useful insight of their processes. This insight can be used to improve the scheduling algorithms by enhancing their solution quality and/or reducing their computing time.

The most common approach of applying machine learning algorithms to job shop scheduling is to learn dispatching rules from historical data. Li and Olafsson (2005) applied an inductive learning algorithm (C4.5) to train a decision tree model using historical data. Later, Olafsson and Li (2010) improved the performance of the model by training it only with a subset of the historical data, representing the best decisions, which were chosen using a genetic algorithm. Mouelhi-Chibani and Pierreval (2010) proposed a neural network-based approach to select, in real time, the best job for a resource, once it becomes available. Instead of using historical data, they trained their model using simulated scheduling data, generated by simulated annealing. As calling a trained model is nearly instantaneous, this type of approaches eliminate, or significantly reduce, the computational time of the scheduling procedure. This feature is advantageous to dynamic job shop scheduling, in which any computational overhead in the scheduling procedure may cause the decisions to be outdated. For a more extensive review of learning dispatching rules from historical data, the reader may wish to consult the review article by Priore et at. (2014).

An alternative approach of applying machine learning algorithms to job shop scheduling is to predict the key scheduling parameters (e.g., job processing times and power consumptions) for the actual scheduling algorithm. When using typical deterministic algorithms in dynamic scheduling, inaccuracies in scheduling parameters can significantly affect the optimality, or even the feasibility, of the solution. In the literature, several studies have been conducted in order to improve the quality of the scheduling via more accurate input parameter predictions. Berral et al. (2010) predicted power consumption levels, CPU loads and SLA timings of a data center using linear regression and the M5P algorithm. They used these predictions in the scheduling of computing tasks, with an objective of reducing the total power consumption of the data center. Jiang et al. (2016) applied Gaussian process regression in dynamic scheduling of continuous casting of steel to predict slack ratios of jobs. A slack ratio describes the trade-off between low production time and increased risk of a cast-break.

Regardless of the size and quality of the available historical data, the parameter predictions contain uncertainty due to noise and model limitations. By acknowledging this fact, the quality of scheduling solutions in a stochastic environment can be further improved by taking these uncertainties into account in the scheduling algorithm (e.g., by using stochastic programming (Birge and Louveaux, 2011)). Although the information of prediction uncertainty lies in any (extensive) historical data, this aspect of machine learning-aided job shop scheduling is rarely studied in the literature.

Thus, in this work, we, first, use probabilistic machine learning algorithms to predict the scheduling parameters and their uncertainties from an industrial job shop scheduling dataset. For simplicity, we narrow the predicted scheduling parameters to be the job processing times. Second, we use stochastic programming to define a scheduling algorithm, which objective is to minimize the make span of a set of products in a dynamic scheduling environment. Finally, we benchmark our approach to traditional deterministic scheduling methods, for which the job processing times are predicted from the same historical data using linear regression models.

References:

Berral, J. L., Goiri, Í., Nou, R., Julià, F., Guitart, J., Gavaldà, R., & Torres, J. 2010. Towards energy-aware scheduling in data centers using machine learning. Proceedings of the 1st International Conference on energy-Efficient Computing and Networking, ACM, 215-224.

Birge, J. R., & Louveaux, F. 2011. Introduction to stochastic programming. Springer Science & Business Media.

Gungor, V. C., & Hancke, G. P. 2009. Industrial wireless sensor networks: Challenges, design principles, and technical approaches. IEEE Transactions on industrial electronics, 56(10), 4258-4265.

Jiang, S. L., Liu, M., Lin, J. H., & Zhong, H. X. 2016. A prediction-based online soft scheduling algorithm for the real-world steelmaking-continuous casting production. Knowledge-Based Systems, 111, 159-172.

Li, X., & Olafsson, S. 2005. Discovering dispatching rules using data mining. Journal of Scheduling, 8(6), 515-527.

Mouelhi-Chibani, W., & Pierreval, H. 2010. Training a neural network to select dispatching rules in real time. Computers & Industrial Engineering, 58(2), 249-256.

Olafsson, S., & Li, X. 2010. Learning effective new single machine dispatching rules from optimal scheduling data. International Journal of Production Economics, 128(1), 118-126.

Priore, P., Gómez, A., Pino, R., & Rosillo, R. 2014. Dynamic scheduling of manufacturing systems using machine learning: An updated review. AI EDAM, 28(1), 83-97.