Journal Home > Volume 29 , Issue 3
Tsinghua Science and Technology 2024, 29(3): 806-817 https://doi.org/10.26599/TST.2023.9010058
Open Access | Issue | Published: 04 December 2023

Improved Double Deep Q Network-Based Task Scheduling Algorithm in Edge Computing for Makespan Optimization

Show Author's Information Lei Zeng1,L,  Qi Liu2,L,  Shigen Shen3( ),  Xiaodong Liu4
School of Computer Science, Nanjing University of Information Science and Technology, Nanjing 210044, China
School of Software, Nanjing University of Information Science and Technology, Nanjing 210044, China
School of Information Engineering, Huzhou University, Huzhou 313000, China
School of Computing, Edinburgh Napier University, Edinburgh, EH10 5DT, UK

Keywords:
edge computing, reinforcement learning, task scheduling, makespan, Double Deep Q Network (DQN)
Cite this article:
Zeng L, Liu Q, Shen S, et al. Improved Double Deep Q Network-Based Task Scheduling Algorithm in Edge Computing for Makespan Optimization. Tsinghua Science and Technology, 2024, 29(3): 806-817. https://doi.org/10.26599/TST.2023.9010058
Download citation
EndNote(RIS)
BibTeX

196

Views

29

Downloads

Citations

2

Crossref

1

WoS

0

Scopus

0

CSCD

Abstract Full text About this article

Edge computing nodes undertake an increasing number of tasks with the rise of business density. Therefore, how to efficiently allocate large-scale and dynamic workloads to edge computing resources has become a critical challenge. This study proposes an edge task scheduling approach based on an improved Double Deep Q Network (DQN), which is adopted to separate the calculations of target Q values and the selection of the action in two networks. A new reward function is designed, and a control unit is added to the experience replay unit of the agent. The management of experience data are also modified to fully utilize its value and improve learning efficiency. Reinforcement learning agents usually learn from an ignorant state, which is inefficient. As such, this study proposes a novel particle swarm optimization algorithm with an improved fitness function, which can generate optimal solutions for task scheduling. These optimized solutions are provided for the agent to pre-train network parameters to obtain a better cognition level. The proposed algorithm is compared with six other methods in simulation experiments. Results show that the proposed algorithm outperforms other benchmark methods regarding makespan.


menu
Abstract
Full text
Outline
About this article

Improved Double Deep Q Network-Based Task Scheduling Algorithm in Edge Computing for Makespan Optimization

Show Author's information Lei Zeng1,L, Qi Liu2,L, Shigen Shen3( ), Xiaodong Liu4
School of Computer Science, Nanjing University of Information Science and Technology, Nanjing 210044, China
School of Software, Nanjing University of Information Science and Technology, Nanjing 210044, China
School of Information Engineering, Huzhou University, Huzhou 313000, China
School of Computing, Edinburgh Napier University, Edinburgh, EH10 5DT, UK

Abstract

Edge computing nodes undertake an increasing number of tasks with the rise of business density. Therefore, how to efficiently allocate large-scale and dynamic workloads to edge computing resources has become a critical challenge. This study proposes an edge task scheduling approach based on an improved Double Deep Q Network (DQN), which is adopted to separate the calculations of target Q values and the selection of the action in two networks. A new reward function is designed, and a control unit is added to the experience replay unit of the agent. The management of experience data are also modified to fully utilize its value and improve learning efficiency. Reinforcement learning agents usually learn from an ignorant state, which is inefficient. As such, this study proposes a novel particle swarm optimization algorithm with an improved fitness function, which can generate optimal solutions for task scheduling. These optimized solutions are provided for the agent to pre-train network parameters to obtain a better cognition level. The proposed algorithm is compared with six other methods in simulation experiments. Results show that the proposed algorithm outperforms other benchmark methods regarding makespan.

Keywords: edge computing, reinforcement learning, task scheduling, makespan, Double Deep Q Network (DQN)

References(34)

[1]

X. Xu, H. Li, W. Xu, Z. Liu, L. Yao, and F. Dai, Artificial intelligence for edge service optimization in Internet of vehicles: A survey, Tsinghua Science and Technology, vol. 27, no. 2, pp. 270–287, 2021.
DOI Google Scholar
[2]

M. Laroui, B. Nour, H. Moungla, M. A. Cherif, H. Afifi, and M. Guizani, Edge and fog computing for IoT: A survey on current research activities & future directions, Comput. Commun., vol. 180, pp. 210–231, 2021.
DOI Google Scholar
[3]

X. Xu, H. Tian, X. Zhang, L. Qi, Q. He, and W. Dou, DisCOV: Distributed COVID-19 detection on X-ray images with edge-cloud collaboration, IEEE Trans. Serv. Comput., vol. 15, no. 3, pp. 1206–1219, 2022.
DOI Google Scholar
[4]

S. B. Slama, Prosumer in smart grids based on intelligent edge computing: A review on artificial intelligence scheduling techniques, Ain Shams Eng. J., vol. 13, no. 1, p. 101504, 2022.
DOI Google Scholar
[5]
H. Wang, L. Cai, X. Hao, J. Ren, and Y. Ma, ETS-TEE: An energy-efficient task scheduling strategy in a mobile trusted computing environment, Tsinghua Science and Technology, vol. 28, no. 1, pp. 105–116, 2022.
DOI
[6]

M. S. U. Islam, A. Kumar, and Y. C. Hu, Context-aware scheduling in fog computing: A survey, taxonomy, challenges and future directions, J. Netw. Comput. Appl., vol. 180, p. 103008, 2021.
DOI Google Scholar
[7]

X. Xu, Q. Jiang, P. Zhang, X. Cao, M. R. Khosravi, L. T. Alex, L. Qi, and W. Dou, Game theory for distributed IoV task offloading with fuzzy neural network in edge computing, IEEE Trans. Fuzzy Syst., vol. 30, no. 11, pp. 4593–4604, 2022.
DOI Google Scholar
[8]
X. Gao, D. Peng, G. Kui, J. Pan, X. Zuo, and F. Li. Reinforcement learning based optimization algorithm for maintenance tasks scheduling in coalbed methane gas field, Comput. Chem. Eng., vol. 170, p. 108131, 2023.
DOI
[9]
H. Tian, X. Xu, T. Lin, Y. Cheng, C. Qian, L. Ren, and M. Bilal, DIMA: Distributed cooperative microservice caching for Internet of Things in edge computing by deep reinforcement learning, World Wide Web, vol. 25, no. 5, pp. 1769–1792, 2022.
DOI
[10]

A. Jayanetti, S. Halgamuge, and R. Buyya, Deep reinforcement learning for energy and time optimized scheduling of precedence-constrained tasks in edge-cloud computing environments, Future Gener. Comput. Syst., vol. 137, pp. 14–30, 2022.
DOI Google Scholar
[11]
Z. Li, X. Xu, X. Cao, W. Liu, Y. Zhang, D. Chen, and H. Dai, Integrated CNN and federated learning for COVID-19 detection on chest X-ray images, IEEE/ACM Trans. Comput. Biol. Bioinform. doi: 10.1109/TCBB.2022.3184319.
DOI
[12]

S. Vemireddy and R. R. Rout, Fuzzy reinforcement learning for energy efficient task offloading in vehicular fog computing, Comput. Netw., vol. 199, p. 108463, 2021.
DOI Google Scholar
[13]

Z. Tang, W. Jia, X. Zhou, W. Yang, and Y. You, Representation and reinforcement learning for task scheduling in edge computing, IEEE Trans. Big Data, vol. 8, no. 3, pp. 795–808, 2022.
DOI Google Scholar
[14]
M. N. Tran and Y. Kim, A cloud QoS-driven scheduler based on deep reinforcement learning, in Proc. 2021 Int. Conf. Information and Communication Technology Convergence (ICTC), Jeju Island, Republic of Korea, 2021, pp. 1823–1825.
DOI
[15]
Z. Yang, M. Xiao, and Y. Ge, Dynamic resource scheduling of cloud-based automatic test system using reinforcement learning, in Proc. 2017 13th IEEE Int. Conf. Electronic Measurement & Instruments (ICEMI), Yangzhou, China, 2017, pp. 159–165.
[16]
D. Ding, X. Fan, Y. Zhao, K. Kang, Q. Yin, and J. Zeng, Q-learning based dynamic task scheduling for energy-efficient cloud computing, Future Gener. Comput. Syst., vol. 108, pp. 361–371, 2020.
[17]

H. Tian, X. Xu, L. Qi, X. Zhang, W. Dou, S. Yu, and Q. Ni, CoPace: Edge computation offloading and caching for self-driving with deep reinforcement learning, IEEE Trans. Veh. Technol., vol. 70, no. 12, pp. 13281–13293, 2021.
DOI Google Scholar
[18]

H. Che, Z. Bai, R. Zuo, and H. Li, A deep reinforcement learning approach to the optimization of data center task scheduling, Complexity, vol. 2020, p. 3046769, 2020.
DOI Google Scholar
[19]
Q. Liu, R. Mo, X. Xu, and X. Ma, Multi-objective resource allocation in mobile edge computing using PAES for Internet of Things, Wirel. Netw. doi: https://doi.org/10.1007/s11276-020-02409-w.
DOI
[20]

H. Xu, J. Zhou, W. Wei, and B. Cheng, Multiuser computation offloading for long-term sequential tasks in mobile edge computing environments, Tsinghua Science and Technology, vol. 28, no. 1, pp. 93–104, 2022.
DOI Google Scholar
[21]
T. Choudhari, M. Moh, and T. S. Moh, Prioritized task scheduling in fog computing, in Proc. ACMSE 2018 Conference, Richmond, Kentucky, 2018, pp. 1–8.
DOI
[22]

Q. Liu, X. Wu, X. Liu, Y. Zhang, and Y. Hu, Near-data prediction based speculative optimization in a distribution environment, Mob. Netw. Appl., vol. 27, no. 6, pp. 2339–2347, 2022.
DOI Google Scholar
[23]

W. Qi, Optimization of cloud computing task execution time and user QoS utility by improved particle swarm optimization, Microprocess. Microsyst., vol. 80, p. 103529, 2021.
DOI Google Scholar
[24]
B. Huang, W. Xia, Y. Zhang, J. Zhang, Q. Zou, F. Yan, and L. Shen, A task assignment algorithm based on particle swarm optimization and simulated annealing in ad-hoc mobile cloud, in Proc. 2017 9th Int. Conf. Wireless Communications and Signal Processing (WCSP), Nanjing, China, 2017, pp. 1–6.
DOI
[25]
J. Gao, Machine learning applications for data center optimization, Google White Paper, https://research.google/pubs/pub42542/, 2014.
DOI
[26]
B. Dab, N. Aitsaadi, and R. Langar, Q-learning algorithm for joint computation offloading and resource allocation in edge cloud, in Proc. 2019 IFIP/IEEE Symp. on Integrated Network and Service Management (IM), Arlington, VA, USA, 2019, pp. 45–52.
[27]

X. Zhao, G. Huang, L. Gao, M. Li, and Q. Gao, Low load DIDS task scheduling based on Q-learning in edge computing environment, J. Netw. Comput. Appl., vol. 188, p. 103095, 2021.
DOI Google Scholar
[28]
J. C. Guevara, R. da S Torres, L. F. Bittencourt, and N. L. S. da Fonseca, QoS-aware task scheduling based on reinforcement learning for the cloud-fog continuum, in Proc. GLOBECOM 2022-2022 IEEE Global Communications Conference, Rio de Janeiro, Brazil, 2022, pp. 2328–2333.
[29]
Y. Wei, L. Pan, S. Liu, L. Wu, and X. Meng, DRL-scheduling: An intelligent QoS-aware job scheduling framework for applications in clouds, IEEE Access, vol. 6, pp. 55112–55125, 2018.
DOI
[30]

T. Dong, F. Xue, C. Xiao, and J. Li, Task scheduling based on deep reinforcement learning in a cloud manufacturing environment, Concurr. Comput. Pract. Exp., vol. 32, no. 11, p. e5654, 2020.
DOI Google Scholar
[31]
J. Li, X. Zhang, J. Wei, Z. Ji, and Z. Wei, GARLSched: Generative adversarial deep reinforcement learning task scheduling optimization for large-scale high performance computing systems, Future Gener. Comput. Syst., vol. 135, pp. 259–269, 2022.
DOI
[32]

P. Gazori, D. Rahbari, and M. Nickray, Saving time and cost on the scheduling of fog-based IoT applications using deep reinforcement learning approach, Future Gener. Comput. Syst., vol. 110, pp. 1098–1115, 2020.
DOI Google Scholar
[33]

Q. Zhang, M. Lin, L. T. Yang, Z. Chen, S. U. Khan, and P. Li, A double deep Q-learning model for energy-efficient edge scheduling, IEEE Trans. Serv. Comput., vol. 12, no. 5, pp. 739–749, 2019.
DOI Google Scholar
[34]

S. Swarup, E. M. Shakshuki, and A. Yasar, Energy efficient task scheduling in fog environment using deep reinforcement learning approach, Procedia Comput. Sci., vol. 191, pp. 65–75, 2021.
DOI Google Scholar
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 10 February 2023
Revised: 25 April 2023
Accepted: 03 June 2023
Published: 04 December 2023
Issue date: June 2024

Copyright

© The Author(s) 2024.

Acknowledgements

Acknowledgment

This work was supported by the National Key Research and Development Program of China (No. 2021YFE0116900), National Natural Science Foundation of China (Nos. 42275157, 62002276, and 41975142), and Major Program of the National Social Science Fund of China (No. 17ZDA092).

Rights and permissions

The articles published in this open access journal are distributed under the terms of theCreative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).

Return