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

来源：计算机集成制造系统杂志2023年第11期北京时间：

作者：翟治年, 刘关俊, 卢亚辉, 向坚, 吴茗蔚, 丰明坤

单位：1.浙江科技学院信息与电子工程学院2.同济大学计算机科学系3.深圳大学计算机与软件学院

摘要：在大量云/服务化资源造成的性能压力下,增量模式回溯法(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倍。

关键词：可满足性,工作流,授权,约束,资源分配,模型计数,模式

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