Complexity-Aware Hybrid Graph Scheduling with Selective Refinement for Heterogeneous DAG Workloads
DOI:
https://doi.org/10.54097/3mtddd95Keywords:
Heterogeneous scheduling, directed acyclic graphs, graph attention, complexity-aware optimization, makespan, reproducible simulationAbstract
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.
Downloads
References
[1] Dean, J., & Ghemawat, S. (2008). MapReduce: Simplified data processing on large clusters. Communications of the ACM, 51(1), 107–113. https://doi.org/10.1145/1327452.1327492
[2] Zaharia, M., Xin, R. S., Wendell, P., Das, T., Armbrust, M., Dave, A., Meng, X., Rosen, J., Venkataraman, S., Franklin, M. J., Ghodsi, A., Gonzalez, J. E., Shenker, S., & Stoica, I. (2016). Apache Spark: A unified engine for big data processing. Communications of the ACM, 59(11), 56–65. https://doi.org/10.1145/2934664
[3] Chen, J., Han, X., Zhang, X., & Yang, Y. (2023). Exact concept-level explanations for early detection of financial misstatements. Eurasia Journal of Science and Technology, 5(2), 34–48.
[4] Hindman, B., Konwinski, A., Zaharia, M., Ghodsi, A., Joseph, A. D., Katz, R. H., Shenker, S., & Stoica, I. (2011). Mesos: A platform for fine-grained resource sharing in the data center. In Proceedings of the USENIX Symposium on Networked Systems Design and Implementation (pp. 295–308).
[5] Ghodsi, A., Zaharia, M., Hindman, B., Konwinski, A., Shenker, S., & Stoica, I. (2011). Dominant resource fairness: Fair allocation of multiple resource types. In Proceedings of the USENIX Symposium on Networked Systems Design and Implementation (pp. 323–336).
[6] Topcuoglu, H., Hariri, S., & Wu, M. Y. (2002). Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Transactions on Parallel and Distributed Systems, 13(3), 260–274. https://doi.org/10.1109/71.993206
[7] Teng, D. (2025). RSRBench: Reproducibility and performance benchmarking for regional seismic risk workflows. Academic Journal of Architecture and Civil Engineering, 3(1), 40–52.
[8] Yang, S., Ding, G., Chen, Z., & Yang, J. S. (2025). GART: Graph neural network-based adaptive and robust task scheduler for heterogeneous distributed computing. IEEE Access, 13, 200196–200216. https://doi.org/10.1109/ACCESS.2025.3633290
[9] Mao, H., Schwarzkopf, M., Venkatakrishnan, S. B., Meng, Z., & Alizadeh, M. (2019). Learning scheduling algorithms for data processing clusters. In Proceedings of the ACM SIGCOMM Conference (pp. 270–288). https://doi.org/10.1145/3341302.3342080
[10] Grandl, R., Kandula, S., Rao, S., Akella, A., & Kulkarni, J. (2016). GRAPHENE: Packing and dependency-aware scheduling for data-parallel clusters. In Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (pp. 81–97).
[11] Tumanov, A., Zhu, T., Park, J. W., Kozuch, M. A., Harchol-Balter, M., & Ganger, G. R. (2016). TetriSched: Global rescheduling with adaptive plan-ahead in dynamic heterogeneous clusters. In Proceedings of the EuroSys Conference (Article 35, pp. 1–16). https://doi.org/10.1145/2901318.2901355
[12] Delimitrou, C., & Kozyrakis, C. (2014). Quasar: Resource-efficient and QoS-aware cluster management. In Proceedings of the International Conference on Architectural Support for Programming Languages and Operating Systems (pp. 127–144). https://doi.org/10.1145/2541940.2541941
[13] Delimitrou, C., & Kozyrakis, C. (2013). Paragon: QoS-aware scheduling for heterogeneous datacenters. In Proceedings of the International Conference on Architectural Support for Programming Languages and Operating Systems (pp. 77–88). https://doi.org/10.1145/2451116.2451125
[14] Schwarzkopf, M., Konwinski, A., Abd-El-Malek, M., & Wilkes, J. (2013). Omega: Flexible, scalable schedulers for large compute clusters. In Proceedings of the EuroSys Conference (pp. 351–364). https://doi.org/10.1145/2465351.2465386
[15] Mao, H., Alizadeh, M., Menache, I., & Kandula, S. (2016). Resource management with deep reinforcement learning. In Proceedings of the ACM Workshop on Hot Topics in Networks (pp. 50–56). https://doi.org/10.1145/3005745.3005750
[16] Ousterhout, K., Wendell, P., Zaharia, M., & Stoica, I. (2013). Sparrow: Distributed, low latency scheduling. In Proceedings of the ACM Symposium on Operating Systems Principles (pp. 69–84). https://doi.org/10.1145/2517349.2522716
[17] Kipf, T. N., & Welling, M. (2017). Semi-supervised classification with graph convolutional networks. In Proceedings of the International Conference on Learning Representations. https://doi.org/10.48550/arXiv.1609.02907
[18] Wang, J., Ge, Y., Liu, J., & Jiang, B. (2024). Early warning of liquidity stress in U.S. banks with seasonally aligned frailty hazards and delayed-feedback conformal alarms. Journal of Trends in Finance and Economics, 1(1), 85–100.
[19] Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., & Bengio, Y. (2018). Graph attention networks. In Proceedings of the International Conference on Learning Representations. https://doi.org/10.48550/arXiv.1710.10903
[20] Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., & Dahl, G. E. (2017). Neural message passing for quantum chemistry. In Proceedings of the International Conference on Machine Learning (Vol. 70, pp. 1263–1272). PMLR.
[21] Battaglia, P. W., Hamrick, J. B., Bapst, V., Sanchez-Gonzalez, A., Zambaldi, V., Malinowski, M., Tacchetti, A., Raposo, D., Santoro, A., Faulkner, R., Gulcehre, C., Song, F., Ballard, A., Gilmer, J., Dahl, G., Vaswani, A., Allen, K., Nash, C., Langston, V., … Pascanu, R. (2018). Relational inductive biases, deep learning, and graph networks. https://doi.org/10.48550/arXiv.1806.01261
[22] Zhou, F. (2026). Moment-constrained side-force allocation for wind-assisted merchant ships: Hydrodynamic performance of retractable anti-leeway fins and flap rudders. Innovation and Technology Studies, 3(1), 27–41.
[23] Cheng, Y., Chai, Z., & Anwar, A. (2018). Characterizing co-located datacenter workloads: An Alibaba case study. In Proceedings of the Asia-Pacific Systems Conference (Article 12). https://doi.org/10.1145/3265723.3265742
[24] Zheng, W., & Sakellariou, R. (2013). Stochastic DAG scheduling using a Monte Carlo approach. Journal of Parallel and Distributed Computing, 73(12), 1673–1689. https://doi.org/10.1016/j.jpdc.2013.07.019
[25] Calheiros, R. N., Ranjan, R., Beloglazov, A., De Rose, C. A. F., & Buyya, R. (2011). CloudSim: A toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms. Software: Practice and Experience, 41(1), 23–50. https://doi.org/10.1002/spe.995
[26] Zhang, F., Shen, A., & Huang, S. (2026). TRIAD: Co-designing mixed-precision quantization, operator fusion, and on-chip memory reuse for real-time vision–language–action inference on automotive NPUs. Results in Engineering. https://doi.org/10.1016/j.rineng.2026.113673
[27] Teng, D., Shang, W., Zhang, F., Chen, T., & Ding, J. (2026). SW-SpeedDLM: Sliding Window Speculative Decoding for Diffusion Language Models Under Long Context Constraints. Mathematics, 14, 2137. https://doi.org/10.3390/math14122137
Downloads
Published
Issue
Section
License
Copyright (c) 2026 Academic Journal of Applied Sciences
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
