An Efficient ACO-Based Approach To Task Scheduling In Heterogeneous Computing Environments
Abstract- Heterogeneous computing environments have the potential to provide quality high performance computing. In order to maximize the potential of these systems, efficient mapping of tasks to the processors (task scheduling) remains one of the most important and challenging issues to consider. The task scheduling problem is critical for several applications, and across the literature, a number of algorithms with several different approaches have been proposed. One such approach has been the Ant Colony Optimization (ACO). This popular optimization technique is inspired by the capabilities of ant colonies to find the shortest path between their nests and food sources. In this paper, we present an ACO-based algorithm as a solution to the task scheduling problem, which utilizes both pheromone and priority-based heuristic information, along with an insertion policy to guide the ants to high quality solutions. Further, to minimize the issue of stagnation, we employ a pheromone aging mechanism to the artificial pheromone trails. We evaluate the performance of our algorithm by comparison with the ACS algorithm using randomly generated directed acyclic graphs (DAGs). Results indicate that our algorithm performs favorably and outperforms the ACS in the various experiments.
Keywords- Ant Colony Optimization, Task Scheduling, Directed Acyclic Graphs, Heterogeneous