Analysis of Reinforcement Learning Effect in Solving Scheduling Problems

Abstract

Reinforcement learning is actively used to find solutions to many real life problems in today's world and is shown among the promising methods in the industry. This study investigated the effect of reinforcement learning, which is a sub-branch of machine learning, in solving job scheduling problems. In this context, first of all, situation definition, action selection and learning algorithms in reinforcement learning are explained. Then, the classification of the job scheduling problem is given. In the literature, 50 articles published in the last twenty years, in which the reinforcement learning method is used in job scheduling, are included. The effects of the studies in the literature on the solution of scheduling problems were evaluated. In the last section, the strengths and weaknesses of reinforcement learning compared to other solution methods are included and evaluations for future research are made. .

Keywords

• Scheduling Optimization
• Machine Learning
• Job Scheduling
• Reinforcement Learning

Makine Çizelgeleme Problemlerinin Çözümünde Pekiştirmeli Öğrenme Etkisinin Analizi

Abstract

Pekiştirmeli öğrenme, günümüz dünyasında birçok gerçek hayat problemine çözüm bulmada aktif bir şekilde kullanılmakta ve endüstri içerisinde de umut verici yöntemler arasında gösterilmektedir. Bu çalışmada, makine öğrenmesinin bir alt dalı olan pekiştirmeli öğrenmenin iş çizelgeleme problemlerinin çözümündeki etkisi araştırılmıştır. Bu kapsamda, öncelikle pekiştirmeli öğrenmede durum tanımı, eylem seçimi ve öğrenme algoritmaları açıklanmıştır. Ardından, iş çizelgeleme probleminin sınıflandırmasına yer verilmiştir. Literatürde yer alan iş çizelgelemede, pekiştirmeli öğrenme yönteminin kullanıldığı, son yirmi yılda yayımlanan, 50 makale çalışmasına yer verilmiştir. Literatürde yer alan çalışmaların çizelgeleme problemlerinin çözümü üzerinde gösterdiği etki değerlendirilmiştir. Son bölümde pekiştirmeli öğrenmenin diğer çözüm yöntemlerine kıyasla güçlü ve zayıf yönlerine yer verilmiş ayrıca gelecekte yapılacak araştırmalara yönelik değerlendirmelerde bulunulmuştur.

Keywords

• Çizelgeleme Optimizasyonu
• Makine Öğrenmesi
• İş Çizelgeleme
• Pekiştirmeli Öğrenme

References

1. [1] Engin, O., Kahraman, C. & Yilmaz, M.K. (2009). A Scatter Search Method for Multiobjective Fuzzy Permutation Flow Shop Scheduling Problem: A Real World Application. U.K. Chakraborty (Ed.): Computational Intelligence in Flow Shop and Job Shop Scheduling. SCI, 230, 169- 189. Springer-Verlag Berlin Heidelberg.
2. [2] Engin, O., Yılmaz, M. K., Baysal, M. E & Sarucan, A. (2013). Solving Fuzzy Job Shop Scheduling Problems with Availability Constraints Using a Scatter Search Method. J. of Mult. -Valued Logic & Soft Computing, 21, 317- 334.
3. [3] Engin, O., Özmete, A., İpek, S. & Karoğlu, Y.E. (2023). Çizelgeleme Problemlerinin Çözümünde Hibrit Biyocoğrafya Tabanlı Optimizasyon Algoritmasının Kullanımı. Harran Üniversitesi Mühendislik Dergisi, 8(1), 68-77. https://doi.org/10.46578/humder.1256671
4. [4] Manzak, R., Engin, O. (2023). Akıllı Fabrikalarda Çizelgeleme Yöntemlerinin Analizi, Verimlilik Dergisi, 57, 4, 761- 774. https://doi.org/10.51551/verimlilik.1136778
5. [5] Oppermann A. (2023). Self Learning AI-Agents Part I: Markov Decision Processes. [Erişim Tarihi: 01.11.2023] https://towardsdatascience.com/self-learning-ai-agents-part-i-markov-decision-processes-baf6b8fc4c5f
6. [6] Thomas, G. (2009). Multi-Agent Reinforcement Learning Approaches for Distributed Job-Shop Scheduling Problems. Computer Science, 1-173.
7. [7] Sutton, R. S., & Barto, A. G. (2015). Reinforcement Learning: An Introduction, Second edition, in progress, 1- 352, The MIT Press Cambridge, Massachusetts London, England.
8. [8] Dietterich, T. G. (2000). Hierarchical Reinforcement Learning with the MAXQ Value Function Decomposition. Journal of Artificial Intelligence Research (C. 13).

9. [9] Sutton, R. S., & Barto, A. G. (1998). Reinforcement learning: an introduction. MIT Press.
10. [10] Wiering, M., Ch, M., Urgen, J. ¨, & Ch, S. J. (1998). Fast Online Q(λ). Machine Learning (C. 33).
11. [11] Kayhan, B. M., & Yildiz, G. (2023). Reinforcement learning applications to machine scheduling problems: a comprehensive literature review, Journal of Intelligent Manufacturing. 34, 905-929, Springer. https://doi.org/10.1007/s10845-021-01847-3
12. [12] De Koning, M. C. T. C. (2020). Fleet Planning Under Demand Uncertainty A Reinforcement Learning Approach. https://stmed.net/sites/default/files/airport-wallpapers-28369-9089125.jpg.
13. [13] Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidjeland, A. K., Ostrovski, G., Petersen, S., Beattie, C., Sadik, A., Antonoglou, I., King, H., Kumaran, D., Wierstra, D., Legg, S., & Hassabis, D. (2015). Human-level control through deep reinforcement learning. Nature, 518(7540), 529-533. https://doi.org/10.1038/nature14236
14. [14] Li, Y. (2018). Deep Reinforcement Learning. http://arxiv.org/abs/1810.06339
15. [15] Grondman, I., Busoniu, L., Lopes, G. A. D., & Babuška, R. (2012). A survey of actor-critic reinforcement learning: Standard and natural policy gradients. Içinde IEEE Transactions on Systems, Man and Cybernetics Part C: Applications and Reviews (C. 42, Sayı 6, ss. 1291-1307). https://doi.org/10.1109/TSMCC.2012.2218595
16. [16] Martínez Jiménez, Y. (2012). A Generic Multi-Agent Reinforcement Learning Approach for Scheduling Problems. VUBPRESS Brussels University Press. www.vubpress.be
17. [17] Başar, R., Engin, O. (2022). Beklemesiz Akış Tipi Çizelgeleme Problemlerinin Analizi ve Hibrit Dağınık Arama Yöntemi ile Çözümü, Çanakkale Onsekiz Mart University Journal of Advanced Research in Natural and Applied Sciences, 8 (2) 293- 308. https://doi.org/10.28979/jarnas.936151
18. [18] Tanyaş, M., & Baskak, M. (2012). Üretim Planlama ve Kontrol. İrfan Yayıncılık.
19. [19] Engin, O., Fığlalı, A. (2002). Akış Tipi Çizelgeleme Problemlerinin Genetik Algoritma Yardımı ile Çözümünde Uygun Çaprazlama Operatörünün Belirlenmesi. Doğuş Üniversitesi Dergisi, 6, 27- 35.
20. [20] Engin, O., Engin, B. (2018). Hybrid Flow Shop with Multiprocessor Task Scheduling Based on Earliness and Tardiness Penalties, Journal of Enterprise Information Management, 31, 6, 925- 936. https://doi.org/10.1108/JEIM-04-2017-0051
21. [21] Engin, O., Günaydın, C. (2011). An Adaptive Learning Approach for No-Wait Flowshop Scheduling Problems to Minimize Makespan. International Journal of Computational Intelligence Systems, 4, 4, 521- 529.
22. [22] Saç, İ, Engin, O. (2018). Bloklama Kısıtlı Akış Tipi Çizelgeleme Problemlerinin Maymun Arama Algoritması ile Çözümü. Journal of Social and Humanities Science Research, 5, 24, 1815- 1821.
23. [23] Baysal, M. E., Sarucan, A., Büyüközkan, K. & Engin, O. (2022) Artificial Bee Colony Algorithm for Solving multi-objective Distributed Fuzzy Permutation Flow Shop Problem. Journal of Intelligent & Fuzzy Systems, 42, 439- 449. https://doi.org/10.3233/JIFS-219202
24. [24] Külahlı, S., Engin, O., Koç, İ. (2021). A New Hybrid Scatter Search Method for Solving the Flexible Job Shop Scheduling Problems. Celal Bayar University Journal of Science, 17, 4, 347- 359. DOI: 10.18466/cbayarfbe.926756
25. [25] Baysal, M. E., Durmaz, T., Sarucan, A., Engin, O. (2012). Açık Atölye Tipi Çizelgeleme Problemlerinin Paralel Kanguru Algoritması ile Çözümü. Gazi Üniv. Müh. Mim. Fak. Der. 27, 4, 855- 864.
26. [26] Vollmann, T. E., Berry, W. L., Whybark, D. C., & Jacobs F.R. (2005). Manufacturing Planning and Control for Supply Chain Management. Mc Graw-Hill Book Companies Inc.
27. [27] Kılıç, M. (2021). Bir Tekstil Firmasının Boyahane Bölümünde Paralel Makine Çizelgeleme Problemi İçin Bir Matematiksel Model Önerisi ve Farklı Çizelgeleme Kurallarının Karşılaştırılması. Necmettin Erbakan Üniversitesi, Fen Bilimleri Enstitüsü Endüstri Mühendisliği Anabilim Dalı, Konya
28. [28] Wang, Y. C., & Usher, J. M. (2005). Application of reinforcement learning for agent-based production scheduling. Engineering Applications of Artificial Intelligence, 18(1), 73-82. https://doi.org/10.1016/j.engappai.2004.08.018
29. [29] Wang, H., Yan, Q., & Zhang, S. (2021). Integrated scheduling and flexible maintenance in deteriorating multi-state single machine system using a reinforcement learning approach. Advanced Engineering Informatics, 49. https://doi.org/10.1016/j.aei.2021.101339
30. [30] Yang, H., Li, W., & Wang, B. (2021). Joint optimization of preventive maintenance and production scheduling for multi-state production systems based on reinforcement learning. Reliability Engineering and System Safety, 214. https://doi.org/10.1016/j.ress.2021.107713
31. [31] Deliktaş, D. (2022). Self-adaptive memetic algorithms for multi-objective single machine learning-effect scheduling problems with release times. Flexible Services and Manufacturing Journal, 34(3), 748-784. https://doi.org/10.1007/s10696-021-09434-7
32. [32] Lopes Silva, M. A., de Souza, S. R., Freitas Souza, M. J., & Bazzan, A. L. C. (2019). A reinforcement learning-based multi-agent framework applied for solving routing and scheduling problems. Expert Systems with Applications, 131, 148-171. https://doi.org/10.1016/j.eswa.2019.04.056
33. [33] Liangxun Guo, Z. Z. Z. H. W. Q. (2020). Optimization of Dynamic Multi-Objective Non-İdentical Parallel Machine Scheduling With Multi-Stage Reinforcement Learning. 2020 16th IEEE International Conference on Automation Science and Engineering (CASE). https://doi.org/10.0/Linux-x86_64
34. [34] Chien, C. F., & Lan, Y. B. (2021). Agent-based approach integrating deep reinforcement learning and hybrid genetic algorithm for dynamic scheduling for Industry 3.5 smart production. Computers and Industrial Engineering, 162. https://doi.org/10.1016/j.cie.2021.107782
35. [35] Arviv, K., Stern, H., & Edan, Y. (2016). Collaborative reinforcement learning for a two-robot job transfer flow-shop scheduling problem. International Journal of Production Research, 54(4), 1196-1209. https://doi.org/10.1080/00207543.2015.1057297
36. [36] Wang, X., & Tang, L. (2017). A machine-learning based memetic algorithm for the multi-objective permutation flowshop scheduling problem. Computers and Operations Research, 79, 60-77. https://doi.org/10.1016/j.cor.2016.10.003
37. [37] Shao, W., Pi, D., & Shao, Z. (2018). A hybrid discrete teaching-learning based meta-heuristic for solving no-idle flow shop scheduling problem with total tardiness criterion. Computers and Operations Research, 94, 89-105. https://doi.org/10.1016/j.cor.2018.02.003
38. [38] Han, W., Guo, F., & Su, X. (2019). A reinforcement learning method for a hybrid flow-shop scheduling problem. Algorithms, 12(11). https://doi.org/10.3390/a12110222
39. [39] Zhao, F., Zhang, L., Cao, J., & Tang, J. (2021). A cooperative water wave optimization algorithm with reinforcement learning for the distributed assembly no-idle flowshop scheduling problem. Computers and Industrial Engineering, 153. https://doi.org/10.1016/j.cie.2020.107082
40. [40] Chen, R., Yang, B., Li, S., Wang, S., & Cheng, Q. (2021). An Effective Multi-population Grey Wolf Optimizer based on Reinforcement Learning for Flow Shop Scheduling Problem with Multi-machine Collaboration. Computers and Industrial Engineering, 162. https://doi.org/10.1016/j.cie.2021.107738
41. [41] Pan, Z., Wang, L., Wang, J., & Lu, J. (2021). Deep Reinforcement Learning Based Optimization Algorithm for Permutation Flow-Shop Scheduling. IEEE Transactions on Emerging Topics in Computational Intelligence. https://doi.org/10.1109/TETCI.2021.3098354
42. [42] Cai, J., Lei, D., Wang, J., & Wang, L. (2022). A novel shuffled frog-leaping algorithm with reinforcement learning for distributed assembly hybrid flow shop scheduling. International Journal of Production Research, 1-19. https://doi.org/10.1080/00207543.2022.2031331
43. [43] Zhao, F., Hu, X., Wang, L., Xu, T., Zhu, N., & Jonrinaldi. (2022). A reinforcement learning-driven brain storm optimisation algorithm for multi-objective energy-efficient distributed assembly no-wait flow shop scheduling problem. International Journal of Production Research. https://doi.org/10.1080/00207543.2022.2070786
44. [44] Zhao, F., Wang, Z., & Wang, L. (2022). A Reinforcement Learning Driven Artificial Bee Colony Algorithm for Distributed Heterogeneous No-Wait Flowshop Scheduling Problem With Sequence-Dependent Setup Times. IEEE Transactions on Automation Science and Engineering, 1-16. https://doi.org/10.1109/tase.2022.3212786
45. [45] Zhao, F., Jiang, T., & Wang, L. (2022). A Reinforcement Learning Driven Cooperative Meta-Heuristic Algorithm for Energy-Efficient Distributed No-Wait Flow-Shop Scheduling with Sequence-Dependent Setup Time. IEEE Transactions on Industrial Informatics, 1-12. https://doi.org/10.1109/tii.2022.3218645
46. [46] Yan, Q., Wu, W., & Wang, H. (2022). Deep Reinforcement Learning for Distributed Flow Shop Scheduling with Flexible Maintenance. Machines, 10(3). https://doi.org/10.3390/machines10030210
47. [47] Nahhas, A., Kharitonov, A., & Turowski, K. (2022). Deep Reinforcement Learning Techniques for Solving Hybrid Flow Shop Scheduling Problems: Proximal Policy Optimization (PPO) and Asynchronous Advantage Actor-Critic (A3C). https://hdl.handle.net/10125/79538
48. [48] He, Z., Wang, K., Li, H., Song, H., Lin, Z., Gao, K., & Sadollah, A. (2022). Improved Q-learning algorithm for solving permutation flow shop scheduling problems. IET Collaborative Intelligent Manufacturing, 4(1), 35-44. https://doi.org/10.1049/cim2.12042
49. [49] Dong, Z., Ren, T., Weng, J., Qi, F., & Wang, X. (2022). Minimizing the Late Work of the Flow Shop Scheduling Problem with a Deep Reinforcement Learning Based Approach. Applied Sciences (Switzerland), 12(5). https://doi.org/10.3390/app12052366
50. [50] Yang, S., & Xu, Z. (2022). Intelligent scheduling and reconfiguration via deep reinforcement learning in smart manufacturing. International Journal of Production Research, 60(16), 4936-4953. https://doi.org/10.1080/00207543.2021.1943037
51. [51] Ying, K. C., & Lin, S. W. (2022). Reinforcement learning iterated greedy algorithm for distributed assembly permutation flowshop scheduling problems. Journal of Ambient Intelligence and Humanized Computing. https://doi.org/10.1007/s12652-022-04392-w
52. [52] Gabel, T., & Riedmiller, M. (2008). Adaptive Reactive Job Shop Scheduling with Reinforcement Learning Agents. International Journal of Information Technology and Intelligent Computing.
53. [53] Luo, S. (2020). Dynamic scheduling for flexible job shop with new job insertions by deep reinforcement learning. Applied Soft Computing Journal, 91. https://doi.org/10.1016/j.asoc.2020.106208
54. [54] Han, B. A., & Yang, J. J. (2021). A deep reinforcement learning based solution for flexible job shop scheduling problem. International Journal of Simulation Modelling, 20(2), 375-386. https://doi.org/10.2507/IJSIMM20-2-CO7
55. [55] Magalhaes, R., Martins, M., Vieira, S., Santos, F., & Sousa, J. (2021). Encoder-Decoder Neural Network Architecture for solving Job Shop Scheduling Problems using Reinforcement Learning. 2021 IEEE Symposium Series on Computational Intelligence, SSCI 2021 - Proceedings. https://doi.org/10.1109/SSCI50451.2021.9659849
56. [56] Feng, Y., Zhang, L., Yang, Z., Guo, Y., & Yang, D. (2021). Flexible Job Shop Scheduling Based on Deep Reinforcement Learning. Proceedings of 2021 5th Asian Conference on Artificial Intelligence Technology, ACAIT 2021, 660-666. https://doi.org/10.1109/ACAIT53529.2021.9731322
57. [57] Long, X., Zhang, J., Qi, X., Xu, W., Jin, T., & Zhou, K. (2022). A self-learning artificial bee colony algorithm based on reinforcement learning for a flexible job-shop scheduling problem. Concurrency and Computation: Practice and Experience, 34(4). https://doi.org/10.1002/cpe.6658
58. [58] Li, R., Gong, W., & Lu, C. (2022). A reinforcement learning based RMOEA/D for bi-objective fuzzy flexible job shop scheduling. Expert Systems with Applications, 203. https://doi.org/10.1016/j.eswa.2022.117380
59. [59] Lei, K., Guo, P., Wang, Y., Xiong, J., & Zhao, W. (2022). An End-to-end Hierarchical Reinforcement Learning Framework for Large-scale Dynamic Flexible Job-shop Scheduling Problem. Proceedings of the International Joint Conference on Neural Networks, 2022-July. https://doi.org/10.1109/IJCNN55064.2022.9892005
60. [60] Chang, J., Yu, D., Hu, Y., He, W., & Yu, H. (2022). Deep Reinforcement Learning for Dynamic Flexible Job Shop Scheduling with Random Job Arrival. Processes, 10(4). https://doi.org/10.3390/pr10040760
61. [61] Liu, R., Piplani, R., & Toro, C. (2022). Deep reinforcement learning for dynamic scheduling of a flexible job shop. International Journal of Production Research, 60(13), 4049-4069. https://doi.org/10.1080/00207543.2022.2058432
62. [62] Zhang, J.-D., He, Z., Chan, W.-H., & Chow, C.-Y. (2022). DeepMAG: Deep reinforcement learning with multi-agent graphs for flexible job shop scheduling. Knowledge-Based Systems, 110083. https://doi.org/10.1016/j.knosys.2022.110083
63. [63] Oh, S. H., Cho, Y. I., & Woo, J. H. (2022). Distributional reinforcement learning with the independent learners for flexible job shop scheduling problem with high variability. Journal of Computational Design and Engineering, 9(4), 1157-1174. https://doi.org/10.1093/jcde/qwac044
64. [64] Zeng, Y., Liao, Z., Dai, Y., Wang, R., Li, X., & Yuan, B. (2022). Hybrid intelligence for dynamic job-shop scheduling with deep reinforcement learning and attention mechanism. http://arxiv.org/abs/2201.00548
65. [65] Cunha, B., Madureira, A., Fonseca, B., & Matos, J. (2021). Intelligent scheduling with reinforcement learning. Applied Sciences (Switzerland), 11(8). https://doi.org/10.3390/app11083710
66. [66] Khuntiyaporn, T., Songmuang, P., & Limprasert, W. (2021). The Multiple Objectives Flexible Jobshop Scheduling Using Reinforcement Learning. 16th International Joint Symposium on Artificial Intelligence and Natural Language Processing, iSAI-NLP 2021. https://doi.org/10.1109/iSAI-NLP54397.2021.9678152
67. [67] Du, Y., Li, J. qing, Chen, X. long, Duan, P. yong, & Pan, Q. ke. (2022). Knowledge-Based Reinforcement Learning and Estimation of Distribution Algorithm for Flexible Job Shop Scheduling Problem. IEEE Transactions on Emerging Topics in Computational Intelligence. https://doi.org/10.1109/TETCI.2022.3145706
68. [68] Wang, H., Cheng, J., Liu, C., Zhang, Y., Hu, S., & Chen, L. (2022). Multi-objective reinforcement learning framework for dynamic flexible job shop scheduling problem with uncertain events. Applied Soft Computing, 109717. https://doi.org/10.1016/j.asoc.2022.109717
69. [69] Chen, Z., Zhang, L., Wang, X., & Gu, P. (2022). Optimal Design of Flexible Job Shop Scheduling Under Resource Preemption Based on Deep Reinforcement Learning. Complex System Modeling and Simulation, 2(2), 174-185. https://doi.org/10.23919/csms.2022.0007
70. [70] Luo, S., Zhang, L., & Fan, Y. (2022). Real-Time Scheduling for Dynamic Partial-No-Wait Multiobjective Flexible Job Shop by Deep Reinforcement Learning. IEEE Transactions on Automation Science and Engineering, 19(4), 3020-3038. https://doi.org/10.1109/TASE.2021.3104716
71. [71] Zhou, H., Gu, B., & Jin, C. (2022). Reinforcement Learning Approach for Multi-Agent Flexible Scheduling Problems. http://arxiv.org/abs/2210.03674
72. [72] Popper, J., & Ruskowski, M. (2022). Using Multi-Agent Deep Reinforcement Learning For Flexible Job Shop Scheduling Problems. Procedia CIRP, 112, 63-67. https://doi.org/10.1016/j.procir.2022.09.039
73. [73] Park, J., Bakhtiyar, S., & Park, J. (2021). ScheduleNet: Learn to solve multi-agent scheduling problems with reinforcement learning. http://arxiv.org/abs/2106.03051
74. [74] Kim, G.H., Lee, C.S.G. (1998). Genetic Reinforcement Learning Approach To The Heterogeneous Machine Scheduling Problem, IEEE Transactions On Robotics And Automation, 14, 6, 879- 893.
75. [75] Kim, Y. G., Lee, S., Son, J., Bae, H., & Chung, B. Do. (2020). Multi-agent system and reinforcement learning approach for distributed intelligence in a flexible smart manufacturing system. Journal of Manufacturing Systems, 57, 440-450. https://doi.org/10.1016/j.jmsy.2020.11.004
76. [76] Wang, J., Lei, D., & Cai, J. (2022). An adaptive artificial bee colony with reinforcement learning for distributed three-stage assembly scheduling with maintenance. Applied Soft Computing, 117. https://doi.org/10.1016/j.asoc.2021.108371