《计算机学报》文章摘要   全文下载
文章题目	基于逆向分层的网格工作流调度算法
作者	苑迎春1),3) 李小平1),2) 王茜1),2) 张毅1),2)
作者单位	1)(东南大学计算机科学与工程学院 南京 210096) 2)(东南大学计算机网络和信息集成教育部重点实验室 南京 210096) 3)(河北农业大学信息科学与技术学院 河北 保定 071001)
发表年份	2008
发表月份	2期(282—290)
文章摘要	摘要 有向无环图DAG(Directed Acrylic Graph)描述的工作流时间费用优化问题是计算网格下一个基本的且难以求解的问题.通过分析DAG图中活动的并行和同步完成特征，采取由后向前方法将活动逆向分层(Bottom Level, BL),将工作流截止期转化为层截止时间，提出截止期约束的逆向分层费用优化算法DBL(Deadline Bottom Level).算法中同层活动的开始时间不同于DTL(Deadline Top Level)算法中设置相同的策略，而是分别由其前驱活动确定，时间浮差被平均分配到各分层，以尽量增大活动的费用优化区间.通过大量模拟实验将DBL和MCP(minimum Critical Path)、DTL两算法比较，结果表明DTL将MCP的平均费用降低15.62%，而DBL将MCP的平均费用降低24.74%.最后讨论了截止期和分组参数对算法性能的影响. 关键词 计算网格；工作流；有向无环图；启发式算法；逆向分层 中图法分类号 TP393