Abstract

This paper presents Memetic algorithm with Tabu search as local search for solving Task scheduling problem considering communication cost. This problem consists of finding a schedule for a general task graph to be executed on a cluster of workstations and hence the schedule length can be minimized. The task scheduling problem known to be NP-hard, and to obtain optimal and suboptimal solutions, several heuristic based algorithms have been developed in the past. Our approach combines local search (by self experience) and global search (by neighboring experience) possessing high search efficiency. The proposed approach is compared with another memetic algorithm where Hill Climbing algorithm as local search. The numerical results clearly indicate that our proposed approach produces solutions which are closer to optimality and/or better quality than the existing list scheduling heuristics.

Paper Details