Abstract: 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.

Key words: satisfiability, workflow, authorization, constraint, resource allocation, model counting, pattern

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

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