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

摘要

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