TY - JOUR

T1 - Heterogeneous Computational Scheduling using Adaptive Neural Hyper-heuristic

AU - Аллахвердян, Александр Львович

AU - Жадан, Анастасия Юрьевна

AU - Кондратов, Иван Владимирович

AU - Петросян, Ованес Леонович

AU - Романовский, Алексей

AU - Харин, Виталий

AU - Ли, Инь

PY - 2025/3/22

Y1 - 2025/3/22

N2 - In heterogeneous computing environments, efficiently scheduling tasks, especially those forming Directed Acyclic Graphs (DAGs), is critical. This is particularly true for various Cloud and Edge computing tasks, as well as training Large Language Models (LLMs). This paper introduces a new scheduling approach using an Adaptive Neural Hyper-heuristic. By integrating a neural network trained with genetic algorithms, our method aims to minimize makespan. The approach uses a two-level algorithm: the first level prioritizes tasks using adaptive heuristic and the second level assigns resources based on the Earliest Finish Time (EFT) algorithm. Our tests show that this method significantly improves over traditional scheduling heuristics and other machine learning-based approaches. It reduces the makespan by 6.7% for small-scale DAGs and 28.49% for large-scale DAGs compared to the leading DONF algorithm. Additionally, it achieves a proximity of 84.08% to 96.43% to the optimal solutions found using Mixed-Integer Linear Programming (MILP), demonstrating its effectiveness in diverse computational settings.

AB - In heterogeneous computing environments, efficiently scheduling tasks, especially those forming Directed Acyclic Graphs (DAGs), is critical. This is particularly true for various Cloud and Edge computing tasks, as well as training Large Language Models (LLMs). This paper introduces a new scheduling approach using an Adaptive Neural Hyper-heuristic. By integrating a neural network trained with genetic algorithms, our method aims to minimize makespan. The approach uses a two-level algorithm: the first level prioritizes tasks using adaptive heuristic and the second level assigns resources based on the Earliest Finish Time (EFT) algorithm. Our tests show that this method significantly improves over traditional scheduling heuristics and other machine learning-based approaches. It reduces the makespan by 6.7% for small-scale DAGs and 28.49% for large-scale DAGs compared to the leading DONF algorithm. Additionally, it achieves a proximity of 84.08% to 96.43% to the optimal solutions found using Mixed-Integer Linear Programming (MILP), demonstrating its effectiveness in diverse computational settings.

KW - Directed Acyclic Graph

KW - Neural networks

KW - genetic algorithm

KW - scheduling

UR - https://link.springer.com/article/10.1134/S106456242460221X

UR - https://www.mendeley.com/catalogue/b23d0580-e243-3b42-99ca-e98f25806410/

U2 - 10.1134/S106456242460221X

DO - 10.1134/S106456242460221X

M3 - Article

VL - 110

SP - 151

EP - 161

JO - Doklady Mathematics

JF - Doklady Mathematics

SN - 1064-5624

IS - Suppl 1

ER -