基于串归约的网格工作流费用优化方法

摘要：

针对截止期限约束下有向无环图DAG(directed acyclic graph)表示的工作流费用优化问题,提出两个新的费用优化算法:时间约束的前向串归约算法FSRD(forward serial reduction within deadline)和时间约束的后向串归约算法BSRD(backward serial reduction within deadline).算法利用DAG图中串行活动特征给出串归约概念;基于分层算法对串归约组的时间窗口重定义,并提出动态规划的求解策略实现组内费用的最优化.两种归约算法综合考虑DAG图中活动的串并特征,改变分层算法中仅对单一活动的费用优化策略,实现了串归约组的时间收集和最优利用.模拟实验结果表明:BSRD和FSRD能够显著改进相应分层算法的平均性能,且BSRD优于FSRD.

关键词：服务网格、有向无环图、工作流、启发式算法、串归约

所属期刊栏目：45

分类号：TP393(计算技术、计算机技术)

资助基金：国家自然科学基金60672092;60504029

在线出版日期：2008-05-07（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：246-253