工作流可满足性的约简增量模式回溯法

作     者：翟治年 刘关俊 卢亚辉 向坚 吴茗蔚 丰明坤 ZHAI Zhinian;LIU Guanjun;LU Yahui;XIANG Jian;WU Mingwei;FENG Mingkun

作者机构：浙江科技学院信息与电子工程学院浙江杭州310023 同济大学计算机科学系上海201804 深圳大学计算机与软件学院广东深圳518060 

出 版 物：《计算机集成制造系统》 (Computer Integrated Manufacturing Systems)

年 卷 期：2023年第29卷第11期

页      面：3624-3638页

核心收录：

学科分类：08[工学] 081104[工学-模式识别与智能系统] 081201[工学-计算机系统结构] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 081202[工学-计算机软件与理论] 

基　　金：国家自然科学基金面上项目(62172299,61972357) 浙江省基础公益研究计划资助项目(LGF22F020017)。 

主　　题：可满足性 工作流 授权 约束 资源分配 模型计数 模式 

摘      要：在大量云/服务化资源造成的性能压力下,增量模式回溯法(Incremental Pattern Backtracking, IPB)及其k指派技术是工作流可满足性求解的首选途径,但对“欠约束实例,其模式枚举性能显著下降,不利于大量可行解的优化选择。针对该问题提出新颖的简指派图概念,证明其可取代k指派图用于模式授权匹配验证,且尽管其块邻域大小耦合了图的整体信息,但仍可以增量方式计算。进而,分析了增量化简指派的实施条件和效果,及其主要影响因素。由此建立了约简增量模式回溯法(Reduced Incremental Pattern Backtracking, RIPB)。在资源配比为2~100的两个仿真实例集上测试,实验结果表明:在其基本子集上,RIPB较IPB有0.96~1.24倍时间性能优势;当资源比例升高或约束密度降低时,RIPB的优势有不同程度扩大;特别地,对资源配比为10而授权比例在1/2左右的两个子集,RIPB的平均优势分别可达1.29和1.61倍。