Research Article Open Access

Tasks Scheduling using Ant Colony Optimization

A. P. Shanthi1, G. Umarani Srikanth2, V. Uma Maheswari1 and Arul Siromoney1
  • 1 Anna University, India
  • 2 S.A. Engineering College, India

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.

Journal of Computer Science
Volume 8 No. 8, 2012, 1314-1320

DOI: https://doi.org/10.3844/jcssp.2012.1314.1320

Submitted On: 14 May 2012 Published On: 25 July 2012

How to Cite: Shanthi, A. P., Srikanth, G. U., Maheswari, V. U. & Siromoney, A. (2012). Tasks Scheduling using Ant Colony Optimization. Journal of Computer Science, 8(8), 1314-1320. https://doi.org/10.3844/jcssp.2012.1314.1320

  • 3,661 Views
  • 4,034 Downloads
  • 11 Citations

Download

Keywords

  • Ant Colony Optimisation (ACO)
  • First Come First Served (FCFS)
  • average utilisation
  • conventional approaches available
  • computational demands