关键词: 资源独立约束, 打破对称, 模式, 匹配

Abstract:

Workflow Satisfiability decision with Resource Independent constraints（*WS-RI） is an essential issue for the planning of business security, which has important meaning in the environments of the third-party resources, such as cloud manufacturing. Incremental Pattern Backtracking（IPB） is a new type of algorithm which can efficiently solve *WS-RI with symmetries broken. As one of its main advantages, when validating a pattern, it incrementally computes the bipartite graph which assigns resources to the pattern’s blocks. But its practical performance is defective in that any assigning neighbor is searched from the whole resource set, as will be amplified on the pattern space. In this paper, by exploiting the gaps among the authorized resources of each step in a block, an accelerating method of boundary shrinking is designed. It incrementally computes the initial boundary of a neighborhood in the searching process, in turn aligns and moves the current boundary. Thus, it can filter out useless resources and quickly find the neighbors. Experiments on the randomly generated instances show that the proposed algorithm is significantly better than the present fastest non-incremental PB. Compared to the present IPB, on the harder instances under conditions of low authorizing proportion or high resource proportion, the proposed algorithm has achieved obvious improvement subject to time performance.

Key words: resource independent constraints, symmetry breaking, pattern, matching