Applying heuristics using scanning of communication term and elimination of ineffective commu-nication overhead to Task Scheduling

Task scheduling is one of core technologies to improve the efficiency of parallel processing. A schedule is a solution of task scheduling problem, and make to cooperate the performance of parallel machines. The shorter length of schedule (makespan) is reduced, the more efficient parallel machines run. But, task scheduling problem is combinatorial optimization problem that has strongly NP hard computational complexity. Accordingly, it is necessary that to design algorithm taking account of more unforeseeable disposition in order to reduce makespan. Concerning to solve the problem, the disposition is considered with communication overhead between machines. In this paper, the authors propose new heuristic algorithms to optimize communication overhead. These are applied the focus to critical path of dependences and earliest allocation pattern of communications. The authors describe characteristics and processes of these algorithms, and our experiments show the effectiveness of the