Tasks Scheduling using Ant Colony Optimization

Abstract

Problem statement: Efficient scheduling of the tasks to heterogeneous processors for any application is critical in order to achieve high performance. Finding a feasible schedule for a given task set to a set of heterogeneous processors without exceeding the capacity of the processors, in general, is NP-Hard. Even if there are many conventional approaches available, people have been looking at unconventional approaches for solving this problem. This study uses a paradigm using Ant Colony Optimisation (ACO) for arriving at a schedule. Approach: An attempt is made to arrive at a feasible schedule of a task set on heterogeneous processors ensuring load balancing across the processors. The heterogeneity of the processors is modelled by assuming different utilisation times for the same task on different processors. ACO, a bio-inspired computing paradigm, is used for generating the schedule. Results: For a given instance of the problem, ten runs are conducted based on an ACO algorithm and the average wait time of all tasks is computed. Also the average utilisation of each processor is calculated. For the same instance, the two parameters: average wait time of tasks and utilisation of processors are computed using the First Come First Served (FCFS). The results are tabulated and compared and it is found that ACO performs better than the FCFS with respect to the wait time. Although the processor utilisation is more for some processors using FCFS algorithm, it is found that the load is better balanced among the processors in ACO. There is a marginal increase in the time for arriving at a schedule in ACO compared to FCFS algorithm. Conclusion: This approach to the tasks assignment problem using ACO performs better with respect to the two parameters used compared to the FCFS algorithm but the time taken to come up with the schedule using ACO is slightly more than that of FCFS.