|Table of Contents|

[1] Qi Chao, Zhang Jing, Li Junhuai, et al. ACS-based resource assignment and task scheduling in grid [J]. Journal of Southeast University (English Edition), 2007, 23 (3): 451-454. [doi:10.3969/j.issn.1003-7985.2007.03.031]
Copy

ACS-based resource assignment and task scheduling in grid()
基于蚁群系统的网格资源分配与任务调度
Share：

Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]

Volumn:
23
Issue:
2007 3
Page:
451-454
Research Field:
Computer Science and Engineering
Publishing date:
2007-09-30

Info

Title:
ACS-based resource assignment and task scheduling in grid
基于蚁群系统的网格资源分配与任务调度
Author(s):
Qi Chao1, 2, Zhang Jing1, Li Junhuai1
1School of Computer Science and Engineering, Xi’an University of Technology, Xi’an 710048, China
2 School of Computer Science, Shaanxi Normal University, Xi’an 710062, China
祁超1, 2, 张璟1, 李军怀1
1西安理工大学计算机科学与工程学院, 西安 710048; 2陕西师范大学计算机科学学院, 西安 710062
Keywords:
grid;  resource assignment;  task scheduling;  ant colony system(ACS);  task resource assignment graph(TRAG);  semaphore
网格;  资源分配;  任务调度;  蚁群系统;  任务资源分配图;  信号量
PACS:
TP393
DOI:
10.3969/j.issn.1003-7985.2007.03.031
Abstract:
To solve the deadlock problem of tasks that the interdependence between tasks fails to consider during the course of resource assignment and task scheduling based on the heuristics algorithm, an improved ant colony system(ACS)based algorithm is proposed.First, how to map the resource assignment and task scheduling(RATS)problem into the optimization selection problem of task resource assignment graph(TRAG)and to add the semaphore mechanism in the optimal TRAG to solve deadlocks are explained.Secondly, how to utilize the grid pheromone system model to realize the algorithm based on ACS is explicated. This refers to the construction of TRAG by the random selection of appropriate resources for each task by the user agent and the optimization of TRAG through the positive feedback and distributed parallel computing mechanism of the ACS.Simulation results show that the proposed algorithm is effective and efficient in solving the deadlock problem.
为了解决基于启发式算法的资源分配和任务调度过程中由于没有考虑任务间的相互依赖关系而出现的任务死锁问题, 提出了一种基于蚁群系统的改进算法.首先阐述了如何将分配调度问题映射到任务资源分配图的优化选择问题上和如何将信号量机制引入到最优任务资源分配图中来解决死锁问题.其次说明了基于蚁群系统如何利用网格信息素系统模型实现该算法, 涉及任务资源分配图的构造, 以及通过蚁群的正反馈和分布式并行计算机制优化任务资源分配图.最后模拟试验结果说明所提出的算法可以有效地解决网格中任务死锁问题.

References:

[1] Foster I, Kesselman C.The grid:blueprint for a future computing infrastructure [M].Morgan Kaufmann Publishers, 1998.
[2] Zhang Yingfeng, Li Yulin.Grid computing resource management scheduler based on evolution algorithm[J].Computer Engineering, 2003, 29(15):110-175.
[3] Dorigo M, Gambardella L M.Ant colony system:a cooperative learning approach to the traveling salesman problem [J].IEEE Trans on Evolutionary Computation, 1997, 1(1):53-66.
[4] Gambardella L M, Dorigo M.Solving symmetric and asymmetric TSPs by ant colonies[C]//Proceedings of the IEEE Conference on Evolutionary Computation. IEEE Press, 1996:622-627.
[5] Colorni A, Dorigo M, Maniezzo V, et al.Distributed optimization by ant colonies [C]//Proceedings of European Conference on Artificial Life.Paris, 1991:134-142.
[6] He Liang, Jarvis Stephen A.Mapping DAG-based applications to multiclusters with background workload[C]//IEEE International Symposium on Cluster Computing and the Grid.Cardiff, Wales, UK, 2005:855-862.
[7] Aggarwal Mona, Kent Robert D, Ngom Alioune.Genetic algorithm based scheduler for computational grids[C]//Proceedings of the 19th International Symposium on High Performance Computing Systems and Applications(HPCS’05).Guelph, Ontario, Canada, 2005:756-761.
[8] Malewicz Grzegorz, Rosenberg Arnold L, Yurkewych Matthew.On scheduling complex dags for internet-based computing[C]//Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium(IPDPS’05).Denver, CA, USA, 2005:645-650.
[9] Chen Tingwei, Zhang Bin, Hao Xianwen, et al.Task scheduling in grid based on particle swarm optimization[C]//Proceedings of the Fifth International Symposium on Parallel and Distributed Computing(ISPDC’06).Timisoara, Romania, 2006:455-461.
[10] Qi Xuguang, Liang Zhengyou.Ant colony algorithm based resource allocation and task scheduling of grid[J].Journal of Guangxi University for Nationalities: Natural Science Edition, 2006(2):123-125.(in Chinese)

Memo

Memo:
Biographies: Qi Chao(1975—), male, graduate;Zhang Jing(corresponding author), male, doctor, professor, zhangjing@xaut.edu.cn.
Last Update: 2007-09-20