ACS-based resource assignment and task scheduling in grid  

基于蚁群系统的网格资源分配与任务调度(英文)

作　　者：祁超[1] 张璟[1] 李军怀[1] 

机构地区：[1]西安理工大学计算机科学与工程学院

出　　处：《Journal of Southeast University(English Edition)》2007年第3期451-454,共4页东南大学学报（英文版）

摘　　要：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.为了解决基于启发式算法的资源分配和任务调度过程中由于没有考虑任务间的相互依赖关系而出现的任务死锁问题,提出了一种基于蚁群系统的改进算法.首先阐述了如何将分配调度问题映射到任务资源分配图的优化选择问题上和如何将信号量机制引入到最优任务资源分配图中来解决死锁问题.其次说明了基于蚁群系统如何利用网格信息素系统模型实现该算法,涉及任务资源分配图的构造,以及通过蚁群的正反馈和分布式并行计算机制优化任务资源分配图.最后模拟试验结果说明所提出的算法可以有效地解决网格中任务死锁问题.

关 键 词：GRID resource assignment task scheduling ant colony system （ACS） task resource assignment graph （TRAG） SEMAPHORE 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]