Cost-aware cloud workflow scheduling using DRL and simulated annealing

Abstract

Cloud workloads are highly dynamic and complex, making task scheduling in cloud computing a challenging problem. While several scheduling algorithms have been proposed in recent years, they are mainly designed to handle batch tasks and not well-suited for real-time workloads. To address this issue, researchers have started exploring the use of Deep Reinforcement Learning (DRL). However, the existing models are limited in handling independent tasks and cannot process workflows, which are prevalent in cloud computing and consist of related subtasks. In this paper, we propose SA-DQN, a scheduling approach specifically designed for real-time cloud workflows. Our approach seamlessly integrates the Simulated Annealing (SA) algorithm and Deep Q-Network (DQN) algorithm. The SA algorithm is employed to determine an optimal execution order of subtasks in a cloud server, serving as a crucial feature of the task for the neural network to learn. We provide a detailed design of our approach and show that SA-DQN outperforms existing algorithms in terms of handling real-time cloud workflows through experimental results.

Keywords

Cloud computing / Deep reinforcement learning / Simulated annealing algorithm / Job scheduling / Workflow

References

[1] L. Cheng, B.F. van Dongen, W.M. van der Aalst, Scalable discovery of hybrid process models in a cloud computing environment, IEEE Trans. Serv. Comput. 13 (2) (2019) 368-380.

[2] J. Liu, H. Shen, H. Chi, H.S. Narman, Y. Yang, L. Cheng, W. Chung, A low-cost multi-failure resilient replication scheme for high-data availability in cloud storage, IEEE/ACM Trans. Netw. 29 (4) (2020) 1436-1451.

[3] L. Cheng, A. Kalapgar, A. Jain, Y. Wang, Y. Qin, Y. Li, C. Liu, Cost-aware real-time job scheduling for hybrid cloud using deep reinforcement learning, Neural Comput. Appl. 34 (21) (2022) 18579-18593.

[4] Y. Mao, W. Yan, Y. Song, Y. Zeng, M. Chen, L. Cheng, Q. Liu, Differentiate quality of experience scheduling for deep learning inferences with docker containers in the cloud, IEEE Trans. Cloud Comput. 11 (2) (2022) 1667-1677.

[5] A. Tchernykh, U. Schwiegelsohn, V. Alexandrov, E.-g. Talbi,Towards understanding uncertainty in cloud computing resource provisioning, Proc. Comput. Sci. 51 (2015) 1772-1781.

[6] Y. Yu, V. Jindal, I.-L. Yen, F. Bastani, Integrating clustering and learning for im-proved workload prediction in the cloud, in: Proceedings of the 2016 IEEE 9th International Conference on Cloud Computing, IEEE, 2016, pp. 876-879.

[7] Z. Zhao, A. Belloum, C. de Laat, P. Adriaans, B. Hertzberger, Distributed execution of aggregated multi domain workflows using an agent framework, in: Proceedings of the 2007 IEEE Congress on Services, IEEE, 2007, pp. 183-190.

[8] X. Ma, H. Xu, H. Gao, M. Bian, Real-time multiple-workflow scheduling in cloud environments, IEEE Trans. Netw. Serv. Manag. 18 (4) (2021) 4002-4018.

[9] S. Abrishami, M. Naghibzadeh, D.H. Epema, Deadline-constrained workflow scheduling algorithms for infrastructure as a service clouds, Future Gener. Comput. Syst. 29 (1) (2013) 158-169.

[10] Y. Hu, C. de Laat, Z. Zhao, Learning workflow scheduling on multi-resource clusters, in: Proceedings of the 2019 IEEE International Conference on Networking, Architec-ture and Storage, IEEE, 2019, pp. 1-8.

[11] S.Z. Selim, K. Alsultan, A simulated annealing algorithm for the clustering problem, Pattern Recognit. 24 (10) (1991) 1003-1008.

[12] P. Henderson, R. Islam, P. Bachman, J. Pineau, D. Precup, D. Meger, Deep reinforce-ment learning that matters, in: Proceedings of the AAAI Conference on Artificial Intelligence, ACM, 2018, pp. 3207-3214.

[13] M.H. Shirvani, A hybrid meta-heuristic algorithm for scientific workflow scheduling in heterogeneous distributed computing systems, Eng. Appl. Artif. Intell. 90 (2020) 103501.

[14] Y.-H. Jia, W.-N. Chen, H. Yuan, T. Gu, H. Zhang, Y. Gao, J. Zhang, An intelligent cloud workflow scheduling system with time estimation and adaptive ant colony optimization, IEEE Trans. Syst. Man Cybern. Syst. 51 (1) (2018) 634-649.

[15] H.Y. Shishido, J.C. Estrella, C.F.M. Toledo, M.S. Arantes, Genetic-based algorithms applied to a workflow scheduling algorithm with security and deadline constraints in clouds, Comput. Electr. Eng. 69 (2018) 378-394.

[16] X. Zhou, G. Zhang, J. Sun, J. Zhou, T. Wei, S. Hu, Minimizing cost and makespan for workflow scheduling in cloud using fuzzy dominance sort based heft, Future Gener. Comput. Syst. 93 (2019) 278-289.

[17] A. Jayanetti, S. Halgamuge, R. Buyya, Deep reinforcement learning for energy and time optimized scheduling of precedence-constrained tasks in edge-cloud comput-ing environments, Future Gener. Comput. Syst. 137 (2022) 14-30.

[18] R. Xie, D. Gu, Q. Tang, T. Huang, F.R. Yu, Workflow scheduling in serverless edge computing for the industrial Internet of things: a learning approach, IEEE Trans. Ind. Inform. 19 (7) (2022) 8242-8252.

[19] Y. Xiang, X. Yang, Y. Sun, H. Luo, A fault-tolerant and cost-efficient workflow scheduling approach based on deep reinforcement learning for it operation and maintenance, in: Proceedings of the 2023 26th International Conference on Com-puter Supported Cooperative Work in Design, IEEE, 2023, pp. 411-416.

[20] P. Guo, Z. Xue, An adaptive pso-based real-time workflow scheduling algorithm in cloud systems, in: Proceedings of the 2017 IEEE 17th International Conference on Communication Technology, IEEE, 2017, pp. 1932-1936.

[21] J. Liu, J. Ren, W. Dai, D. Zhang, P. Zhou, Y. Zhang, G. Min, N. Najjari, Online multi-workflow scheduling under uncertain task execution time in iaas clouds, IEEE Trans. Cloud Comput. 9(3) (2019) 1180-1194.

[22] H. Chen, X. Zhu, D. Qiu, L. Liu, Uncertainty-aware real-time workflow scheduling in the cloud, in: Proceedings of the 2016 IEEE 9th International Conference on Cloud Computing, IEEE, 2016, pp. 577-584.

[23] F. Song, Y. Ma, I. You, H. Zhang, Smart collaborative evolvement for virtual group creation in customized industrial IoT, IEEE Trans. Netw. Sci. Eng. 10 (5) (2022) 2514-2524.

[24] F. Song, M. Zhu, Y. Zhou, I. You, H. Zhang, Smart collaborative tracking for ubiq-uitous power IoT in edge-cloud interplay domain, IEEE Int. Things J. 7(7) (2019) 6046-6055.

[25] P. Zhang, M. Zhou, Dynamic cloud task scheduling based on a two-stage strategy, IEEE Trans. Autom. Sci. Eng. 15 (2) (2017) 772-783.

[26] X. Chen, L. Cheng, C. Liu, Q. Liu, J. Liu, Y. Mao, J. Murphy, A woa-based optimiza-tion approach for task scheduling in cloud computing systems, IEEE Syst. J. 14 (3)(2020) 3117-3128.

[27] M. Adhikari, T. Amgoth, S.N. Srirama, A survey on scheduling strategies for work-flows in cloud environment and emerging trends, ACM Comput. Surv. 52 (4) (2019) 1-36.

[28] Z. Sun, B. Zhang, C. Gu, R. Xie, B. Qian, H. Huang, ET2FA: a hybrid heuristic al-gorithm for deadline-constrained workflow scheduling in cloud, IEEE Trans. Serv. Comput. 16 (3) (2022) 1807-1821.

[29] J. Guo, L. Cheng, S. Wang, CoTV: cooperative control for traffic light signals and connected autonomous vehicles using deep reinforcement learning, IEEE Trans. In-tell. Transp. Syst. 24 (10) (2023) 10501-10512.

[30] Q. Liu, L. Cheng, A.L. Jia, C. Liu, Deep reinforcement learning for communication flow control in wireless mesh networks, IEEE Netw. 35 (2) (2021) 112-119.

[31] M. Mekala, G. Dhiman, G. Srivastava, Z. Nain, H. Zhang, W. Viriyasitavat, G. Varma, A DRL-based service offloading approach using dag for edge computational orches-tration, IEEE Trans. Comput. Soc. Syst. (3) (2024) 3070-3078.

[32] L. Wang, E. Gelenbe, Adaptive dispatching of tasks in the cloud, IEEE Trans. Cloud Comput. 6(1) (2015) 33-45.

[33] K. Arulkumaran, M.P. Deisenroth, M. Brundage, A.A. Bharath, Deep reinforcement learning: a brief survey, IEEE Signal Process. Mag. 34 (6) (2017) 26-38.

[34] E.A. Avello, F.F. Baesler, R.J. Moraga, A meta-heuristic based on simulated anneal-ing for solving multiple-objective problems in simulation optimization, in: Proceed-ings of the 2004 Winter Simulation Conference, IEEE, 2004.

[35] M. Ghobaei-Arani, S. Jabbehdari, M.A. Pourmina, An autonomic resource provision-ing approach for service-based cloud applications: a hybrid approach, Future Gener. Comput. Syst. 78 (2018) 191-210.

[36] Y. Wei, L. Pan, S. Liu, L. Wu, X. Meng, DRL-scheduling: an intelligent qos-aware job scheduling framework for applications in clouds, IEEE Access 6 (2018) 55112-55125.