Scheduling tasks with communication delays on parallel processors

LetP={v₁,...,v_n} be a set ofn jobs to be executed on a set ofm identical machines. In many instances of scheduling problems, if a jobv_i has to be executed before the jobv_j and both jobs are to be executed on different machines, some sort of information exchange has to take place between the machines executing them. The time it takes for this exchange of information is called a communication delay.In this paper we give anO(n) algorithm to find an optimal scheduling with communication delays when the number of machines is not limited and the precedence constraints on the jobs form a tree.