文章快速检索 高级检索

A dynamic refinement approach for flexible activity based on knowledge tree and constraints
JIANG Yanrong, LI Weihua, YANG Jintao
School of Computer, Guangdong University of Technology, Guangzhou 510006, China
Abstract: Flexible workflow systems offer huge advantages in addressing dynamic uncertain factors during the modeling period; however, the dynamic refinement of flexible activities remains a challenge in the modeling and application of flexible workflows. Therefore, we propose a dynamic refinement approach of flexible activities based on a knowledge tree and various constraints. More specifically, we used the inclusion and generalization relationships of knowledge trees as heuristic information; further, we used activity selection constraints and temporal constraints to guide our verification processes. Given the introduction of a knowledge tree and its containing relationships, as well as activity selection constraint and temporal constraint rules, we provide a dynamic refinement algorithm and an algorithm for activity selection checkout and temporal constraint checkup. Finally, we provide a realization of our algorithms and offer case analyses. Our results show that our proposed algorithms are effective and can solve the problem of dynamic refinement of flexible activities quite well.
Key words: flexible workflow     dynamic refinement     temporal constraints     workflow generation     process modeling

1 柔性工作流的建模

FAR=FR∪CR为描述活动池中活动关系的规则集, 可以为空。其中FR为柔性规则集, CR为普通规则集, 采用ECA规则形式表示。FAC=CM为柔性活动的约束规则集, 其目的是用于柔性活动细化过程中的活动选择、活动时序关系的校验和生成子流图的正确性验证, 以保证细化结果的正确。采用一元或二元谓词、预设的操作集和规则进行表达, 在柔性活动的细化过程中, 生成的子流程必须满足该约束条件的规定。其中, C为约束规则集, 用于约束活动的选取、活动的组合、活动之间的时序关系、活动的属性等; M为修正规则集, 用于对生成的流程进行修改。

2 细化算法 2.1 知识树及与流程模板的影射

 图 1 软件开发的知识树 Fig. 1 Knowledge tree for software development

2.2 约束规则

1) 活动选取规则

 (1)

 (2)

2) 活动的时序约束规则

IF select (a) AND select (b) THEN Previous (a, b), 如果选择了活动ab, 则活动a必须要在b之前执行。

3) 属性约束规则

2.3 柔性活动的动态细化算法

 图 2 柔性活动细化算法FlexActRefining Fig. 2 Refinement algorithm for flexible activity

1) 根据柔性活动的目标, 在知识树中查找匹配的节点。对该节点映射的流程模板进行分析:若存在完善的流程模板, 则选择匹配最佳的流程模板返回; 否则转2)。

2) 分析该节点与子节点的关系。若不存在子节点, 则如果存在对应的约束关系, 用约束关系生成流程并返回, 否则出错返回。如果存在子节点, 则根据如下规则将父节点的实现转换为子节点的实现, 生成细化的子流图。① 若存在明确的时序关系规定, 则按照时序关系的要求去生成细化的子流图; ② 若该节点与子节点的关系为包含关系, 则按照AND或顺序结构生成子流图; ③ 若该节点与子节点的关系为泛化关系, 则按照OR结构生成子流图; ④ 其他情况则按照顺序结构生成子流图。

3) 依据约束规则, 对生成的子流图进行校验。分别调用函数ActSelValid () 对活动选取进行校验, 调用TemporalCons () 对活动的时序约束进行校验。若没有通过校验, 则出错返回。

4) 检查生成的子流图是否存在子柔性活动。若不存在, 则返回生成的子流图, 算法结束。否则, 对每一个子柔性活动, 转算法的步骤1)。

3 校验算法

{

for each selection constraint sci in SC{

decompose sci into Lpart and Rpart;

for each coni in Lpart {

if coni is “NOT select (a)”

if aA then coni = false;

else coni = true;

if coni is “select (a)”

if aA then coni = true;

else coni = false;

if coni is ctx

check if there exist fact faci and coni =faci

coni = true;

else coni = false;

}

while Lpart is not a single “true” or “false”{

if there exist “E1 AND…AND En” in Lpart{

if there exist a “false” in sub-expression

replace sub-expression with “false”;

else replace it with “true”;

}

if there exist “E1 OR…OR En” in Lpart{

if there exist a “true” in sub-expression

replace the sub-expression with “true”;

else replace it with “false”;

}

} // end while

if Lpart is true then{// rule sci is triggered.

for each opi in Rpart {

if opi is “NOT select (a)”

if aA then opi = false;

else opi = true;

if opi is “select (a)”

if aA then opi = true;

else opi = false;

}//end for

while Rpart is not a single “true” or “false”{

if there exist “E1 AND…En” in Rpart{

if there exist a “false” in sub-expression

replace sub-expression with “false”;

else replace it with “true”;

}

if there exist “E1 OR…En” in Rpart{

if there exist a “true” in sub-expression

replace sub-expression with “true”;

else replace it with “false”;

}

} // end while

if Rpart is “false” then{

report the information of error to user;

return false; //quit

}

} // end of the deal of Rpart

}// end of the deal of sci

return true;

TemporalCons () 是活动时序约束检验算法, 其中A为活动集, TC为时序约束集。算法首先检查时序约束tc涉及的活动是否存在于活动集A中, 如果不存在, 则返回false.时序约束规则tc可以分解出由时序约束组成的操作集Rpart, 然后对其中每个约束进行检查, 对不满足约束的情况进行出错报告, 并返回false.

{

for each temporal constraint tci in TC {

decompose tci into Lpart and Rpart;

if activities referred by Lpart are all in set A{

for each opi in Rpart{

if opi is “Previous (a, b)”{

if there is no path from a to b{

mark the error place;

return false;

}

}

if opi is “ImtPrevious (a, b)”{

if there is not any edge 〈a, b〉 then{

mark the error place;

return false;

}

}

if opi is “AndSyn (a, b)”{

if there exists a common predecessor As

and successor Ae for a and b then{

if satisfy Previous (As, a) and

Previous (As, b) and Previous (a, Ae)

and Previous (b, Ae) and there exist no

path from a to b or b to a then{

return true;

}

}

return false;

}

if opi is “OrSyn (a, b)”{

if there exists a common predecessor As

and successor Ae for a and b then{

if satisfy either (Previous (As, a) and

Previous (a, Ae)) or (Previous (As, b)

and Previous(b, Ae)) and a and b

can not run at the same time then{

return true;

}

}

return false;

}

if opi is NotLimit (a, b){

if there is no path from a to b or from b to a{

mark the error place;

return false;

}

} //end of the deal for each opi

} //end if

} //end of the deal of each tci

return true;

4 实现及实例分析

 图 3 软件开发过程的主流程 Fig. 3 Main flowchart of a software development process

 图 4 软件开发过程的动态细化方法示意图 Fig. 4 Illustration of dynamic refinement for a software development process
 图 5 细化之后的流程图 Fig. 5 Process model after refinement
5 结束语

 [1] 李竞杰, 王维平, 杨峰. 柔性工作流理论方法综述[J]. 计算机集成制造系统, 2010, 16(8): 1569-1577. LI Jingjie, WANG Weiping, YANG Feng. Review on approaches of flexible workflow[J]. Computer integrated manufacturing systems, 2010, 16(8): 1569-1577. [2] 周建涛, 史美林, 叶新铭. 柔性工作流技术研究的现状与趋势[J]. 计算机集成制造系统, 2005, 11(11): 1501-1510. . ZHOU Jiantao, SHI Meilin, YE Xinming. State of arts & trends on flexible workflow technology[J]. Computer integrated manufacturing systems, 2005, 11(11): 1501-1510. DOI:10.3969/j.issn.1006-5911.2005.11.001. [3] SADIQ S, SADIQ W, ORLOWSKA M. Pockets of flexibility in workflow specification[C]//Proceedings of the 20th International Conference on Conceptual Modeling. Berlin, Germany: Springer, 2001: 513-526. [4] VAN ELST L, ASCHOFF F R, BERNARDI A, et al. Weakly-structured workflows for knowledge-intensive tasks: an experimental evaluation[C]//Proceedings of the Twelfth International Workshop on Enabling Technologies: Infrastructure for Collaborative Enterprises. Linz, Austria: IEEE, 2003: 340-345. [5] ADAMS M, TER HOFSTEDE A H M, EDMOND D, et al. Worklets: a service-oriented implementation of dynamic flexibility in workflows[M]//MEERSMAN R, TARI Z. On the Move to Meaningful Internet Systems 2006: CoopIS, DOA, GADA, and ODBASE. Berlin Heidelberg: Springer, 2006: 291-308. [6] 邓水光, 吴朝晖, 俞镇. 支持动态建模的工作流管理系统的研究与设计[J]. 计算机辅助设计与图形学学报, 2004, 16(5): 712-718. DENG Shuiguang, WU Chaohui, YU Zhen. Flexible workflow model based on ECA joined with activity[J]. Journal of computer-aided design & computer graphics, 2004, 16(5): 712-718. [7] JIANG Yanrong, LI Weihua, YANG Jingtao. An incremental approach to modeling flexible workflows using activity decomposition and gradual refinement[J]. Journal of software, 2014, 9(10): 2628-2637. [8] BAE J, BAE H, KANG S H, et al. Automatic control of workflow processes using ECA rules[J]. IEEE transactions on knowledge and data engineering, 2004, 16(8): 1010-1023. DOI:10.1109/TKDE.2004.20. [9] GIL Y, RATNAKAR V, KIM J, et al. Wings: intelligent workflow-based design of computational experiments[J]. IEEE intelligent systems, 2011, 26(1): 62-72. DOI:10.1109/MIS.2010.9. [10] CHUN S A, ATLURI V, ADAM N R. Domain knowledge-based automatic workflow generation[C]//Proceedings of the 13th International Conference on Database and Expert Systems Applications. Berlin, Germany: Springer-Verlag, 2002: 81-93. [11] SHEPELEV V A, DIRECTOR S W. Automatic workflow generation[C]//Proceedings of the EURO-DAC '96, European Design Automation Conference. Geneva, Switzerland: IEEE, 1996: 104-109.
DOI: 10.11992/tis.201603009

0

#### 文章信息

JIANG Yanrong, LI Weihua, YANG Jintao

A dynamic refinement approach for flexible activity based on knowledge tree and constraints

CAAI Transactions on Intelligent Systems, 2017, 12(2): 158-165
http://dx.doi.org/10.11992/tis.201603009