一种求解异构DAG调度问题的置换蚁群  

Permutation Ant Colony System for Heterogeneous DAG Scheduling Problem

作　　者：邓蓉[1] 陈闳中[1] 王博[1] 王小明[1] 李灿[1] 

机构地区：[1]同济大学计算科学与技术系,上海201804

出　　处：《计算机科学》2010年第12期193-196,共4页Computer Science

基　　金：863国家重点基金项目(No.2009AA01Z141)资助

摘　　要：减少分布式程序的执行时间,是网格调度系统需要解决的重要问题。因分布式程序常建模为DAG图,故该问题又称异构DAG调度问题。提出的置换调度蚁群PSACS(Permutation Scheduling Ant Colony System)将DAG调度方案表示为任务置换列表,使用标准蚁群搜索技术探索解空间。实验表明,该算法明显优于遗传算法和粒子群算法,能够一次求出大部分(65%)同构DAG调度问题的最优解并获得非常好的异构DAG调度方案。Reducing execution time of distributed program is a major issue of Grid Scheduling System.Because scheduled programs are modeled by DAG,this problem is also called Heterogeneous DAG scheduling problem.Permutation Sche-duling Ant Colony System（PSACS） proposed by this paper presents solution of this problem as task permutation list and utilizes standard ACO searching technique to explore solution space.Experimental result indicates that PSACS outperforms GA and PSO substantially.It can get global optima for the majority（65%）of homogeneous DAG scheduling problems and pretty good solutions for heterogeneous DAG scheduling problems.

关 键 词：网格 DAG调度 蚁群优化 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]