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

计算机科学 ›› 2010, Vol. 37 ›› Issue (12): 193-196.

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

邓蓉,陈闳中,王博,王小明,李灿

(同济大学计算科学与技术系上海201804)

出版日期:2018-12-01 发布日期:2018-12-01
基金资助:
本文受863国家重点基金项目( 2009AA01Z141)资助。

Permutation Ant Colony System for Heterogeneous DAG Scheduling Problem

DENG Rong,CHEN Hong-zhong,WANG Bo,WANG Xiao-ming,LI Can

Online:2018-12-01 Published:2018-12-01

摘要/Abstract

摘要： 减少分布式程序的执行时间，是网格调度系统需要解决的重要问题。因分布式程序常建模为DAG图，故该问题又称异构DAG调度问题。提出的置换调度蚁群PSACS(Permutation Scheduling Ant Colony System)将DAG调度方案表示为任务置换列表，使用标准蚁群搜索技术探索解空间。实验表明，该算法明显优于遗传算法和粒子群算法，能够一次求出大部分(65%)同构DAG调度问题的最优解并获得非常好的异构DAG调度方案。

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

Abstract: 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 Schedining 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.

Key words: Grid, DAG scheduling, Ant colony optimization

邓蓉,陈闳中,王博,王小明,李灿. 一种求解异构DAG调度问题的置换蚁群[J]. 计算机科学, 2010, 37(12): 193-196. https://doi.org/

DENG Rong,CHEN Hong-zhong,WANG Bo,WANG Xiao-ming,LI Can. Permutation Ant Colony System for Heterogeneous DAG Scheduling Problem[J]. Computer Science, 2010, 37(12): 193-196. https://doi.org/

参考文献

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed