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

Reduced incremental pattern backtracking for workflow satisfiability

作　　者：翟治年[1] 刘关俊[2] 卢亚辉[3] 向坚[1] 吴茗蔚[1] 丰明坤[1] ZHAI Zhinian;LIU Guanjun;LU Yahui;XIANG Jian;WU Mingwei;FENG Mingkun(School of Information and Electronics,Zhejiang University of Science and Technology,Hangzhou 310023,China;Department of Computer Science,Tongji University,Shanghai 201804,China;College of Computer and Software,Shenzhen University,Shenzhen 518060,China)

机构地区：[1]浙江科技学院信息与电子工程学院,浙江杭州310023 [2]同济大学计算机科学系,上海201804 [3]深圳大学计算机与软件学院,广东深圳518060

出　　处：《计算机集成制造系统》2023年第11期3624-3638,共15页Computer Integrated Manufacturing Systems

基　　金：国家自然科学基金面上项目(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倍。Under the performance pressure caused by a great deal of clouded/servicized resources,the Incremental Pattern Backtracking(IPB)with its technique of k assignment is the preferred approach to Workflow Satisfiability(WS)solving.However,for"under-constrained"instances,its pattern enumeration performance drops significantly,which is not conducive to the optimal selection of a large number of feasible solutions.For this reason,a novel concept of reduced assignment graph was proposed,which would be replaced k assignment graph for authorization matching verification of a pattern.It was showed that such a graph could be computed incrementally,although the sizes of its block neighborhoods were coupled with its overall information.Furthermore,the working conditions and effects of incremental reduced assignment and their main influencing factors were analyzed.Thus,an algorithm of Reduced Incremental Pattern Backtracking(RIPB)was established.Experiments on two simulated sets of instances with the resource ratio of 2~100 showed that compared to IPB,RIPB achieved 0.96~1.24 times advantage in time performance on their basic sub-sets;the advantage of RIPB would expand to different degrees as the authorization ratio increasing or the density of constraints decreasing;in particular,on the two sub-sets with the resource ratio of 10 and the authorization ratio of about 1/2,the average advantage of RIPB could reach 1.29 and 1.61 times respectively.

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

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] TP301.6[自动化与计算机技术—控制科学与工程] TP309.2