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

Task Scheduling is one of the most challenging problems in parallel and distributed computing. For static scheduling, the program to be parallelized is usually modeled as a Directed Acyclic Graph (DAG). In general, the scheduling of a DAG is a strong NP hard problem. The objective of this problem is minimizing the schedule length considering the communication costs. Genetic algorithm (GA) based technique have been proposed to search optimal solutions from entire solution space. The main shortcoming of 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 as local search is applied in the proposed memetic algorithm. Extended simulation results demonstrate that the proposed method outperforms the existing GA-based method, producing the optimal schedule