An Experimental Investigation into the Approximation Weight Function of a Stochastic List Scheduling Algorithm

This paper considers scheduling tasks of a stochastic workflow, represented by a directed acyclic graph with random weight of nodes and edges, onto a bounded number of heterogeneous machines. We focus on seeking for an appropriate way to approximate the random weight of the nodes and edges of the graph when scheduling. Different schemes for computing these approximation weights are evaluated by simulation experiments. Our findings indicate that the performance of the schedule produced may be significantly affected by the scheme used, and suggest that computing the approximation weight by simply summing up the expectation and standard variation may not be a particular good choice.