A Memetic Algorithm Based Task Scheduling considering Communication Cost on Cluster of Workstations

Task Scheduling is one of the most challenging problems inparallel and distributed computing. For static scheduling, theprogram to be parallelized is usually modeled as a Directed AcyclicGraph (DAG). In general, the scheduling of a DAG is a strong NPhard problem. The objective of this problem is minimizing theschedule length considering the communication costs. Geneticalgorithm (GA) based technique have been proposed to searchoptimal solutions from entire solution space. The main shortcomingof this approach is to spend much time doing scheduling and hence, needs exhaustive time. This paper proposes a Memetic Algorithm (MA) to overcome with this shortcoming. Hill Climbing algorithm aslocal search is applied in the proposed memetic algorithm. Extendedsimulation results demonstrate that the proposed methodoutperforms the existing GA-based method, producing the optimalschedule