Complexity-Aware Hybrid Graph Scheduling with Selective Refinement for Heterogeneous DAG Workloads

Hybrid graph schedulers can improve the ordering of dependent tasks, but their inference and repeated list-scheduling costs are rarely allocated according to workload difficulty. This paper presents CAHG-SR, a complexity-aware scheduler that combines a bidirectional edge-conditioned graph attention encoder with heterogeneous earliest-finish-time list scheduling and a validation-calibrated search budget. The graph encoder implements edge-aware attention and two-direction residual message aggregation; its scores perturb an analytically ranked baseline to construct alternative feasible schedules. A deterministic gate selects one, five, or nine candidates from structural workload features, retaining the HEFT solution as a quality safeguard. On 132 independently generated heterogeneous DAGs, the proposed policy obtains a mean makespan ratio of 0.9717 against HEFT (2.83% lower; paired bootstrap 95% CI of the difference: [−0.0361, −0.0210]), while using a median 9.79 ms of CPU scheduling time versus 17.38 ms for unrestricted nine-candidate graph refinement. Matched-budget graph removal increases the ratio to 0.9839. A fixed-budget random gate yields mean ratio 0.9767, while an OCT-based PEFT baseline obtains 1.0205 under the original distribution. Two frozen-model cost-shift evaluations reveal both additional gains and regimes where PEFT is stronger. All results use synthetic DAGs and CPU-based offline scheduling, without claims of online cluster deployment.