*WS-RI增量模式回溯的边界收缩加速

作者：翟治年; 卢亚辉; 周武杰; 彭艳斌; 郑志军; 俞坚; 丰明坤

来源：计算机工程与应用, 2020, 56(24): 236-241.

DOI：10.3778/j.issn.1002-8331.2005-0204

• 资源独立约束
• 打破对称
• 模式
• 匹配

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

• 单位
  浙江科技学院; 电子工程学院