Deterministic latency DAG task scheduling algorithm based on NCSAC for mobile edge networks

Abstract

Task scheduling of directed acyclic graph (DAG) based applications in edge computing faces challenges from dynamic task variations and lack of deterministic latency guarantees, while traditional algorithms perform poorly in latency, energy consumption and resource utilization, making them unable to meet the requirements of latency-sensitive applications. To address this issue, this paper proposes the network calculus soft actor-critic (NCSAC) algorithm, which integrates network calculus with the soft actor-critic (SAC) algorithm for DAG task scheduling. NCSAC formulates the DAG scheduling problem as a Markov decision process (MDP) and constructs a joint model of task dependency graphs and edge node networks, using dual graph convolutional networks (DGCNs) to extract deep features. It embeds network calculus into the policy network loss function with a delay penalty to prioritize latency-constrained scheduling policies, and employs SAC's maximum entropy framework, soft update and experience replay to balance exploration and exploitation for stable training. A multi-objective optimization objective is designed to optimize delay deviation and network traffic cost simultaneously. Comparative experiments are conducted with network-calculus-based proximal policy optimization (NCPPO), SAC, min-min scheduling algorithm and heterogeneous earliest finish time (HEFT) algorithm. Results demonstrate that NCSAC achieves low and steadily increasing total latency deviation and worst-case latency under dynamic DAG tasks and edge nodes, reduces network cost by 15.4% - 48.0% on average, and exhibits superior latency determinism, cost efficiency and robustness.

Keywords

edge computing / task scheduling / soft actor-critic (SAC) / network calculus

References

[1] ZHU J, WANG S W . QoS-guaranteed resource allocation in mobile communications: A stochastic network calculus approach. IEEE/ACM Transactions on Networking, 2024, 32(6): 5159-5171.

[2] WU W P, LIN Z D, WANG C, et al. Research on dynamic task scheduling methods based on edge computing. Technology Innovation and Application, 2025, 15(19): 52-55. (in Chinese)

[3] ZHANG X L, YANG L, YAO J M, et al. Deterministic transmission method for heterogeneous industrial Internet of things based on time-sensitive technology. Information and Control, 2025, 54(3): 488-501. (in Chinese)

[4] CAI C X . Cloud computing task scheduling algorithm based on repeated heterogeneous earliest finish time. Journal of Southwest China Normal University (Natural Science Edition), 2020, 45(5): 141-147. (in Chinese)

[5] MAO L H, DENG Q, LIU R N, et al. CPM-GA for multi-satellite and multi-task simulation scheduling. Journal of System Simulation, 2021, 33(1): 205-214. (in Chinese)

[6] SELIEM M, ZAHRAN A, PESCH D. Delay analysis of redundant TSN-based industrial networks using network calculus. Proceedings of the IEEE 29th International Symposium on Local and Metropolitan Area Networks (LANMAN'23), 2023, Jul 10-11, London, UK. Piscataway, NJ, USA: IEEE, 2023: 3p.

[7] LIU Z Q, LI K, WANG Y, et al. Mixed traffic scheduling with latency and jitter analysis in URLLC industrial automation. IEEE Internet of Things Journal, 2025, 12(12): 18820-18835.

[8] GARCÍA A. Greedy algorithms: A review and open problems. Journal of Inequalities and Applications, 2025: Article 11.

[9] DANG Y K, REN Y M . Solving the economic dispatch problem of power systems based on multi-population genetic algorithm. Open Access Library Journal, 2024, 11: Article e12522.

[10] LI C, LI J B, DING C C, et al. DRL-based edge monitoring task offloading and resource allocation algorithm. Journal of System Simulation, 2024, 36(9): 2113-2126. (in Chinese)

[11] TIAN Q, WU F . A survey of communication-based cooperative multi-agent reinforcement learning algorithms. Aerospace Control, 2023, 41(4): 13-19. (in Chinese)

[12] HAN L, ZHU S J, ZHAO H Y, et al. An enhanced whale optimization algorithm for task scheduling in edge computing environments. Frontiers in Big Data, 2024, 7: DOI: 10.3389/fdata.2024.1422546.

[13] YANG S J, ZHUANG L, ZHANG J H, et al. A multipolicy deep reinforcement learning approach for multiobjective joint routing and scheduling in deterministic networks. IEEE Internet of Things Journal, 2024, 11(10): 17402-17418.

[14] LI J C, ZHOU F Q, LI W J, et al. Componentized task scheduling in cloud-edge cooperative scenarios based on GNN-enhanced DRL. Proceedings of the 2023 IEEE/IFIP Network Operations and Management Symposium (NOMS'23), 2023, May 8-12, Miami, FL, USA. Piscataway, NJ, USA: IEEE, 2023: 4p.

[15] LI H Y, CHE X R . DRL-based edge computing model to offload the FIFA World Cup traffic. Mobile Information Systems, 2020: DOI: 10.1155/2020/8825643.

[16] YANG S, ZHANG L M, CUI L Z, et al. RLCS: Towards a robust and efficient mobile edge computing resource scheduling and task offloading system based on graph neural network. Computer Communications, 2023, 206: 38-50.

[17] DUAN Y F, LI J C, SUN H, et al. Telemetry-aided cooperative multi-agent online reinforcement learning for DAG task scheduling in computing power networks. Simulation Modelling Practice and Theory, 2024, 132: DOI: 10.1016/j.simpat.2023.102885.

[18] GAO J, ZHOU F Q, DONG M X, et al. Optimal latency and energy-aware task scheduling in in-network computing paradigm: A deep reinforcement learning approach. IEEE Transactions on Sustainable Computing, 2025, 10(4): 690-704.

[19] GEYER F, SCHEFFLER A, BONDORF S. Network calculus with flow prolongation: A feedforward FIFO analysis enabled by ML. IEEE Transactions on Computers, 2023, 72(1): 97-110.

[20] CUI P, CUI P, HAN S J, et al. End-to-end delay performance analysis of industrial internet of things: A stochastic network calculus perspective. IEEE Internet of Things Journal, 2024, 11(3): 5374-5387.

[21] MOHAMMADPOUR E, STAI E, LE BOUDEC J Y . Improved network-calculus nodal delay-bounds in time-sensitive networks. IEEE/ACM Transactions on Networking, 2023, 31(6): 2902-2917.

[22] ISLAM M A, STEA G . Estimating bandwidth and analyzing worst-case delay bounds using network calculus. IEEE Access, 2025, 13: 92227-92241.

[23] LI Z D. Performance study of energy harvesting communication systems based on network calculus. Master Thesis. Beijing, China: Beijing University of Posts and Telecommunications, 2018 (in Chinese).

[24] GAO Y H, ZHANG X, YANG H W . Network calculus theory and application: A new graduate course for engineering students. Journal of Educational Research Progress, 2024, 4(1): 23-31.

[25] ZHU W W, DENG X H, GUI J S, et al. Cost-effective task offloading and resource scheduling for mobile edge computing in 6G space-air-ground integrated network. IEEE Internet of Things Journal, 2025, 12(12): 19428-19442.

[26] SADASIVAN A, GANANATHAN K, JOE DHANITH P R, et al. A systematic survey of graph convolutional networks for artificial intelligence applications. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 2025, 15(2): Article e70012.

[27] JAMSHIDI S, NIKANJAM A, NAFI K W, et al. Application of deep reinforcement learning for intrusion detection in internet of things: A systematic review. Internet of Things, 2025, 31: Article 101531.

[28] ABBASOVA S, KARIMOVA M. Deep reinforcement learning models for traffic flow optimization in SDN architectures. Luminis Applied Science and Engineering, 2025, 2(2): 55-63.

[29] JAYANETTI A, HALGAMUGE S, BUYYA R . Deep reinforcement learning for energy and time optimized scheduling of precedence-constrained tasks in edge: Cloud computing environments. Future Generation Computer Systems, 2022, 137: 14-30.

[30] ZHOU X K, LIANG W, YAN K, et al. Edge-enabled two-stage scheduling based on deep reinforcement learning for internet of everything. IEEE Internet of Things Journal, 2023, 10(4): 3295-3304.