A Randomized Heuristic for Stochastic Workflow Scheduling on Heterogeneous Systems

This paper focuses on the problem of scheduling a workflow onto a set of heterogeneous resources with stochastic model of task execution times and communication times. With understanding that deterministic scheduling heuristics can seldom perform well in such a stochastic model, we extend a well-known deterministic heuristic and propose a novel randomized scheduling approach. Extensive experiments have been carried out by simulation. The results show the proposed randomized approach significantly outperforms its deterministic counterpart and the extra overhead introduced is not only controllable but also acceptable.