基于图裁减和图搜索的工作流图验证算法  

Improved algorithm combining graph-reduction and graph-search for workflow verification

作　　者：党正军[1] 杜中军[1] 

机构地区：[1]四川大学计算机学院,成都610065

出　　处：《计算机工程与应用》2011年第4期226-228,244,共4页Computer Engineering and Applications

摘　　要：工作流程中的结构冲突将导致工作流管理系统无法正常运行,因此需要在工作流图付诸实施之前要验证工作流的正确性,检测出其中的冲突。目前,无环工作流图的冲突检测在Mahanti-Sinnakkrishnan算法中已经得到了较好的解决,L.Kai和L.Qiang提出了CWRS算法用来检测有环工作流图的结构冲突,但该算法存在缺陷,会产生误判。对CWRS算法进行分析,指出了该算法的缺陷,并提出了改进方法,解决了有环工作流图AND型节点不配对时的冲突检测问题。Since the structural conflicts in workflow processes can lead to malfunction of workflow management systems,the problem should be detected before workflow processes are put into execution.Up to now,workflow verification without cycles is well solved in Mahanti-Sinnakkrishnan algorithm.L.Kai and L.Qing proposed an algorithm called CWRS to verify workflow graphs which may have cycles,but it has some deficencies which can lead to misjudgment.This paper mainly analyzes the CWRS algorithm,and points the deficencies,then proposes an improved method to completely solve the structural conflicts even if unpaired AND nodes exist in the loop.

关 键 词：工作流 有向图 工作流验证 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]