Task graph scheduling in multiprocessor systems using a coarse grained genetic algorithm

Effective scheduling is of great importance in parallel programming environments. The problem of tasks graph scheduling in a multi processor system can be stated as allocating tasks to processor of each computer. Scheduling problem is known as NP-Hard. Thereof, usage of evolutionary processing and especially genetic algorithms are effective for solving scheduling problems. The objective of this problem is minimizing Makespan and communication cost while maximizing CPU utilization. In this paper a new coarse-grain genetic algorithm for scheduling problem is presented so that the initial population divided into multi subpopulation toward for reduce solution search speed and to prevent early convergence by migration between subpopulations. Experimental results prove that the proposed method reduce the makespan and achieves a better scheduling in comparison with the existing approaches such as MCP and exist genetic algorithms.