Job Scheduling and Simulation in Cloud Based on Deep Reinforcement Learning

doi:10.16182/j.issn1004731x.joss.21-0337

Abstract

Abstract:

To solve the difficulty in job scheduling in the complex and transient multi-user, multi-queue, and multi-data-center cloud computing environment, this paper proposed a job scheduling method based on deep reinforcement learning. A system model of cloud job scheduling and its mathematical model were built, and an optimization goal consisting of transmission time, waiting time, and execution time was obtained. A job scheduling algorithm based on deep reinforcement learning was designed, and its state space, action space, and reward function were given. A simulated cloud job scheduler was designed and developed, and simulated scheduling experiments were conducted on it. The results show that compared with benchmark algorithms such as random scheduling, round-robin scheduling, firstfit, and optimal fit, the proposed algorithm could effectively reduce the overall makespan of the jobs.

Key words: cloud computing, job scheduling, deep reinforcement learning, makespan, multi-user, multi-queue, multi-data-center

CLC Number:

TP391.9

Qirui Li, Xinyi Peng. Job Scheduling and Simulation in Cloud Based on Deep Reinforcement Learning[J]. Journal of System Simulation, 2022, 34(2): 258-268.

Figures/Tables 10

Fig. 1

Fig. 2

Table 1

Fig. 3

Fig. 4

Table 2

Hyperparameters of DQN network

参数	值	参数	值
训练回合数量	5 000	目标网络更新频率	300
学习率 $α$	0.01	初始 $ε$ 值	0.2
折扣因子β	0.9	最大 $ε$ 值	0.9
样本池规模	500	$ε$ 每回合增幅	0.002
批样本数	64	等待时间系数 $ζ$	0.5
隐藏层数	2	传输时间系数 $ξ$	1

Table 2

Fig. 5

Fig. 6

Fig. 7

Fig. 8

References 20

1	Xu Z, Liang W, Xia Q. Efficient Embedding of Virtual Networks to Distributed Clouds via Exploring Periodic Resource Demands[J]. IEEE Transactions on Cloud Computing(S2168-7161), 2018, 6(3): 694-707.
2	李成辉, 李仁旺, 杨强光, 等. 基于改进萤火虫算法的云计算任务调度算法[J]. 浙江理工大学学报(自然科学版), 2019, 41(3): 354-359.
	Li Chenghui, Li Renwang, Yang Qiangguang, et al. Cloud Computing Task Scheduling Algorithm Based on Improved Firefly Algorithm[J]. Journal of Zhejiang Sci-Tech University(Natural Sciences Edition), 2019, 41(3):354-359.
3	王康瑾, 贾统, 李影. 在离线混部作业调度与资源管理技术研究综述[J].软件学报, 2020, 31(10): 3100-3119.
	Wang Kangjin, Jia Tong, Li Ying. State-of-the-art Survey of Scheduling and Resource Management Technology for Colocation Jobs[J]. Journal of Software, 2020,31(10):3100-3119.
4	Verma A, Kaushal S. A hybrid Multi-objective Particle Swarm Optimization for Scientific Workflow Scheduling[J]. Parallel Computing(S0167-8191), 2017, 62: 1-19.
5	Duan H, Chen C, Min G, et al. Energy-aware Scheduling of Virtual Machines in Heterogeneous Cloud Computing Systems[J]. Future Generation Computer Systems(S0167-739X), 2017, 74: 142-150.
6	Srichandan S, Turuk A K S. Task Scheduling for Cloud Computing Using Multi-objective Hybrid Bacteria Foraging Algorithm[J]. Future Computing and Informatics Journal(S2314-7288), 2018, 3(2): 210-23.
7	李强, 刘晓峰. 基于模拟植物生长算法的云作业调度模型[J]. 系统仿真学报, 2018, 30(12): 4649-4658.
	Li Qiang, Liu Xiaofeng. Cloud Job Scheduling Model Based on Improved Plant Growth Algorithm[J]. Journal of System Simulation, 2018, 30(12): 4649-4658.
8	殷昌盛, 杨若鹏, 朱巍, 等. 多智能体分层强化学习综述[J]. 智能系统学报, 2020, 15(4): 646-655.
	Yin Changsheng, Yang Ruopeng, Zhu Wei, et al. A Survey on Multi-agent Hierarchical Reinforcement Learning[J]. CAAI Transactions on Intelligent Systems, 2020, 15(4): 646-655.
9	Peng Z, Cui D, Zuo J, et al. Random Task Scheduling Scheme Based on Reinforcement Learning in Cloud Computing[J]. Cluster Computing(S1386-7857), 2015, 18: 1595-1607.
10	Cui D, Peng Z, Xiong J, et al. A Reinforcement Learning-Based Mixed Job Scheduler Scheme for Grid or IaaS Cloud[J]. IEEE Transactions on Cloud Computing(S2168-7161), 2020, 4: 1030-1039.
11	袁景凌, 陈旻骋, 江涛, 等. 异构云环境下AHP定权的多目标强化学习作业调度方法[J/OL].(2021-01-05) 控制与决策, 2021:1-8. .
	Yuan Jingling, Chen Minchi, Jiang Tao, et al. Multi-Objective Reinforcement Learning Job Scheduling Method using AHP Fixed Weight in Heterogeneous Cloud Environment[J/OL].(2021-01-05) Control and Decision, 2021:1-8. .
12	Lin J, Cui D, Peng Z, et al. A Two-Stage Framework for the Multi-User Multi-Data Center Job Scheduling and Resource Allocation[J]. IEEE Access(S2169-3536), 2020, 8: 197863-197874.
13	郭玉栋, 左金平. 基于霍普菲尔德网络的云作业调度算法[J]. 系统仿真学报, 2019, 31(12): 2859-2867.
	Guo Yudong, Zuo Jinping. The Scheduling Algorithm of Cloud Job Based on Hopfield Neural Network[J]. Journal of System Simulation, 2019, 31(12): 2859-2867.
14	Rangra A, Sehgal V K, Shukla S. A Novel Approach of Cloud Based Scheduling Using Deep-Learning Approach in E-Commerce Domain[J]. International Journal of Information System Modeling and Design(S1947-8186), 2019, 10(3): 59-75.
15	李凯文, 张涛, 王锐, 等. 基于深度强化学习的组合优化研究进展[J]. 自动化学报, 2021, 47(11): 2521-2537.
	Li Kaiwen, Zhang Tao, Wang Rui, et al. Research Reviews of Combinatorial Optimization Methods Based on Deep Reinforcement Learning[J]. Acta Automatica Sinica, 2021, 47(11): 2521-2537.
16	朱斐, 吴文, 伏玉琛, 等. 基于双深度网络的安全深度强化学习方法[J].计算机学报, 2019, 42(8): 1812-1826.
	Zhu Fei, Wu Wen, Fu Yushen, et al. A Dual Deep Network Based Secure Deep Reinforcement Learning Method[J]. Chinese Journal of Computers, 2019, 42(8): 1812-1826.
17	Guo W, Tian W, Ye Y, et al. Cloud Resource Scheduling With Deep Reinforcement Learning and Imitation Learning[J]. IEEE Internet of Things Journal(S2327-4662), 2021, 8(5): 3576-3586.
18	Peng Z, Lin J, Cui D, et al. A Multi-objective Trade-off Framework for Cloud Resource Scheduling Based on the Deep Q-network Algorithm[J]. Cluster Computing(S1386-7857), 2020, 23(4): 2753-2767.
19	Lin J, Peng Z, Cui D. Deep Reinforcement Learning for Multi-resource Cloud Job Scheduling[C]// 2018 25th International Conference on Neural Information Processing. Berlin: Springer, 2018: 289-302.
20	Miettinen A, Nurminen J. Energy Efficiency of Mobile Clients in Cloud Computing[C]// Boston: USENIX Association, 2010: 1-7.

序号	计算能力(cycles)	核心数(个)	带宽/Mbps
1	650	4	200
2	1 850	8	300
3	2 500	12	500
4	700	6	250
5	2 050	10	400
6	1 500	8	200

[1]	Sen Zhang, Mengyan Zhang, Jingping Shao, Jiexin Pu. Multi-UAVs 3D Path Planning Method Based on Random Strategy Search [J]. Journal of System Simulation, 2022, 34(6): 1286-1295.
[2]	Lingjia Ni, Xiaoxia Huang, Hongga Li, Zibo Zhang. Research on Fire Emergency Evacuation Simulation Based on Cooperative Deep Reinforcement Learning [J]. Journal of System Simulation, 2022, 34(6): 1353-1366.
[3]	Hongwei Wang, Peng Yang. Research on Optimization of Airport Cargo Business Based on Deep Reinforcement Learning [J]. Journal of System Simulation, 2022, 34(3): 651-660.
[4]	Gao Ang, Dong Zhiming, Zhang Guohui, Liang Tao, Guo Qisheng. Research on Generation Technology of Computer Generated Force in LVC Training System [J]. Journal of System Simulation, 2021, 33(3): 745-752.
[5]	Zeng Bi, Fang Xiao, Kong Deshuai, Song Xiangxiang, Jia Zhengxuan, Lin Tingyu. A Data-Driven Modeling Method for Game Adversity Agent [J]. Journal of System Simulation, 2021, 33(12): 2838-2845.
[6]	Liu Changping, Jian Zhenfu, Fu Wenhan. A Discrete Krill Herd Algorithm for the No-wait Flow Shop Scheduling Problem [J]. Journal of System Simulation, 2020, 32(6): 1051-1059.
[7]	Zhang Huili, Li Zhihe. A Cloud Service Composition Optimization Based on HNN [J]. Journal of System Simulation, 2019, 31(11): 2335-2343.
[8]	Zhang Tianrui, Qu Chuansheng, Wu Baoku, Xu Jianan. Modeling and Simulation of Complex Equipment Health Management System Based on Cloud Computing [J]. Journal of System Simulation, 2019, 31(11): 2356-2365.
[9]	Li Qiang, Liu Xiaofeng. Cloud Job Scheduling Model Based on Improved Plant Growth Algorithm [J]. Journal of System Simulation, 2018, 30(12): 4649-4658.
[10]	Guo Songhui, Li Qingbao, Sun Lei, Gong Xuerong, Yang Tianchi. Performance Modeling of Cryptographic Service System Virtualization Based on ISSM [J]. Journal of System Simulation, 2017, 29(8): 1692-1701.
[11]	Wan Cong, Wang Cuirong, Wang Cong. QoS-aware Scheduling for Data Intensive Workflow [J]. Journal of System Simulation, 2016, 28(3): 549-558.
[12]	Jiang Wuxue, Hu Xuanzi, Liu Minxia, Chen Yuqiang. Information Collaboration Model of Cloud Computing Supply Chain Based on Multi-Agent [J]. Journal of System Simulation, 2016, 28(1): 51-56.