基于逆向分层的网格工作流调度算法

被引：51

作者：

苑迎春

李小平

王茜

张毅

机构：

[1] 东南大学计算机科学与工程学院

[2] 东南大学计算机科学与工程学院南京河北农业大学信息科学与技术学院河北保定

[3] 南京东南大学计算机网络和信息集成教育部重点实验室南京

来源：

计算机学报 | 2008年 / 02期

关键词：

计算网格; 工作流; 有向无环图; 启发式算法; 逆向分层;

D O I：

暂无

中图分类号：

TP393.01 [];

学科分类号：

081201 ; 1201 ;

摘要：

有向无环图DAG(Directed Acrylic Graph)描述的工作流时间费用优化问题是计算网格下一个基本的且难以求解的问题.通过分析DAG图中活动的并行和同步完成特征,采取由后向前方法将活动逆向分层(BottomLevel,BL),将工作流截止期转化为层截止时间,提出截止期约束的逆向分层费用优化算法DBL(Deadline BottomLevel).算法中同层活动的开始时间不同于DTL(Deadline Top Level)算法中设置相同的策略,而是分别由其前驱活动确定,时间浮差被平均分配到各分层,以尽量增大活动的费用优化区间.通过大量模拟实验将DBL和MCP(mini mumCritical Path)、DTL两算法比较,结果表明DTL将MCP的平均费用降低15.62%,而DBL将MCP的平均费用降低24.74%.最后讨论了截止期和分组参数对算法性能的影响.

引用

页码：282 / 290

页数：9

共 8 条

[1] CGSP作业管理器合成服务的QoS优化模型及求解 [J].