Scheduling of random task graphs on parallel processors

Task graphs are one of the most used models for representing parallel computations. The structures of these graphs are sometimes obtained when compiling the parallel programs. In many other cases, however, they can be determined only at run time. In this paper, we study the scheduling of parallel computations whose task graphs are generated at run time. We obtain a simple optimal scheduling policy for the stochastic minimization of the running time of task graphs when these graphs are generated according to some specific statistical laws