Scheduling Parallel Tasks with Communication Overhead in an Environment with Multiple Machines
Jiann-Fu Lin · IEICE Transactions on Information and Systems · 2008
This paper investigates the problem of nonpreemptively scheduling independent parallel tasks in an environment with multiple machines, which is motivated from the recent studies in scheduling tasks in a multi-machine environment.In this scheduling environment, each machiie contains a number of identical processors and each parallel task can simultaneously require a number of processors for its processing in any single machine.Whenever tasks are processed in parallel in a parallel machine , message communication among processors is often inevitable.The problem of finding a shortest schedule length on scheduling independent parallel tasks with the consideration of communication overhead in a multimachine environment is NP-hard.The aim of this paper is to propose a heuristic algorithm for this kind of problem and to analyze the performance bound of this heuristic algorithm.