工作流模型时间与费用性能评估算法
|
摘要
对无环工作流模型的时间与费用性能参数进行分析,通过引入循环结构的提取算法,实现对有环工作流模型的时间与费用性能评估.利用改进的Tarjan算法和七元组来提取和存储每一个循环结构的参数信息.分析所有的七元组,计算所有标志节点的进度与费用值.有环结构中的循环结构在被提取完之后,会转化为无环结构,利用无环模型的算法即可进行进度与费用的评估.实验证明:算法能很有效地评估复杂模型的进度与费用性能,算法执行效率高,计算结果准确.
The time and cost performance parameters of acyclic workflow model were analyzed,the introduction of the extraction algorithm of the circular structure made it possible to evaluate the time and cost performance of ring workflow model.Using improved Tarjan algorithm and 7-tuple,each cycle structure parameter was extracted and stored.All 7-tuples were analysised,the time and cost values of all sign nodes of workflow model were calculated.The model will be converted into acyclic structure after the loop structures were extracted.It can evaluate the time and cost performance by using acyclic workflow model algorithm.Experiments show that the algorithm can be very effective to calculate the time and cost performance of the complex model.The algorithm is efficient and the results are accurate.
The time and cost performance parameters of acyclic workflow model were analyzed,the introduction of the extraction algorithm of the circular structure made it possible to evaluate the time and cost performance of ring workflow model.Using improved Tarjan algorithm and 7-tuple,each cycle structure parameter was extracted and stored.All 7-tuples were analysised,the time and cost values of all sign nodes of workflow model were calculated.The model will be converted into acyclic structure after the loop structures were extracted.It can evaluate the time and cost performance by using acyclic workflow model algorithm.Experiments show that the algorithm can be very effective to calculate the time and cost performance of the complex model.The algorithm is efficient and the results are accurate.
引文
[1]Li Jianqiang,Fan Yushun,Zhou Mengchu.Performance modelingand analysis of workflow[J].IEEE Transactions on System,2004,34(2):229-242
[2]苑迎春,李小平.基于串规约的网格工作流费用优化方法[J].计算机研究与发展,2008,45(2):246-253Yuan Yingchun,Li Xiaoping.Cost optimization heuristics for gridworkflow scheduling based on serial reduction[J].Journal ofComputer Research and Development,2008,45(2):246-253(in Chinese)
[3]范玉顺.工作流管理技术基础[M].北京:清华大学出版社,2001Fan Yushun.Workflow management[M].Beijing:TsinghuaUniversity Press,2001(in Chinese)
[4]Mark Allen Weiss.Data structures and algorithm analysis in C[M].2nd Edition.Beijing:China Machine Press,2011:230-232
[5]Tarjan R E.Depth-first search and linear graph algorithms[J].SIAM Journal on Computing,1972,1(2):146-160
[2]苑迎春,李小平.基于串规约的网格工作流费用优化方法[J].计算机研究与发展,2008,45(2):246-253Yuan Yingchun,Li Xiaoping.Cost optimization heuristics for gridworkflow scheduling based on serial reduction[J].Journal ofComputer Research and Development,2008,45(2):246-253(in Chinese)
[3]范玉顺.工作流管理技术基础[M].北京:清华大学出版社,2001Fan Yushun.Workflow management[M].Beijing:TsinghuaUniversity Press,2001(in Chinese)
[4]Mark Allen Weiss.Data structures and algorithm analysis in C[M].2nd Edition.Beijing:China Machine Press,2011:230-232
[5]Tarjan R E.Depth-first search and linear graph algorithms[J].SIAM Journal on Computing,1972,1(2):146-160