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

• 作者: 张毅 李小平 王茜 苑迎春
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 计算网格 工作流 有向无环图 启发式算法 逆向分层
• 年，卷（期）: 2008,（2）
• 所属期刊栏目: 研究论文
• 页码范围: 282-290
• 页数: 9页
• 分类号: TP393
• 字数: 8420字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.2008.02.012

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	苑迎春	东南大学计算机科学与工程学院	28	359	10.0	18.0
3	王茜	东南大学计算机科学与工程学院	60	1157	18.0	32.0
9	李小平	东南大学计算机科学与工程学院	31	465	11.0	21.0
13	张毅	东南大学计算机科学与工程学院	23	178	7.0	12.0