A path relinking enhanced estimation of distribution algorithm for direct acyclic graph task scheduling problem

Superior task scheduling scheme is able to improve the performance in achieving shorter task completion time in multi-processor computing system. Large scale applications are generally modelled as direct acyclic graph (DAG) to be processed efficiently in parallel. To solve DAG task scheduling problem (DAG-SP) with the criterion of minimizing makespan, this paper proposes an estimation of distribution algorithm (EDA) enhanced by the path relinking. An efficient hybrid scheme integrating list scheduling heuristics is designed to take advantage of the knowledge of existing works. In addition, to describe the relative position relationships between the task pairs, a specific probability model is built and the task processing permutations are produced by sampling such a model. To enhance the exploitation of EDA, a path relinking based knowledge is used to design the local search method. Simulation experiments are carried out with both benchmark datasets and real-world graphs, where the comparative results show that the above designs can improve the performance effectively. Moreover, the numerical comparisons show that the proposed algorithm performs significantly better than the existing heuristics and evolutionary algorithms. (C) 2021 Elsevier B.V. All rights reserved.

Automated summary

This paper proposes a task scheduling scheme based on EDA and path relinking, which can effectively improve the performance of task completion time in multi-processor computing systems. By establishing probability models and designing local search methods, the relative position relationships between tasks can be described and the utilization of the algorithm can be improved.