Source-linked AI summary
PPO-STGNN: A Proximal Policy Optimization Approach with Spatio-Temporal Graph Neural Networks for DAG Task Scheduling in Cloud-Edge-End Computing
Yangshuo Qi, Chenwei Wang, Zihan Shen, Songlin Sun
TL;DR
Heterogeneous cloud-edge-end resources and changing network conditions make dependency-constrained DAG scheduling difficult, while existing methods may miss topology or temporal dynamics. PPO-STGNN combines spatio-temporal graph representations with PPO and behavior-cloning pretraining, and experiments report improved load balancing with low completion time.
Problem
Heterogeneous cloud-edge-end resources and dynamic network conditions make efficient DAG scheduling with complex dependencies an NP-hard problem, while existing methods may overlook topology or temporal changes.
Method
PPO-STGNN uses an STGNN to jointly encode DAG topology and evolving physical resources, then optimizes scheduling with PPO and multi-teacher behavior-cloning pretraining.
Results
PPO-STGNN achieves the best reported makespan and load balancing against listed traditional baselines, including LB 127.9 and makespan 124.8 s.
Takeaways & Limitations
The reported results support PPO-STGNN for dynamic cloud-edge-end scheduling where balanced resource use and low global completion time are both important.
Abstract
from arXiv · showhide
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.
1 Introduction
Cloud-edge-end DAG scheduling is difficult because resources and network conditions vary across heterogeneous layers, while task dependencies impose an NP-hard scheduling problem. PPO-STGNN addresses these limitations by combining spatio-temporal graph modeling with PPO and behavior-cloning pretraining.
- Problem setting: Cloud-edge-end environments combine heterogeneous computing, energy, and network conditions with DAG dependencies, making makespan minimization NP-hard.Cloud nodes offer high computational power but cross-layer latency, while terminal devices are energy-constrained and links fluctuate dynamically.
- Existing limitations: Traditional heuristics use static or greedy rules, while MLP-based reinforcement learning can lose DAG topology and many GNN methods overlook temporal resources and hierarchy.These limitations reduce adaptability to highly dynamic cloud-edge-end workloads.
- Proposed approach: PPO-STGNN jointly models DAG task topology and evolving physical resources to provide PPO with spatio-temporal features for task-node matching.The method constructs a heterogeneous scheduling model that includes computing, energy, topology, and link constraints.
- Training strategy: Multi-teacher behavior-cloning pretraining uses heuristic-generated expert trajectories to mitigate cold-start difficulties in large joint action spaces.The pretraining mechanism is introduced before reinforcement-learning optimization.
2 Scenario and System Model
The system models cloud, edge, and end devices as a hierarchical computing environment with distinct capabilities and communication constraints. DAG applications and three objectives—makespan, SLR, and load balancing—define the scheduling problem.
- Cloud-edge-end scenario: The physical scenario contains cloud servers, edge servers, and terminal devices arranged in a hierarchical topology.Cloud, edge, and end nodes form the system's layered physical structure.
- Node heterogeneity: End nodes are energy-sensitive and suited to lightweight tasks, edge nodes handle medium-complexity tasks, and cloud nodes process computation-intensive tasks.The layers differ in computing capacity and intended workload role.
- Network constraints: Communication links differ in bandwidth and latency, with end-to-end links having the lowest bandwidth and highest delay.Edge-to-cloud links offer relatively high bandwidth but incur cross-layer latency, while intra-domain edge links perform better.
- Task model: Applications are represented as DAGs whose nodes are subtasks and whose edges encode data dependencies, with execution time affected by current CPU availability.The model captures both workflow structure and time-varying resource conditions.
- Optimization objectives: The scheduling objectives are makespan, SLR, and load balancing across normalized CPU and memory loads.SLR compares actual completion time with optimal-node critical-path execution time, while load balancing sums CPU and memory-load variances.
3 Proposed PPO-STGNN Algorithm
PPO-STGNN formulates DAG scheduling as an end-to-end reinforcement-learning problem that jointly represents physical resources and task graphs. Its encoder combines spatial, temporal, and DAG-structural features, while constrained joint actions, composite rewards, and behavior-cloning pretraining support scheduling decisions.
- Framework: The proposed framework integrates STGNN and PPO to solve DAG scheduling as a Markov decision process.The workflow is designed as an end-to-end reinforcement-learning architecture.
- State representation: At each decision step, the state contains physical resource information and the logical task-graph state.The STGNN encoder extracts topological relationships from both parts of the state.
- Resource encoding: Resource features include CPU and memory idle rates, container pressure, and network throughput, with GAT modeling spatial connectivity.Attention weights are dynamically determined by link latency and bandwidth.
- DAG encoding: DAG features include task depth, in-degree, out-degree, and critical-path score, while GCN layers aggregate predecessor and successor information.The resulting DAG representation is combined with the resource representation before actor-critic processing.
- Actions and rewards: The action space jointly matches a task with a node, and a topological mask filters illegal hierarchical routes.The reward combines step-level response-time, transmission-cost, and load-balancing penalties with terminal makespan and SLR objectives.
- Training: Heuristic expert trajectories provide multi-teacher behavior-cloning pretraining before PPO fine-tuning with generalized advantage estimation.The clipped PPO objective is used to prevent policy collapse during online learning.
4 Experimental Setup and Result Analysis
The experiments compare PPO-STGNN with traditional schedulers and alternative reinforcement-learning architectures using makespan, SLR, load balancing, and training convergence. PPO-STGNN achieves strong load balancing and low completion time while modeling spatio-temporal graph information.
- Experimental design: The evaluation compares PPO-STGNN with FCFS, LeastLoad, HEFT, and Greedy under the same task set and resource configuration.It evaluates makespan, schedule length ratio (SLR), and resource load balance.
- Traditional baselines: PPO-STGNN achieves the best performance in makespan and load balancing against the traditional baseline algorithms.The comparison includes FCFS, LeastLoad, HEFT, and Greedy.
- Traditional baselines: 127.9 LB: PPO-STGNN reduces load balancing relative to FCFS (194.6), LeastLoad (174.4), and HEFT (162.5).The reported decreases are approximately 34.3%, 26.7%, and 21.3%, respectively.
- Traditional baselines: 124.8 s makespan: PPO-STGNN outperforms FCFS (153.0 s) and Greedy (130.5 s), while HEFT achieves the best SLR at 7.8 versus PPO-STGNN’s 11.6.The results describe PPO-STGNN as trading off global completion time and system resource loading rather than minimizing only a critical path.
- Reinforcement-learning frameworks: PPO-STGNN rapidly reaches stable convergence, maintaining makespan below 60 s and SLR around 15–20, whereas MLP-PPO stagnates near 110 s and SLR 40.PPO-StaticGNN improves over MLP-PPO but still exhibits noticeable training fluctuations.
- Reinforcement-learning frameworks: MLP-PPO’s low load variance comes from indiscriminately over-dispersing tasks and sacrificing global scheduling efficiency, unlike PPO-STGNN’s balanced trade-off.PPO-STGNN keeps dynamic load within a reasonable range while maintaining higher scheduling efficiency.
5 Conclusion
The paper proposes PPO-STGNN for dynamic cloud-edge-end DAG scheduling by modeling resources as a dynamic graph and workflows as DAGs. Its experiments show improved load balancing with competitive makespan performance in dynamically changing resource environments.
- Conclusion: PPO-STGNN models heterogeneous computing resources as a dynamic resource graph and workflow tasks as a DAG.It uses spatio-temporal graph representation learning to capture task-node matching features.
- Conclusion: Experimental results show that PPO-STGNN improves load balancing while maintaining competitive makespan performance in cloud-edge-end scenarios.The stated target setting includes dynamically changing resources.