Scheduling dynamic workflows onto clusters of clusters using postponing

In this article, we revisit the problem of scheduling dy-namically generated directed acyclic graphs (DAGs) of multi-processor tasks (M-tasks). A DAG is a ba-sic model for expressing workflows applications where each node represents a task of the workflow. We present a novel algorithm (DMHEFT) for scheduling dynami-cally generated DAGs onto a heterogeneous collection of clusters. The scheduling decisions are based on the predicted runtime of an M-task as well as the estima-tion of the redistribution costs between data-dependent tasks. The algorithm also takes care of unfavorable placements of M-tasks by considering the postponing of ready tasks even if idle processors are available. We evaluate the scheduling algorithm by comparing the re-sulting makespans to the results obtained by using other scheduling algorithms, such as RePA and MHEFT. 1