Heterogeneous multiprocessor scheduling with differential evolution

The problem of scheduling a parallel program given by a directed acyclic graph (DAG) of tasks is a well-studied area. We present a new approach which employs differential evolution to numerically optimize the priorities of tasks. Our algorithm starts with a number of acceptable solutions, results of different heuristics, and merges them to achieve better one in a small number of function evaluations. The algorithm outperforms both a number of greedy heuristics and a classical genetic algorithm on the most of the program graphs considered in our experiments.