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 pe rformance. Finding a feasible schedule for a given task set to a set of heterogeneous processors without ex ceeding 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 assu ming 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 c onducted based on an ACO algorithm and the average wait time of all tasks is computed. Also th e average utilisation of each processor is calculat ed. For the same instance, the two parameters: average wait time of tasks and utilisation of processors ar e 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 bala nced among the processors in ACO. There is a marginal increase in the time for arriving at a schedule in AC O 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 sli ghtly more than that of FCFS.