Efficient local search for DAG scheduling

Scheduling DAGs to multiprocessors is one of the key issues in high-perform ance computing. Most realistic scheduling algorithms are heuristic and heur istic algorithms often have room for improvement. The quality of a scheduli ng algorithm can be effectively improved by a local search. In this paper, we present a fast local search algorithm based on topological ordering. Thi s is a compaction algorithm that can effectively reduce the schedule length produced by any DAG scheduling algorithm. Thus, it can improve the quality of existing DAG scheduling algorithms. This algorithm can quickly determin e the optimal search direction. Thus, it is of low complexity and extremely fast.