@article{4791,
  author = {Hathairat Ketmaneechairat},
  title = {Analysis of DAG Structure and HEFT Scheduling Efficiency Across Graph Sets},
  journal = {Journal of Intelligent Computing},
  year = {2026},
  volume = {17},
  number = {3},
  doi = {https://doi.org/10.6025/jic/2026/17/3/141-170},
  url = {https://www.dline.info/jic/fulltext/v17n3/jicv17n3_3.pdf},
  abstract = {This study investigates the relationship between Directed Acyclic Graph (DAG) structural properties and
scheduling efficiency under the Heterogeneous Earliest Finish Time (HEFT) algorithm in heterogeneous
computing environments. Despite HEFT's widespread adoption as a benchmark scheduling heuristic,
systematic characterization of how graph topology influences its performance across diverse workload
regimes remains limited. Using a comprehensive benchmark of 300 DAG workflows spanning three complexity
classes (9, 23, and 29 tasks), we employ multivariate statistical techniques including Principal Component
Analysis, K-means clustering, hierarchical clustering, multiple regression, and Random Forest modeling to
identify latent structural dimensions governing execution behavior. Results reveal three dominant variance
components that explain 97.6% of the total variability: graph scale and computational complexity (PC1:
47.7%), communication intensity (PC2: 22.9%), and execution heterogeneity (PC3: 18.1%). Clustering analysis
validates three distinct workload regimes with strong statistical separation (Silhouette score = 0.612).
Critically, regression and feature importance analyses demonstrate that critical path length overwhelmingly
dominates execution time (importance = 0.974), while total workload and graph size contribute secondarily.
HEFT efficiency varies substantially across clusters, ranging from 0.771 (small graphs) to 0.408 (large
graphs), with communication heavy and deep dependency structures exhibiting significant performance
degradation. These findings support the development of Cluster Aware HEFT (CA-HEFT), an adaptive
scheduling architecture that pre classifies incoming workflows and applies tailored prioritization and
processor selection strategies. This research contributes an empirical taxonomy of DAG workloads, identifies
critical path as the principal performance bottleneck, and provides a foundation for structure aware, adaptive
scheduling in heterogeneous distributed systems.},
}