2008 Volume E91.D Issue 10 Pages 2379-2385
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 machine 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.