APPLYING AN IMPROVED FAST ANT SYSTEM TO DAG SCHEDULING FOR COMPUTATIONAL GRIDS

作者：Chiang Chuan Wen^*

来源：Journal of the Chinese Institute of Engineers, 2008, 31(7): 1113-1125.

DOI：10.1080/02533839.2008.9671467

• computational grids
• task matching and scheduling
• ant search techniques
• Globus toolkit

Computational grids have recently attracted considerable attention as cost-effective platforms for parallel processing. Generally a parallel program carried Out Oil such a platform can he characterized as a directed acyclic graph (DAG). To take full advantage of available resources in,rids and achieve hi( h computational performance, all effective DAG scheduling algorithm is indispensable. This study presents a novel constructive algorithm based oil the Fast Ant System (FANT). The proposed algorithm. namely. the Fast Ant System for Task Matching and Scheduling (FANT-TMS) algorithm. determines the scheduling order of all tasks in it parallel program and, then, allocates these tasks to appropriate processing elements in a computational grid, thereby minimizing total completion time of the parallel program. Performance of the FANT-TMS algorithm is demonstrated by comparison with a genetic algorithm (GA)-based scheduling technique ill terms of overall schedule length of randomly generated DAGs. Experimental results demonstrate that the proposed algorithm Outperforms file conventional GA-based approach. Additionally, a novel local search strategy is devised that further enhances solution quality obtained with the FANT-TMS algorithm.

• 出版日期2008