Greedy-Ant: Ant Colony System-Inspired Workflow Scheduling for Heterogeneous Computing

The last decades have seen a considerable progress on workflow scheduling in heterogeneous computing environments. However, existing methods still need to be improved on the performance in the makespan-based metrics. This paper proposes a novel workflow scheduling algorithm named Greedy-Ant to minimize total execution time of an application in heterogeneous environments. First, the ant colony system is applied to scheduling from a new standpoint by guiding ants to explore task priorities and simultaneously assign tasks to machines. Second, forward/backward dependence is defined to indicate the global significance of each node, based on which, a new heuristic factor is proposed to help ants search for task sequences. Finally, a greedy machine allocating strategy is presented. Experimental results demonstrate that Greedy-Ant outperforms the state of the art up to 18% in the metric of speedup.