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

Abstract 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.