首页> 中文期刊> 《北京工业大学学报》 >基于启发式分段的网格工作流费用优化方法

基于启发式分段的网格工作流费用优化方法

         

摘要

针对有向无环图(directed acrylic graph,DAG)表示的截止期约束下的网格工作流费用优化问题,提出启发式分段(segment level,SL)费用优化算法.通过分析DAG图中活动的并行和同步特征,算法对活动进行分段,时间浮差按比例分配到各段,段内的费用优化采用动态规划的求解策略实现.通过将工作流截止期转换为段截止时间,扩大了活动的费用优化区间,通过大量模拟实验将SL算法和MCP(minimum critcal path)、DTL (deadline top level)、DBL(deadline bottom level)算法比较,证明了SL算法的有效性.%Workflow scheduling with the objective of time-cost optimization is a fundamental problem in grids and generally the problem is NP-hard. In this paper, a novel heuristics called SL (Segment Level ) for workflows represented by DAG (Directed Acyclic Graph ) is proposed. Considering the parallel and synchronization properties, the workflow application is divided into segments, and the workflow deadline is transformed into the time intervals and appointed to different segments. The floating time is prorated to each segment to enlarge costtime duration, and a dynamic programming method is implemented to optimize cost for each segment. By comparing SL with MCP (Minimum Critical Path), DTL(Deadline Top Level), DBL(Deadline Bottom Level), the heuristics' efficiency is verified by experimental results.

著录项

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号