Solving the task scheduling problem using a parallel genetic algorithm implemented with GRADE

Abstract

In this paper, we present a task-scheduling heuristic, based on parallel genetic algorithm (PGA). The algorithm schedules parallel programs, represented as directed acyclic graphs (DAGs), onto multi-processor systems with dynamic interconnection networks (DINs) taking into account inter-processor communication cost, link contention and changes of inter-processor connections. The proposed solution combines two methods: list scheduling which is used for constructing schedules  and genetic algorithms which drives exploration of the search space for the list algorithm. The parallel genetic algorithm has been implemented on a cluster of workstations in the GRADE environment.