HGT-PPO: A Hybrid Graph-Transformer Approach for Large-Scale DAG Task Scheduling in SAGIN

Abstract

Space–air–ground integrated network (SAGIN) provides a promising computing infrastructure for 6G applications, but scheduling large-scale directed acyclic graph (DAG) tasks in such networks remains challenging due to dynamic topology, heterogeneous resources, and complex intertask dependencies. This article investigates DAG task scheduling in SAGIN with the objective of minimizing the weighted cost of completion delay and energy consumption. To address the exponential action-space growth caused by large DAGs, we propose a dynamic task execution window (DTEW)-enabled hybrid graph-transformer (HGT)-proximal policy optimization (PPO) framework. DTEW dynamically constructs the executable task window at each decision epoch according to DAG dependency constraints and real-time resource feasibility, while incorporating bounded deferral and automatic retry strategies to improve scheduling flexibility and fault tolerance. Unlike prior graph neural network (GNN)-based schedulers that capture only explicit serial dependencies along DAG edges, the HGT-PPO architecture further models the latent contention structure among parallelizable subtasks within each execution window and the cross-domain alignment between task requirements and heterogeneous server capabilities, enabling a more comprehensive state representation for policy learning. Extensive experiments under varying DAG scales, server configurations, and network volatility conditions demonstrate that HGT-PPO consistently outperforms existing methods in total cost, task completion rate, and robustness.