An Efficient Low Delay Task Scheduling Algorithm Based on Ant Colony System in Heterogeneous Environments

Low delay is an important issue in a variety of applications on heterogeneous computing platforms. A great number of algorithms including heuristics as well as metaheuristics have been designed to minimize the completion time (i.e., makespan) of applications and achieved good results. However, the demand of high performance never stops. In this paper, we propose a new and efficient Ant-Colony based Low Delay Scheduling (ACLDS) algorithm to minimize the makespan of applications which can form directed acyclic graphs and are executed on a heterogeneous system. Simulated results show that our proposed algorithm is highly efficient in reducing makespan in comparison with state-of-the-art scheduling algorithms. For instance, the reduction ratio can be up to 15.2174% for a Fast Fourier Transform (FFT) benchmark.