Task Scheduling Using Probabilistic Ant Colony Heuristics
Umarani Srikanth1, Uma Maheswari2, Shanthi Palaniswami3, and Arul Siromoney3
1Department of PG Studies in Engineering, S.A. Engineering College, India
2Department of Information Science and Technology, Anna University, India
3Department of Computer Science and Engineering, Anna University, India
Abstract: The problem of determining whether a set of tasks can be assigned to a set of heterogeneous processors in general is NP-hard. Generating an efficient schedule of tasks for a given application is critical for achieving high performance in a heterogeneous computing environment. This paper presents a novel algorithm based on Ant Colony Optimization (ACO) for the scheduling problem. An attempt is made to arrive at a feasible schedule for a task set on heterogeneous processors ensuring fair load balancing across the processors within a reasonable amount of time. Three parameters: Average waiting time of tasks, utilization of individual processors and the scheduling time of tasks are computed. The results are compared with those of the First Come First Served (FCFS) algorithm and it is found that ACO performs better than FCFS with respect to the waiting time and individual processor utilization. On comparison with the FCFS approach, the ACO method balances the load fairly among the different processors with the standard deviation of processors utilization being 88.7% less than that of FCFS. The average waiting time of the tasks is also found to be 34.3% less than that of the FCFS algorithm. However, there is a 35.5% increase in the scheduling time for the ACO algorithm.
Keywords: ACO, tasks scheduling problem, processor utilization, heterogeneous processors.
Received July 6, 2013; accepted September 19, 2013