A Structure-Aware Hybrid Scheduling Framework for Mixed-Dependency Workflow Scheduling in V2X Testing

Abstract

Efficient workflow scheduling is essential for improving testing efficiency in large-scale Vehicle-to-Everything (V2X) protocol conformance testing. Existing directed acyclic graph (DAG) schedulers treat all test components uniformly, overlooking the inherent structural heterogeneity of V2X workflows which contain mixed independent and precedence-constrained components. This leads to cross-subsystem interference, low resource utilization, and extended makespan. This paper presents AOE–CP (AON DAG with Edge-Weighted Transformation and Critical Path Scheduling), a structure-aware hybrid scheduling architecture for V2X testing. Unlike existing heuristic-based improvements, AOE–CP achieves performance gains through domain-specific structural reorganization rather than new scheduling rules. It integrates three mechanisms: (i) structural decomposition to decouple independent and dependent components and resolve their conflicting optimization objectives; (ii) critical path thread isolation to eliminate cross-subsystem resource competition and guarantee zero critical path waiting time for V2X dominant-topology workflows; (iii) atomic operation-based time estimation supporting fully offline scheduling without runtime profiling overhead. Experiments show that, for large-scale workflow scenarios, AOE–CP reduces normalized makespan by 14–16% and 22–24% compared with HEFT (Heterogeneous Earliest Finish Time) and CPOP (Critical Path On Processor), respectively. Scheduling overhead is only 2.1 ms for 1000-component workflows. AOE-CP reaches makespan saturation with four threads, versus 12 for HEFT and 28 for CPOP, demonstrating superior resource efficiency and scalability. The framework can also be generalized to other mixed-dependency workflow scenarios.