1-1hit |
Jiann-Fu LIN Win-Bin SEE Sao-Jie CHEN
This paper investigates the problem of scheduling parallel tasks" with consideration of communication cost on an m-processor system, where processors are assumed to be identical and tasks being scheduled are independent such that they can run on more than one processor simultaneously. Once a task is processed in parallel, its finish time will be speeded up, but communication cost will also be incurred and should be taken into account. To find a schedule with minimum finish time for the parallel tasks scheduling problem is NP-hard. Therefore, in this paper, we will propose a heuristic algorithm for this kind of problem and derive its performance bounds for two different cases of applications, respectively.