Ant colony optimisation for task matching and scheduling

Ant colony optimisation for task matching and scheduling

For access to this article, please select a purchase option:

Buy article PDF
(plus tax if applicable)
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend to library

You must fill out fields marked with: *

Librarian details
Your details
Why are you recommending this title?
Select reason:
IEE Proceedings - Computers and Digital Techniques — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

PC clusters have recently received considerable interest as cost-effective parallel platforms for CPU-intensive applications. A cluster of PCs generally comprises of a collection of heterogeneous process elements (PEs). To make effective use of a PC cluster, a parallel program, which is characterised by a node- and edge-weighted directed acyclic graph (DAG), can usually be decomposed into a set of precedence-constrained atomic tasks such that PEs are able to accommodate these tasks and minimise the overall program-completion time. Consequently, techniques for task matching and scheduling become extremely important for effectively harnessing the computing power of the target cluster-based system. This work presents a constructive algorithm based on ant colony optimisation (ACO). The proposed algorithm, namely ACO-TMS, adopts a new state transition rule that reduces the time required when finding the satisfactory scheduling results. The proposed algorithm also integrates a local search procedure that proposed to help improve the scheduling results. The performance of this algorithm is demonstrated by comparing it against other existing algorithms, such as the genetic-algorithm-based scheduling method and the dynamic priority scheduling (DPS) heuristic, in terms of overall schedule length of randomly generated DAGs. Experimental results indicate that the proposed algorithm outperforms the genetic algorithm and the DPS heuristic algorithm for high communication to computation and heterogeneous computing environment.


    1. 1)
    2. 2)
    3. 3)
    4. 4)
    5. 5)
    6. 6)
    7. 7)
    8. 8)
      • L. Wang , H.J. Siegel , V.P. Roychowdhury , A.A. Maciejewski . Task matching and scheduling in heterogeneous computing environments using a genetic-algorithm-based approach. Parallel Distrib. Comput. , 1 , 8 - 22
    9. 9)
      • M. Dorigo , V. Maniezzo , A. Colorni . Ant system: optimization by a colony of cooperating agents. IEEE Trans. Syst. Man Cybern. B , 91 , 29 - 41
    10. 10)
      • T. Stuzle , H.H. Hoos . MAX-MIN ant system. Future Gener. Comput. Syst. , 8 , 889 - 914
    11. 11)
    12. 12)
      • V. Maniezzo , A. Carbonaro . An ants heuristic for the frequency assignment problem. Future Gener. Comput. Syst. , 9 , 927 - 935
    13. 13)
    14. 14)
      • Bank, M., Honig, U., Schiffmann, W.: `An ACO-based approach for scheduling task graphs with communication costs', Proc. Int. Conf. on Parallel Processing (ICPP'05), 2005, p. 623–629.
    15. 15)
      • N.J.A. Sloane . A library of orthogonal arrays.
    16. 16)
      • M. AI-Mouhamed , H. Najjari . Adaptive scheduling of computations and communications on distributed-memory systems. Parallel Distrib. Comput. , 6 , 716 - 740
    17. 17)
      • M.Y. Wu , W. Shu , J. Gu . Efficient local search for DAG scheduling. IEEE Trans. Parallel Distrib. Syst. , 6 , 617 - 627

Related content

This is a required field
Please enter a valid email address