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

摘要：

资源独立约束工作流可满足决策*WS-RI是业务安全规划的典型问题，在云制造等第三方资源环境中有重要意义。增量模式回溯法（Incremental Pattern Backtracking，IPB）是一种能够打破对称，高效求解*WS-RI的新型算法。它的一个主要优势是在模式验证时，通过渐进方式计算其中各块到资源集的指派图。但其在整个资源集中搜索指派邻点，实际性能存在缺陷，并在模式空间上放大。利用块中各步骤授权资源的分布间隙，设计了一种边界收缩的加速方法。它在搜索过程中增量计算邻域的初始边界，循环对齐和滑动当前边界，过滤无用资源，快速求出各个邻点。随机实例集上的实验表明，该算法显著优于目前最快的非增量模式回溯法。而较现有IPB，对低授权或高资源比例的相对困难实例，时间性能有明显提高。

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