Workflow Scheduling using Graph Segmentation and Reinforcement Learning

doi:10.23940/ijpe.20.08.p13.12621270

Abstract

Abstract: Cloud computing with high availability and good scalability is becoming an important platform to solve scientific workflow problems, and scheduling is the prominent issue for optimal strategy. This paper presents a cloud scheduling algorithm using graph partitioning and reinforcement learning for data-intensive workflow scheduling based on the cloud heterogeneous platform. Aiming at reducing the cost and makespan during the process of task execution, the proposed algorithm firstly evaluates the dual optimization weight of workflow and clusters the tasks that have strong data dependence into blocks by the graph partitioning algorithm. Then, we train the partitioned workflow by iterating the reinforcement learning method such that the match for tasks and resources will meet our expectations. In consideration of performance metrics like total cost and makespan, the partitioning reinforcement learning scheduling algorithm is much better compared to classic algorithms during the simulating experiments conducted on the scientific workflow simulation.

Key words: cloud computing, scientific workflow scheduling, multi-objective optimization, reinforcement learning

Shujun Pei, Qinggen Zhang, and Xuehui Cheng. Workflow Scheduling using Graph Segmentation and Reinforcement Learning [J]. Int J Performability Eng, 2020, 16(8): 1262-1270.

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

References

1. S. W. Liu, L. M. Kong, K. J. Ren, J. Q. Song, K. F. Deng,H. Z. Leng, “A Two-Step Data Placement and Task Scheduling Strategy for Optimizing Scientific Workflow Performance on Cloud Computing Platform,” Chinese Journal of Computers, Vol. 34, No. 11, pp. 2121-2130, 2011
2. L. Cui, S. Y. Lu, X. B. Fei, A. Chebotko, D. Pai, Z. Q. Lai, et al., “A Reference Architecture for Scientific Workflow Management Systems and the View SOA Solution,” IEEE Transactions on Services Computing, Vol. 2, No. 1, pp. 79-92, 2009
3. W. M. Zhang, C. Liu,Z. G. Luo, “A Review on Scientific Workflows,” Journal of National University of Defense Technology, Vol. 33, No. 3, pp. 56-65, 2011
4. Y. Lin, Y. Li, X. Yin,Z. Dou, “Multisensor Fault Diagnosis Modeling based on the Evidence Theory,” IEEE Transactions on Reliability, Vol. 67, No. 2, pp. 513-521, 2018
5. Y. Lin, X. L. Zhu, Z. G. Zheng, Z. Dou,R. L. Zhou, “The Individual Identification Method of Wireless Device based on Dimensionality Reduction and Machine Learning,”Journal of Supercomputing, Vol. 75, pp. 3010-3027, 2019
6. M. Kumar, S. C. Sharma, A. Goel,S. P. Singh, “A Comprehensive Survey for Scheduling Techniques in Cloud Computing,”Journal of Network and Computer Applications, Vol. 143, pp. 1-33, 2019
7. M. Kalra and S. Singh, “A Review of Metaheuristic Scheduling Techniques in Cloud Computing,” Egyptian Informatics Journal, Vol. 16, No. 3, pp. 275-295, 2015
8. E. Aloboud and H. Kuidi, “Cuckoo-Inspired Job Scheduling Algorithm for Cloud Computing,”Procedia Computer Science, Vol. 151, pp. 1078-1083, 2019
9. M. Adhikari and T. Amgoth, “An Intelligent Water Drops-based Workflow Scheduling for IaaS Cloud,”Applied Soft Computing Journal, Vol. 77, pp. 547-566, 2019
10. C. Chen, “Workflow Task Scheduling in Cloud Computing based on Hybrid Improved CS Algorithm and Decision Tree,” Journal of University of Electronic Science and Technology of China, Vol. 45, No. 6, pp. 974-980, 2016
11. S. G. Ahmad, C. S. Liew, M. M. Rafique, E. U. Munir,S. U. Khan, “Data-Intensive Workflow Optimization based on Application Task Graph Partitioning in Heterogeneous Computing Systems,” inProceedings of the 4th IEEE International Conference on Big Data and Cloud Computing, pp. 129-136, 2015
12. I. O. Alexandru, P. Florin,R. Ioan, “New Scheduling Approach using Reinforcement Learning for Heterogeneous Distributed Systems,”Journal of Parallel and Distributed Computing, Vol. 117, pp. 292-302, 2018
13. Y. Tu, Y. Lin,J. Wang, “Semi-Supervised Learning with Generative Adversarial Networks on Digital Signal Modulation Classification”, CMC-Computers Materials and Continua, Vol. 55, No. 2, pp. 243-254, 2018
14. Y. Lin, C. Wang, J. X. Wang,Z. Dou, “A Novel Dynamic Spectrum Access Framework based on Reinforcement Learning for Cognitive Radio Sensor Networks,” Sensors, Vol. 16, No. 10, pp. 1675, 2016
15. J. Niu and C. Lin, “Research on Power Distribution Control Method of Hybrid Electric Vehicle,”Automotive Practical Technology, No. 3, pp. 109-112, 2016
16. Z. Tong, Z. Xiao, K. L. Li,K. Q. Li, “Proactive Scheduling in Distributed Computing - A Reinforcement Learning Approach,” Journal of Parallel and Distributed Computing, Vol. 74, No. 7, pp. 2662-2672, 2014
17. J. H. Zhong, D. L. Cui, Z. P. Peng, Q. R. Li,J. G. He, “Multi Workflow Fair Scheduling Scheme Research based on Reinforcement Learning,”Procedia Computer Science, Vol. 154, pp. 117-123, 2019
18. E. Ipek, O. Mutlu, J. F. Martinez,R. Caruana, “Self-Optimizing Memory Controllers: A Reinforcement Learning Approach,” ACM SIGARCH Computer Architecture News, Vol. 36, No. 3, pp. 39-50, 2008
19. M. Melnik and D. Nasonov, “Workflow Scheduling using Neural Networks and Reinforcement Learning,”Procedia Computer Science, Vol. 156, pp. 29-36, 2019
20. Q. Liu, J. W. Zhai,Z. Z. Zhang, “A Survey on Deep Reinforcement Learning,” Chinese Journal of Computers, Vol. 41, No. 1, pp. 1-27, 2018
21. Y. M. Xu, K. L. Li, J. T. Hu,K. Q. Li, “A Genetic Algorithm for Task Scheduling on Heterogeneous Computing Systems using Multiple Priority Queues,”Information Sciences, Vol. 270, pp. 255-287, 2014
22. S. Bharathi, A. Chervenak, E. Deelman, G. Mehta, M. H. Su,K. Vahi, “Characterization of Scientific Workflows,” inProceedings of the 3rd Workshop on Workflows in Support of Large-Scale Science, pp. 1-10, Austin, 2018
23. W. Chen and E. Deelman, “Workflowsim: A Toolkit for Simulating Scientific Workflows in Distributed Environments,” in Proceedings of2012 IEEE 8th International Conference on E-Science, pp. 1-8, 2012
24. H. Topcuoglu, S. Hariri,M. Y. Wu, “Performance-Effective and Low Complexity Task Scheduling for Heterogeneous Computing,” IEEE Transaction on Parallel and Distributed Systems, Vol. 13, No. 3, pp. 260-274, 2002

[1]	Sushant Jhingran, Mayank Kumar Goyal, and Nitin Rakesh. DQLC: A Novel Algorithm to Enhance Performance of Applications in Cloud Environment [J]. Int J Performability Eng, 2023, 19(12): 771-778.
[2]	Jinxin Wang, Zhiping Zhai, Yuezheng Lan, Xiaoyi Zhai, and Lixiang Zhao. Reliability Analysis and Optimization of Forage Crushers Based on Bayesian Network [J]. Int J Performability Eng, 2023, 19(10): 700-709.
[3]	Priti Kumari and Parmeet Kaur. An Adaptable Approach to Fault Tolerance in Cloud Computing [J]. Int J Performability Eng, 2023, 19(1): 43-54.
[4]	Shaili Mishra and Anuja Arora. Double Deep Q Network with Huber Reward Function for Cart-Pole Balancing Problem [J]. Int J Performability Eng, 2022, 18(9): 644-653.
[5]	Yuting Cheng, Dongcheng Li, W. Eric Wong, Man Zhao, and Dengfeng Mo. Multi-UAV Collaborative Path Planning using Hierarchical Reinforcement Learning and Simulated Annealing [J]. Int J Performability Eng, 2022, 18(7): 463-474.
[6]	Divya Singhal, Laxmi Ahuja, and Ashish Seth. An Insight into Combating Security Attacks for Smart Grid [J]. Int J Performability Eng, 2022, 18(7): 512-520.
[7]	Chengjie Xu, Dongcheng Li, W. Eric Wong, and Man Zhao. Service Caching Strategy based on Edge Computing and Reinforcement Learning [J]. Int J Performability Eng, 2022, 18(5): 350-358.
[8]	Sukruta Pardeshi, chetana Khairnar, and Khalid Alfatmi. Analysis of Data Handling Challenges in Edge Computing [J]. Int J Performability Eng, 2022, 18(3): 176-187.
[9]	Sanjay Razdan, Himanshu Gupta, and Ashish Seth. A Multi-Layer Feed Forward Network Intrusion Detection System using Individual Component Optimization Methodology for Cloud Computing [J]. Int J Performability Eng, 2022, 18(11): 781-790.
[10]	Haoran Li, Dongcheng Li, W. Eric. Wong, Deze Zeng, and Man Zhao. Kubernetes Virtual Warehouse Placement based on Reinforcement Learning [J]. Int J Performability Eng, 2021, 17(7): 579-588.
[11]	Gayathri D and S.P. Shantharajah. A Survey on Fusion of Internet of Things and Cloud Computing [J]. Int J Performability Eng, 2021, 17(11): 946-954.
[12]	D. Sakthivel and B. Radha. Adaptive Model to Detect Anomaly and Real-Time Attacks in Cloud Environment Using Data Mining Algorithm [J]. Int J Performability Eng, 2021, 17(10): 889-899.
[13]	Kun Li, Liwei Jia, and Xiaoming Shi. IPSOMC: An Improved Particle Swarm Optimization and Membrane Computing based Algorithm for Cloud Computing [J]. Int J Performability Eng, 2021, 17(1): 135-142.
[14]	Xiaoxiang Fan. Cloud Computing Task Scheduling based on Improved Bird Swarm Algorithm [J]. Int J Performability Eng, 2021, 17(1): 85-94.
[15]	Priti Kumari and Parmeet Kaur. Connected Data Set-based Virtual Machine Replication in Cloud Computing [J]. Int J Performability Eng, 2020, 16(9): 1351-1361.