Decision Tree Based Scheduling for Flexible Job Shops with Multiple Process Plans

Authors: H.-H. Doh, J.-M. Yu, Y.-J. Kwon, J.-H. Shin, H.-W. Kim, S.-H. Nam, D.-H. Lee

Abstract:

This paper suggests a decision tree based approach for flexible job shop scheduling with multiple process plans, i.e. each job can be processed through alternative operations, each of which can be processed on alternative machines. The main decision variables are: (a) selecting operation/machine pair; and (b) sequencing the jobs assigned to each machine. As an extension of the priority scheduling approach that selects the best priority rule combination after many simulation runs, this study suggests a decision tree based approach in which a decision tree is used to select a priority rule combination adequate for a specific system state and hence the burdens required for developing simulation models and carrying out simulation runs can be eliminated. The decision tree based scheduling approach consists of construction and scheduling modules. In the construction module, a decision tree is constructed using a four-stage algorithm, and in the scheduling module, a priority rule combination is selected using the decision tree. To show the performance of the decision tree based approach suggested in this study, a case study was done on a flexible job shop with reconfigurable manufacturing cells and a conventional job shop, and the results are reported by comparing it with individual priority rule combinations for the objectives of minimizing total flow time and total tardiness.

Keywords: Flexible job shop scheduling, Decision tree, Priority rules, Case study.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1091604

References:

[1] C. Ozguven, L. Ozbakir, and Y. Yavuz, "Mathematical models for job-shop scheduling problems with routing and process plan flexibility,” Applied Mathematical Modelling, vol. 34, pp. 1539–1548, 2010.
[2] H.-H. Doh, J.-M. Yu, J.-S. Kim, D.-H. Lee, and S.-H. Nam, "A priority scheduling approach for flexible job shops with multiple process plans,” International Journal of Production Research. vol. 51, pp. 3748-3764, 2013.
[3] H. Deng, G. Runger, and E. Tuv, "Bias of importance measures for multi-valued attributes and solutions," Proceedings of the 21st International Conference on Artificial Neural Networks, pp.293-300.
[4] N. Shinichi and Y. Taketoshi, "Dynamic scheduling system utilizing matching learning as a knowledge acquisition tool,” International Journal of Production Research, vol. 30, pp. 411-431, 1992.
[5] M. J. Shaw, S. Park and N. Raman, "Intelligent scheduling with machine learning capabilities: the induction of scheduling knowledge,” IIE Transactions, vol. 24, pp. 156-168, 1992.
[6] S. Piramuthu, N. Raman and M. J. Shaw, "Learning-based scheduling in a flexible manufacturing flow line,” IEEE Transactions on Engineering Management, vol. 41, pp. 172-182, 1994.
[7] S.-C. Park, N. Raman, and M. J. Shaw, "Adaptive scheduling in dynamic flexible manufacturing systems: a dynamic rule selection approach," IEEE Transactions on Robotics and Automation, vol. 13, pp.486-502, 1997.
[8] C.-Y. Lee, S. Piramuthu, and Y.-K. Tsai, "Job shop scheduling with a genetic algorithm and machine learning," International Journal of Production Research, vol. 35, pp.1171–1191, 1997.
[9] Y. Arzi and L. Iaroslavitz, "Operating an FMC by a decision-tree-based adaptive production control system," International Journal of Production Research, vol. 38, pp.675-697, 2000.
[10] C. T. Su and Y. R. Shiue, "Intelligent scheduling controller for shop floor control systems: a hybrid genetic algorithm/decision tree learning approach," International Journal of Production Research, vol. 41, pp.2619-2641, 2003.
[11] C. Kwak and Y. Yie, "Data mining approach to production control in the computer integrated testing cell," IEEE Transactions on Robotics and Automation, vol. 20, pp.107-116, 2004.
[12] P. Priore, D. De La Fuente, J. Puente, and J. Parreno, "A comparison of machine learning algorithms for dynamic scheduling of flexible manufacturing systems, Engineering Applications of Artificial Intelligence, vol. 19, pp.247-255, 2006.
[13] Y.R. Shiue, R. S. Guh, and T. Y. Tseng, "GA-based learning bias selection mechanism for real-time scheduling systems," Expert Systems with Applications, vol. 36, pp.11451-11460, 2009.
[14] H.-S. Choi, J.-S. Kim, and D.-H. Lee, "Real-time scheduling for reentrant hybrid flow shops: a decision tree based mechanism and its application to a TFT-LCD line,” Expert Systems with Applications, Vol. 38, pp. 3514-3521, 2011.
[15] Y.-J. Kwon, J.-M. Yu, H.-H. Doh, S.-H. Nam and D.-H. Lee, "Decision tree based real-time scheduling: a decision tree construction method,” Proceedings of the International Symposium on Green Manufacturing and Applications, Honolulu, USA, 2013.
[16] Quinlan, J. R. "Introduction of decision trees,” Machine Learning, Vol. 1, pp. 80-106, 1986.
[17] Y. Koren, U. Heisel, F. Jovane, T. Moriwaki, G. Pritschow, G. Ulsoy, and H. Brussel, "Reconfigurable manufacturing systems," Annals of the CIRP, vol.48, pp.527–540, 1999.
[18] H.-W. Kim, J.-M. Yu, J.-S. Kim, H.-H. Doh, D.-H. Lee, and S.-H Nam, "Loading algorithms for flexible manufacturing systems with partially grouped unrelated machines and additional tooling constraints," International Journal of Advanced Manufacturing Technology, vol. 58, pp. 683-691, 2012.
[19] H.-H. Doh, J.-M. Yu, J.-S. Kim, D.-H. Lee, and S.-H. Nam, "A Priority Scheduling Approach for Flexible Job Shops with Multiple Process Plans," International Journal of Production Research, vol. 51, pp. 3748-3764, 2013.
[20] J.-M. Yu, H.-H. Doh, J.-S. Kim, Y.-J. Kwon, D.-H. Lee, and S.-H. Nam, "Input Sequencing and Scheduling for a Reconfigurable Manufacturing System with a Limited Number of Fixtures," International Journal of Advanced Manufacturing Technology, vol. 67, pp. 157-169, 2013.