Real-Time Scheduling Scheme based on Reinforcement Learning Considering Minimizing Setup Cost

Woosik Yoo, Sungjae Kim, Kwanho Kim

Abstract


This study starts with the idea that the process of creating a Gantt Chart for schedule planning is similar to Tetris game with only a straight line. In Tetris games, the X axis is M machines and the Y axis is time. It is assumed that all types of orders can be worked without separation in all machines, but if the types of orders are different, setup cost will be incurred without delay. In this study, the game described above was named Gantris and the game environment was implemented. The AI-scheduling table through in-depth reinforcement learning compares the real-time scheduling table with the human-made game schedule. In the comparative study, the learning environment was studied in single order list learning environment and random order list learning environment. The two systems to be compared in this study are four machines (Machine)-two types of system (4M2T) and ten machines-six types of system (10M6T). As a performance indicator of the generated schedule, a weighted sum of setup cost, makespan and idle time in processing 100 orders were scheduled. As a result of the comparative study, in 4M2T system, regardless of the learning environment, the learned system generated schedule plan with better performance index than the experimenter. In the case of 10M6T system, the AI system generated a schedule of better performance indicators than the experimenter in a single learning environment, but showed a bad performance index than the experimenter in random learning environment. However, in comparing the number of job changes, the learning system showed better results than those of the 4M2T and 10M6T, showing excellent scheduling performance.


Full Text:

PDF

References


Beck, J. E. and Woolf, B. P., High-Level Student Modeling with Machine Learning, In: Gauthier, G., Frasson, C., VanLehn, K.(eds) Intelligent Tutoring Systems, ITS 2000, Lecture Notes in Computer Science, Vol, 1839, 2000, Springer, Berlin, Heidelberg.

Jeong et al., “An Neural Network Approach to Job-shop Scheduling based on Reinforcement Learning,” Proceedings of the Korean Society of Computer Information Conference, pp. 47-48, 2018.

Kaplan, R., Sauer, C., and Sosa, A., “Beating atari with natural language guided reinforcement learning,” arXiv preprint arXiv:1704.05539, 2017.

Kim, A., “Ensemble-based Quality Classification and Deep Reinforcement Learning-based Production Scheduling: Ensemble-based Quality Classification and Deep Reinforcement Learning-based Production Scheduling,” KyungHee University, Ph.D. Thesis, 2018.

Kim, J., “Packet scheduling algorithm using deep Q-Network in wireless network”, Yonsei University, M.S Thesis, 2018.

Lee, S.-H., “Reinforcement Learning based AGV Scheduling,” The Korean Society of Computer And Information, Proceedings of the Korean Society of Computer Information Conference, pp. 23-24, 2018.

Lin, C.-C., Deng, D.-J., Chih, Y.-L., and Chiu, H.-T., “Smart Manufacturing Scheduling with Edge Computing Using Multi- Class Deep q Network”, IEEE Transactions on Industrial Informatics, 2019.

Mnih et al., “Human-level control through deep reinforcement learning”, Nature, Vol. 518, No. 7540, pp. 529-533, 2015.

Mnih et al., “Playing Atari with Deep Reinforcement Learning”, Proceedings of the NIPS Deep Learning Workshop, 2013.

Park, I.-B., Huh, J., Kim, J., and Park, J., “A reinforcement learning approach to robust scheduling of semiconductor manufacturing facilities,” IEEE Transactions on Automation Science and Engineering, 2019.

Schrum, J., Evolving Indirectly Encoded Convolutional Neural Networks to Play Tetris With Low-Level Features, Proceedings of the Genetic and Evolutionary Computation Conference, (GECCO), 2018.

Shahrabi, J., Adibi, M. A., and Mahootchi, M., “A reinforcement learning approach to parameter estimation in dynamicjob shop scheduling,” Computers & Industrial Engineering, Vol. 110, pp. 75-82, 2017.

Silver et al., “Mastering the game of Go with deep neural networks and tree search,” Nature, Vol. 529, pp. 484-489, 2016.

Waschneck et al., “Deep reinforcement learning for semiconductor production scheduling”, Proc. 29th. Annu. SEMI Adv. Semicond. Manuf. Conf, 2018.

Yoo, W., Seo, J., Kim, D., and Kim, K., “Machine scheduling models based on reinforcement learning for minimizing due date violation and setup change,” The Journal of Society for e-Business Studies, Vol. 24, No. 3, pp. 19-33, 2019.


Refbacks

  • There are currently no refbacks.