A polynomial algorithm to optimally schedule tasks on a virtual distributed system under tree-like precedence constraints (Q582203)

Considered is a computer system with an unbounded number of independent interchangeable processors with independent memory. The paper deals with a job scheduling problem in which the jobs are depending from each other through a tree-like structure. This means that any ``root'' job cannot be performed before all ``branch'' jobs have been performed. In this situation the jobs running on different processors must communicate with each other because of the independent memory. We assume that the maximum communication time is less than the minimum task processing time. In this case the paper gives a polynomial algorithm for the optimal job scheduling problem.