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

• 作者: 丰明坤 俞坚 卢亚辉 周武杰 彭艳斌 翟治年 郑志军
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 资源独立约束 打破对称 模式 匹配
• 年，卷（期）: 2020,（24）
• 所属期刊栏目: 工程与应用
• 页码范围: 236-241
• 页数: 6页
• 分类号: TP309
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.2005-0204

摘要

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