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

Year 2024, Volume: 6 Issue: 2, 116 - 140, 30.08.2024

Bünyamin Sarıcan , Orhan Engin

https://doi.org/10.46740/alku.1390397

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

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

References

• [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] 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] 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] 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] 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] Thomas, G. (2009). Multi-Agent Reinforcement Learning Approaches for Distributed Job-Shop Scheduling Problems. Computer Science, 1-173.
• [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] Dietterich, T. G. (2000). Hierarchical Reinforcement Learning with the MAXQ Value Function Decomposition. Journal of Artificial Intelligence Research (C. 13).
• [9] Sutton, R. S., & Barto, A. G. (1998). Reinforcement learning: an introduction. MIT Press.
• [10] Wiering, M., Ch, M., Urgen, J. ¨, & Ch, S. J. (1998). Fast Online Q(λ). Machine Learning (C. 33).
• [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] 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] 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] Li, Y. (2018). Deep Reinforcement Learning. http://arxiv.org/abs/1810.06339
• [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] Martínez Jiménez, Y. (2012). A Generic Multi-Agent Reinforcement Learning Approach for Scheduling Problems. VUBPRESS Brussels University Press. www.vubpress.be
• [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] Tanyaş, M., & Baskak, M. (2012). Üretim Planlama ve Kontrol. İrfan Yayıncılık.
• [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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] Gabel, T., & Riedmiller, M. (2008). Adaptive Reactive Job Shop Scheduling with Reinforcement Learning Agents. International Journal of Information Technology and Intelligent Computing.
• [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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] Zhou, H., Gu, B., & Jin, C. (2022). Reinforcement Learning Approach for Multi-Agent Flexible Scheduling Problems. http://arxiv.org/abs/2210.03674
• [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] 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] 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] 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] 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