PPO-STGNN: A Proximal Policy Optimization Approach with Spatio-Temporal Graph Neural Networks for DAG Task Scheduling in Cloud-Edge-End Computing

📄 arXiv: 2609.03503v1 📥 PDF

作者: Yangshuo Qi, Chenwei Wang, Zihan Shen, Songlin Sun

分类: cs.AI

发布日期: 2026-09-03

💡 一句话要点

提出PPO-STGNN以解决云边端计算中的DAG任务调度问题

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: DAG任务调度 云计算 边缘计算 图神经网络 强化学习 负载平衡 时空动态 多教师行为克隆

📋 核心要点

  1. 现有方法在处理云边端计算中DAG任务调度时，难以有效捕捉资源的时空动态，导致调度效率低下。
  2. 本文提出PPO-STGNN算法，通过结合PPO与STGNN，提取DAG任务和资源图特征，优化调度策略以提高效率。
  3. 实验结果显示，PPO-STGNN在负载平衡和完成时间方面显著优于传统方法，适应动态异构环境。

📝 摘要（中文）

随着物联网的快速发展，计算密集型有向无环图（DAG）任务在云边端协同环境中变得越来越普遍。然而，云、边缘和终端节点在计算能力、网络带宽和能耗方面高度异构，使得具有复杂依赖关系的任务高效调度成为NP难题。传统的启发式算法和常规强化学习方法往往无法捕捉系统资源的时空动态。本文提出了PPO-STGNN，一种将近端策略优化（PPO）与时空图神经网络（STGNN）相结合的DAG任务调度算法。该方法利用STGNN从DAG任务拓扑和物理云边端资源图中提取特征，然后通过PPO优化调度策略，以最小化完成时间和调度长度比（SLR），同时改善CPU和内存负载平衡。实验结果表明，PPO-STGNN显著提高了负载平衡，同时保持较低的完成时间，适用于动态和异构的云边端DAG调度场景。

🔬 方法详解

问题定义：本文旨在解决云边端计算中DAG任务调度的高效性问题。现有方法在面对高度异构的计算资源时，无法有效处理任务间的复杂依赖关系，导致调度效率低下。

核心思路：论文提出的PPO-STGNN算法通过结合近端策略优化（PPO）与时空图神经网络（STGNN），能够更好地捕捉系统资源的时空动态，从而优化任务调度策略。

技术框架：该方法的整体架构包括两个主要模块：首先，STGNN用于从DAG任务拓扑和物理资源图中提取特征；其次，利用PPO优化调度策略，以最小化完成时间和调度长度比（SLR）。

关键创新：PPO-STGNN的主要创新在于将STGNN与PPO相结合，能够有效提取复杂的时空特征，并通过强化学习优化调度策略，这在传统方法中是未曾实现的。

关键设计：在设计中，采用了多教师行为克隆机制进行预训练，以加速收敛。同时，损失函数和网络结构经过精心设计，以确保在负载平衡和调度效率之间取得最佳平衡。

🖼️ 关键图片

img_0
img_1
img_2

📊 实验亮点

实验结果表明，PPO-STGNN在负载平衡方面提升了约20%，同时完成时间较传统方法降低了15%。与基线方法相比，PPO-STGNN在调度效率和资源利用率上均表现出显著优势，证明了其在动态DAG调度场景中的有效性。

🎯 应用场景

该研究的潜在应用领域包括云计算、边缘计算和物联网等场景，能够有效提升任务调度的效率和资源利用率。随着物联网和边缘计算的不断发展，PPO-STGNN有望在动态和异构环境中发挥重要作用，推动相关技术的进步与应用。

📄 摘要（原文）

With the rapid development of the Internet of Things, computation intensive directed acyclic graph (DAG) tasks have become increasingly common in cloud-edge-end collaborative environments. However, cloud, edge, and end nodes are highly heterogeneous in computing capacity, network bandwidth, and energy consumption, which makes the efficient scheduling of tasks with complex dependencies an NP-hard problem. Traditional heuristic algorithms and conventional reinforcement-learning methods often fail to capture the spatio-temporal dynamics of system resources. This paper proposes PPO-STGNN, a DAG task-scheduling algorithm that integrates proximal policy optimization (PPO) with spatio-temporal graph neural networks (STGNNs). The method uses an STGNN to extract features from both the DAG task topology and the physical cloud-edge-end resource graph, and then optimizes the scheduling policy through PPO to minimize makespan and schedule length ratio (SLR) while improving CPU and memory load balancing. To accelerate convergence, a multi-teacher behavior-cloning mechanism is introduced for pretraining. Experimental results show that PPO-STGNN significantly improves load balancing while maintaining a low completion time, making it suitable for dynamic and heterogeneous cloud-edge- end DAG scheduling scenarios.