| 基于启发式分段的网格工作流费用优化方法 |
| |
| 引用本文： | 龙浩,邸瑞华,梁毅.基于启发式分段的网格工作流费用优化方法[J].北京工业大学学报,2011,37(4):583-590. |
| |
| 作者姓名： | 龙浩 邸瑞华 梁毅 |
| |
| 作者单位： | 北京工业大学计算机学院,北京,100124;江西师范大学软件学院,南昌,330022;北京工业大学计算机学院,北京,100124 |
| |
| 基金项目： | 北京市教育委员会基金资助项目(JJ007011200901) |
| |
| 摘 要： | 针对有向无环图(directed acrylic graph,DAG)表示的截止期约束下的网格工作流费用优化问题,提出启发式分段(segment level,SL)费用优化算法.通过分析DAG图中活动的并行和同步特征,算法对活动进行分段,时间浮差按比例分配到各段,段内的费用优化采用动态规划的求解策略实现.通过将工作流截止期转换为段截止时间,扩大了活动的费用优化区间,通过大量模拟实验将SL算法和MCP(minimum critical path)、DTL(deadline top level)、DBL(deadline bottom level)算法比较,证明了SL算法的有效性.
|
| 关 键 词： | 网格工作流 有向无环图 启发式算法 分段 |
Segment Level Based Heuristic for Workflow Cost-time Optimization in Grids |
| |
| LONG Hao,DI Rui-hua,LIANG Yi.Segment Level Based Heuristic for Workflow Cost-time Optimization in Grids[J].Journal of Beijing Polytechnic University,2011,37(4):583-590. |
| |
| Authors: | LONG Hao DI Rui-hua LIANG Yi |
| |
| Affiliation: | LONG Hao1,2,DI Rui-hua1,LIANG Yi1(1.College of Computer Science,Beijing University of Technology,Beijing 100124,China,2.College of Software,Jiangxi Normal University,Nanchang 330022,China) |
| |
| Abstract: | 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 segm... |
| |
| Keywords: | grid workflow directed acrylic graph heuristics segment level |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
