Task Scheduling in Heterogeneous Multiprocessor Environments–An Efficient ACO-Based Approach

In heterogeneous computing environments, finding optimized solutions continues to be one of the most important and yet, very challenging problems. Task scheduling in such environments is NP-hard, so efficient mapping of tasks to the processors remains one of the most critical issues to be tackled. For several types of applications, the task scheduling problem is crucial, and across the literature, a number of algorithms with several different approaches have been proposed. One such effective approach is known as Ant Colony Optimization (ACO). This popular optimization technique is inspired by the capabilities of ant colonies to find the shortest paths between their nests and food sources. Consequently, we propose an ACO-based algorithm, called rACS, as a solution to the task scheduling problem. Our algorithm utilizes pheromone and a priority-based heuristic, known as the upward rank value, as well as an insertion-based policy and a pheromone aging mechanism to guide the ants to high quality solutions. To evaluate the performance of our algorithm, we compared our algorithm with the ACS algorithm and the ACO-TMS algorithm using randomly generated directed acyclic graphs (DAGs). The simulation results indicated that our algorithm experienced comparable or even better performance, than the selected algorithms