首页> 中文期刊> 《计算机学报》 >基于逆向分层的网格工作流调度算法

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

         

摘要

有向无环图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%.最后讨论了截止期和分组参数对算法性能的影响.

著录项

  • 来源
    《计算机学报》 |2008年第2期|282-290|共9页
  • 作者单位

    东南大学计算机科学与工程学院;

    南京;

    210096;

    河北农业大学信息科学与技术学院;

    河北;

    保定;

    071001;

    东南大学计算机科学与工程学院;

    南京;

    210096;

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

    南京;

    210096;

    东南大学计算机科学与工程学院;

    南京;

    210096;

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

    南京;

    210096;

    东南大学计算机科学与工程学院;

    南京;

    210096;

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

    南京;

    210096;

  • 原文格式 PDF
  • 正文语种 chi
  • 中图分类 计算机网络;
  • 关键词

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

相似文献

  • 中文文献
  • 外文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号