On Resource Efficiency of Workflow Schedules

This paper presents the Maximum Effective Reduction (MER) algorithm, which optimizes the resource efficiency of a workflow schedule generated by any particular scheduling algorithm. The inefficiency in resource usage of workflow execution/schedule is not only in the number of resources used, but also the actual amount of “used” resource time, including idle time between any two task executions sourced from data dependencies. MER trades the minimal makespan increase for the maximal resource usage reduction by consolidating tasks with the exploitation of resource inefficiency in the original workflow schedule. Our evaluation using traces from four real-world scientific workflow applications shows that the rate of resource usage reduction far outweighs that of the increase in makespan, i.e., the number of resources used is halved on average while incurring an increase in makespan of less than 10%.