A Genetic-Annealing Algorithm for Task Scheduling Based on Precedence Task Duplication

Task Scheduling is one of the most challenging NP-complete problems in parallel and distributed computing systems. In general scheduling algorithms with task duplication are of better performance than those without duplication, for fine grain tasks graphs and for networks with high communication latencies. The paper proposes a new genetic-annealing algorithm (GAA) based on task duplication, which achieves considerable performance improvement over two typical scheduling algorithms TDS and OSA. Based on task duplication, in GAA a simulated annealing algorithm is used to alleviate the selection pressure of the genetic algorithm, and enhance the global convergence of GAA. Compared with other known algorithms, GAA could find shorter scheduling length with the limited processors number, and without any restricted condition to task grain for a given system.