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

2023-12-04翟治年刘关俊卢亚辉吴茗蔚丰明坤

计算机集成制造系统 2023年11期

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

(1.浙江科技学院信息与电子工程学院,浙江杭州 310023;2.同济大学计算机科学系,上海 201804;3.深圳大学计算机与软件学院,广东深圳 518060)

0 引言

工作流可满足性(Workflow Satisfiability,WS)[1-2]是一种保守(conservative)约束可满足问题(Constraint Satisfaction Problem,CSP)[3-4],其基本设置是求授权约束下任一可行资源分配(或确定其无解),称为WS决策。在工作流执行资源日益云/服务化趋势下,资源配比(资源数n与任务数k之比)显著增大,成为WS相对其他CSP的主要特征,并给WS求解技术带来了独特挑战,要求其实现固定参数k的多项式时间复杂度[1,5-7]。另一方面,WS决策侧重于安全策略性质的验证,不足以指导最终的资源分配。在WS无解时,为消除冲突,使业务得以运转,可以通过CSP值化[8-9]将部分约束柔性化,并最小化有关风险(也有研究通过调整授权来消除冲突,并最小化有关代价[10])。而当WS有解,特别是可行解很多时,更有必要从其他角度优选,特别是根据某些柔性约束,选出违反风险最小者。柔性约束导致的寻优需求对WS求解技术提出了进一步考验,要求其在枚举设置下,快速求解“欠约束”实例。上述两个方面的需求共同引出了本文的研究主题,下面展开进行分析。

首先,高资源配比将造成变量取值范围的膨胀,放大潜在的值对称因素。但保守CSP的打破值对称求解受到变量值域不统一的严重限制,在群等价树[11]、值可交换性[12]、逐片值可交换性[13]等相关研究中,均未得到很好解决,给人们造成了长期困扰。2014年,COHEN[14]面向常见的资源独立CSP,提出了资源分配模式概念,为完全值对称因素的分离打破准备了重要工具[15],并由此提出一种模式动态规划(Pattern Dynamic Programming,PDP)算法。PDP借助模式等价性来压缩缓存,但模式数量仍为超指数级,将造成极大空间开销,且该算法的设计需要反复搬移缓存内容,进一步制约了其时间性能。随后,文献[16]通过约束预处理、约束传播、资源动态排序和消除无用值对PDP进行了优化,但不能从根本上克服前述缺陷。2015年,KARAPETYAN[17]建立了模式空间上的回溯搜索技术,首次实现了多项式空间的WS固定参数求解。普通回溯的搜索树已体现了变量值域(即各任务的授权资源集)因素,在节点处只须检查或传播约束[3]。而模式回溯要在搜索节点处计算指派(二分)图及其(从左到右完备)匹配,以验证授权。指派图需要系统计算,每个块邻域耗费O(kn)时间,成为模式回溯的性能瓶颈。2019年,KARAPETYAN[7]在匹配等价前提下,将全指派约简为k指派,利用搜索上下文加速指派及匹配计算,得到增量模式回溯(Incremental Pattern Backtracking,IPB)法,其性能显著超过了包括CP-SAT(近几年Minizinc约束规划挑战赛的冠军求解器)和文献[16]PDP在内的多种代表性方法[7],将模式技术研究推向了高峰[18-21]。现有IPB可对资源分配或其模式进行决策、枚举或计数[22],但缺乏面向寻优场景的性能研究。另一方面,柔性约束违反风险是可行解寻优的重要标准,其建模框架在CSP领域已有研究[8-9],但相关算法难以应对WS的高资源配比压力。2015年,CRAMPTON[23]建模了柔性资源独立约束的违反程度,表明其仅由模式确定,由此提出了值工作流可满足性(Valued WS,VWS)问题及其模式分支限界(Pattern Branch Bounding,PBB)算法。2017年,CRAMPTON[24]针对多个柔性目标的度量值难以归一化的情况,提出了双目标VWS及其PBB算法。现有PBB均借鉴模式回溯法,以深度优先的模式枚举搜索为基础,但不支持刚性的约束和授权。

若刚性和柔性资源独立约束并存,且授权为刚性,需要对可行资源分配进行寻优,则IPB的模式枚举能力提供了直接的解决方案:根据柔性约束可快速计算模式的风险值[23],通过模式枚举找出风险最小可行模式,利用其搜索验证时的指派图匹配信息,转化为可行解即可。因其在仅与k有关的模式空间上搜索,并在模式层面进行解的优选,故具有固定k的参数化性能。若进一步引入目标剪枝能力,还可望达到更好的性能。

然而,现有IPB研究主要关注WS决策设置,并用相变实例集进行测试。相变是从“欠约束”到“过约束”的临界状态,将导致可行解极少而难以搜到,或刚好无解而难以剪枝,为决策设置提供了测试压力。但模式枚举的情况非常不同。特别是“欠约束”(通过扩大授权或降低约束而脱离相变点)的实例,可能有大量可行模式,均位于完全搜索树叶端,将共同拉近剪枝搜索树与完全树的差距。由于可行模式大量分布于叶端,找到其中一个很快,但枚举它们要遍历整个剪枝树,将非常缓慢。本文实验表明:IPB对“欠约束”实例的模式枚举性能很弱,且随着“欠约束”程度增大快速下降。从应用角度看,相变实例的出现条件过于苛刻,大多数WS有解实例都位于“欠约束”区,而“欠约束”程度越高,可行解越多,对枚举寻优性能要求越高。而对无解WS,也须尽量将问题调整到“欠约束”状态,并进行解的寻优。总的来说,枚举设置下“欠约束”实例的求解性能是业务运转和优化的重要保障,而现有IPB对此存在明显不足。

本文对基于IPB的模式枚举框架进行研究,并将问题设置简化为模式枚举计数(通过模式枚举完成模式计数)。主要贡献在于:通过挖掘模式授权验证中指派与匹配两个环节的关系,提出了新的指派图约简理论与技术;将其用于现有IPB的两种实现,均明显提升了模式枚举计数性能,特别是对高授权比例的“欠约束”情形,提升效果更为显著;在相变实例集上,其模式枚举计数性能也有所提高,故也有益于WS的决策/模式决策求解(至少无解情形下如此)。

1 引例

本章对文献[1]给出的采购工作流进行调整,以说明刚性和柔性资源独立性约束并存时,对WS可行解的寻优需求。该工作流包括创建订购t1、同意订购t2、收货签字t3、创建支付t4、收货副签t5、同意支付t6共6个任务,其执行关系为t1-t2-(t3-t5,t4)-t6,这里用—连接顺序任务,用()列出并行任务。该工作流有一定资源集,在它与任务集之间存在一定的刚性授权关系。在t1和t2、t3和t5、t4和t6三对任务之间,分别存在刚性互斥约束,以保证创建与同意或签字与副签职责的分离;在t1和t3之间存在柔性绑定约束,表示最好由订购者收货,当资源分配模式P为t1和t3分配相同资源时,违反度为0,否则为1;而在t1和t4之间存在柔性互斥约束,表示尽量避免由订购者创建支付,当模式P为t1和t4分配不同资源时,违反度为0,否则为1。根据两条柔性约束的重要程度,为相应违反度赋予不同权重,可得到关于P的目标函数。

上述刚性授权和刚性互斥约束共同确定了一个WS问题。但为了实现目标函数的最小化,需要对该问题进行模式枚举求解。

2 预备知识

约束的资源独立性,是指当计划π满足约束x∈X时(约束及其满足的定义与约束类型有关),任取U上的置换φ,计划φ∘π也满足x。根据该性质,将可通过模式抽象,简化计划的约束满足性验证。例如某模式相应的多个计划是否违反互斥约束x=(s,t),由s和t在该模式中是否同块即可判断,无须对每个计划分别验证。称模式P是合格的,当且仅当任何符合该模式的计划合格;又称模式P是授权的,当且仅当存在相应的计划授权。称授权且合格的模式为有效模式,而有效的全模式为可行模式。WS决策/枚举/计数设置分别求任一可行计划(或确定其不存在)/所有可行计划/可行计划的数量。这些设置可有模式化版,即模式决策/模式枚举/模式计数分别求任一可行模式/所有可行模式/所有可行模式的数量。引言所述的模式枚举计数要求通过枚举方式统计可行模式数量,本质上是模式枚举设置。

上述模式授权性,等价于模式的全指派图存在左完备匹配。该图定义为:

定义1给定模式Q,其全指派图B=B(Q)是以Q为左侧顶点集(每个左顶是Q作为划分的一个块),U为右侧顶点集的二分图,且块b∈Q在B中的邻域NB(b)=∩{U(t)|t∈b}。同时,将该邻域称为块b的全(指派)邻域。

该图的左完备匹配可为Q中每个块分配不同的资源,从而将模式转化为一个相应的计划。只要模式是授权的,该计划就是授权的。

利用模式之间的关系组织树形模式空间,并进行回溯搜索,可求解WS的各种问题设置及其模式化版本。模式回溯压缩了搜索范围,有助于化解高资源配比的性能压力,而代价是在搜索结点处增加了模式授权验证,包括计算模式指派图,再求其左完备匹配两个环节[17]。

文献[7]进一步建立了模式回溯的增量化框架:在每个节点处,相对于父节点只有一个新块,即包含当前任务的块(可能是当前任务单独成块,或将其加入父节点的某块而得),只须计算该块的指派邻域,即可将父节点指派图更新为该节点的指派图,称为增量指派;而在父指派图的匹配中,将当前任务所加入块原有的匹配边(若当前任务单独成块,则之前为空块,无匹配边)取消,然后以其为初始匹配,进行一次匹配增广,即得该节点指派图的左完备匹配,称为增量匹配。

对于全指派图,计算新块邻域需要O(kn)的时间,特别是求一个邻点也需要O(kn)的时间,在高资源配比(n/k)条件下,计算块指派的全邻域会严重拖慢搜索进度。为降低增量指派的计算代价,文献[7]建立了k指派图的概念:

定义2设模式Q的全指派图B=B(Q),称其生成子图K为Q的k指派图,当且仅当任取b∈Q,若|NB(b)|

该图在|NB(b)|≥k时对块b的邻域实施约简,降低指派计算目标和负担,且不影响授权匹配:

定理1给定模式Q,设其指派图B=B(Q),而其k指派图K∈K(Q),则B存在左完备匹配当且仅当K存在左完备匹配。

约简指派计算目标之后,文献[7]对计算出的块邻域进行缓存,以减少重复计算,而在其提供的IPB实现中,还使用了位运算来加速邻点计算。文献[21]为块指派邻点的计算引入了边界收缩加速,以克服IPB从整个U中连续查找邻点的缺陷。

文献[7]的IPB针对WS决策设置描述,但很容易修改用于模式决策,而文献[22]进一步给出了基于IPB近似求解WS计数设置的方法,容易修改用于模式枚举计数。因后者不统计可行模式相应的计划数,不存在遗漏可行计划的问题,故可采用k指派图代替该文献使用的全指派图。须注意的是,该文献对约束图做了连通分解预处理,以控制问题规模,加快总体求解,但其不能简单迁移到模式枚举/计数。不妨设有两个连通分支,分别取相应分问题的一个可行计划,组合即得总问题的一个可行计划(由于无跨连通片的约束,故组合不会导致约束违反,而在两个分计划中,每个变量的取值必然满足其值域要求)。反过来,将后者分解到两个连通片上,即可还原之前的两个分计划。于是约束分解不影响计划的枚举/计数。然而,在模式枚举/计数设置下,从两个连通片各自取一个分可行模式,其组合出的总可行模式未必唯一确定。具体有哪些结果,还依赖于每个分模式包含哪些可行计划。为了保证模式枚举/计数的正确性,应当取消约束分解。

3 约简增量模式回溯法

本文将定义一种结构优化的简指派图(定义3),进一步削减指派计算目标,并证明该图的左完备匹配存在性等价于全指派图(定理2)以及k指派图。简指派图的块邻域大小与指派图整体结构(体现在定义3中的|Q|和|∪Q|项)耦合,不利于增量计算(父子结点对简指派邻域的定义标准不同,影响子结点处的重用)。本文将通过证明有关的算法不变式(引理1和定理3),表明在IPB模式计数的搜索上下文中,可以增量方式计算简指派图。下面先给出有关概念:

定义3设模式Q的全指派图B=B(Q),称其生成子图R为Q的简指派图,当且仅当任取b∈Q,若|NB(b)|<|Q|+k-|∪Q|,则NR(b)=NB(b),否则|Q|+k-|∪Q|≤|NR(b)|≤k。易知Q的简指派图不唯一,将它们的集合记为R(Q)。

简指派图可代替全/k指派图,作为授权匹配的基础。其依据在于:

定理2给定模式Q,设B=B(Q)为其全指派图,R∈R(Q)为其简指派图,则B存在左完备匹配当且仅当R存在左完备匹配。

证明由于R是B的生成子图,充分性显然。下面只证必要性。

由二分图匹配的Hall定理,要证R有左完备匹配,只须证任取Q′⊆Q,|∪{NR(d)|d∈Q′}|≥|Q′|。而任取Q′⊆Q,分两种情况:

(1)存在b∈Q′,|NB(b)|≥|Q|+k-|∪Q|。由定义3知,|NR(b)|≥|Q|+k-|∪Q|,又恒有|∪Q|≤k,故有|∪{NR(d)|d∈Q′}|≥|NR(b)|≥|Q|≥|Q′|。

(2) 任取b∈Q′,均有|NB(b)|<|Q|+k-|∪Q|。由定义3可知任取b∈Q′,NR(b)=NB(b),而由B有左完备匹配可知|∪{NB(d)|d∈Q′}|≥|Q′|,从而也有|∪{NR(d)|d∈Q′}|≥|Q′|。

综合上可知,R必存在左完备匹配。

证毕。

给定模式Q中的块,求每个指派邻点都要验证若干候选资源,最坏情况下须遍历整个U,且对每个候选,都要验证其与块中O(k)个任务的授权,故邻点指派过程具有O(kn)代价。全指派块邻域的规模达到O(n),计算代价很高。k指派和简指派可分别对规模超过k和|Q|+k-|∪Q|的块邻域实施约简,而后者的约简条件更低。又因为k≥|NR(b)|,所以其约简结果也可能更小。

本文的改进IPB将对搜索到的每个模式节点,以增量化方式计算唯一的简指派图,其核心思路是:对模式空间中的结点Q,设其唯一的新块(包含当前任务的块)为bQ,而任取非新块b,必然属于Q的父结点模式P,此时有:

|Q|+k-|∪Q|≤|P|+k-|∪P|。

(1)

注意子模式比父模式多含1个新任务,故总有|∪Q|=|∪P|+1,但|P|≤|Q|≤|P|+1,即子模式所含划分块数未必加1。于是任取块b∈P∩Q,P简指派图对全指派邻域NB(b)在较高起点进行较小幅度的约简,所得b邻域一定满足Q简指派图的要求。只要b邻域在P处符合要求,到Q处可不加改动。从而在节点Q处,只须计算新块bQ的简指派邻域(这表明简指派图可以增量方式计算)。特别地,若|NB(bQ)|≥|Q|+k-|∪Q|,根据定义3,计算|Q|+k-|∪Q|个邻点即可作为NR(bQ),否则取NR(bQ)=NB(bQ)。下面分两种情况,对简指派与k指派图的约简能力进行比较:

(1)|NB(bQ)|<|Q|+k-|∪Q|时,有|NB(bQ)|

(2) 否则,即在|NB(bQ)|≥|Q|+k-|∪Q|条件下,简指派将实施约简,取|NR(bQ)|=|Q|+k-|∪Q|。但本条件下不一定有|NB(bQ)|≥k,即未必满足k指派的约简条件。综合这一差异,可给出本条件下简指派较k指派减少计算的邻点数量:

min{|∪Q|-|Q|+|NB(bQ)|-k,|∪Q|-|Q|}。

(2)

易知,式(2)必为非负值,其第一项对应本文实施约简而k指派未实施的情况,第二项对应两者都实施的情况。在第一种情况下|NB(bQ)|

综合上述条件可知,若用简指派代替k指派,则IPB主要的增量指派代价不增加,且简指派图规模不超过k指派图,可以保持增量匹配的时间复杂度,故其在性能上至少是安全的,不会招致明显损失。

其中条件(2)使得简指派真正发挥作用,并较k指派产生优势。单独考查一个搜索结点Q,可知|NB(bQ)|或|∪Q|-|Q|越大,该条件越容易满足。而满足后,简指派将产生式(2)描述的优势。当|∪Q|-|Q|越大时,式(2)中min操作所比较的两项都越大,其比较结果也越大。当|NB(bQ)|

以上考查了简指派优势在模式剪枝树中的分布情况,以便分析其整体效果。由于本文关心“欠约束”实例上的性能,而进入该状态有提高授权比例、提高资源配比(本文工作以高资源配比为前提,但其程度存在进一步差别)和降低约束密度3种基本手段。在后文实验部分,将分别改变这些参数,对简指派的改进效果进行测试和分析。

接下来面向WS模式枚举计数设置给出本文的约简增量模式回溯算法。

算法1RIPB(P,&R,M,&S,&U,&A,&X)。

输入:S,U,A和X描述一个WS问题;P是一个可行模式;&表示其后的参数为传址引用;R为P的简指派图,本文灵活使用该记号,也将其视为从P中块到其简指派邻域的映射,即R(b)表示P中第b块的简指派邻域;M是R的左完备匹配,本文灵活使用该记号,也将其视为从P中块到其匹配资源(未匹配时为nil)的映射,还用其表示P中所有块的匹配资源的集合,尚未匹配时为∅;X为约束集,本文灵活使用该记号,也将其视为从任务到其参与的约束子集的映射,即任务s参与的约束子集可表示为X(s);

输出:对问题(S,U,A,X),可由P扩展得到的可行模式数量;

输出不变式:返回时R与输入时相同。

1 cnt←0;//子问题可行模式的数量,初始化

2 if(|∪P|=k){//P为全模式,扩展过程终止

3 cnt←1;//扩展于P的可行模式数为1

4 }else{

5 s←SelectLeftTask(P,S);//按排序规则取一剩余任务

6 for(1≤b≤|P|+1){//b依次标识P中各块和空块

7 Pb←(P-{b})∪{b∪{s}};//s进入b后块标识不变

8 if(!Satisfy(Pb,s,X))continue;

9 bak←R(b);//备份新块的邻域

10 R(b)←∅;//准备计算新块的邻域

11 for(u∈∩{U(t)|t∈b}){//用b表示块本身

12 R(b)←R(b)∪{u};

13 if(|R(b)|=|Pb|+k-|∪Pb|) break;

14 }//不变式:此时R为Pb的简指派图

15 if(|b|=1)//s进入空块形成,此时M(b)=nil

16 M′←Augment(R,M,b);//R上从b增广M

17 else//|b|>1,M(b)≠nil

18 M′←Augment(R,M-{(b,M(b))},b);

19 if(M′(b)≠nil){//授权匹配成功

20 c←RIPB(Pb,R,M′,S,U,A,X);;

21 cnt←cnt+c;//按加法原理汇总

22 }

23 R(b)←bak;//恢复至P的简指派图

24 }//for

25}//if-else

26 return cnt;

算法1第2行检查模式P的完整性,若完整,且按输入要求也是可行模式,则由第3行计数为1,由第26行返回结果;若P不完整,第7行对其进行扩展,得到子节点Pb,第8行对Pb进行约束验证,只须验证s所参与的约束子集X(s),第10～18行对其进行授权验证,其中第10～14行为增量指派环节,15～18行为增量匹配环节。当两种验证通过后,第20行深度优先搜索下一节点。若第8行约束验证失败,恢复块b进而恢复模式P,切换到兄弟节点继续搜索。若授权验证失败,由第23行恢复第9行备份的R(b),再由第6行循环控制切换到兄弟节点。每个兄弟Pb的根子树搜索完成后返回计数结果c,第21行将c累加到父节点P的计数器cnt中,当各Pb根子树搜索完成后,cnt就是P根子树的可行模式数量,由第26行返回。注意,若没有Pb通过验证,则cnt保持第1行赋的0值,由26行返回,表明P根子树不含可行模式。

如下给出了算法1模式计数框架的基本特性:

引理1算法1的输出不变式成立,即对符合要求的输入,该算法结束时的R等于输入时的R。

证明|∪P|作归纳:

(1)基始。当|∪P|=k时,算法进入第3行的if分支,然后从第26行返回,R显然不变。

(2)归纳步骤。假设当|∪P|=h+1(0≤h<|S|)时结论成立,要证|∪P|=h时也成立。此时,因h

综合基始与归纳步骤,命题得证。

证毕。

算法1的指派约简不影响授权验证,有结论:

定理3算法1第14行的不变式成立,即该行结束时的R为Pb的简指派图。

证明由于|∪P|=|S|时不经过第14行,只须考虑|∪P|<|S|的情况,又分两种情况:

(1) 当P≠∅时,同时输入的R∈R(P)(算法1的输入要求),要证第14行处R∈R(Pb)。设全指派图B=B(P),B′=B(Pb)。这里b是模式Pb相对P的唯一新块(注意Pb中的块b包含第5行选择的s,而P中的块无论是否标识为b,均不含s)。任取Pb中(相对于P)的非新块d,由定义1可知NB′(d)=NB(d)=∩{U(t)|t∈d}。由引理1的结论及类似其归纳步骤的分析,第6行控制的每次循环都处理与输入时相同的R和P,故第10行面临的R∈R(P),即R为P的简指派图。由定义3可知R(d)⊆NB(d)(R为B生成子图),而且:①当|NB(d)|≥|P|+k-|∪P|时,|P|+k-|∪P|≤|R(d)|≤k。那么由NB′(d)=NB(d)也必有R(d)⊆NB′(d),再由式(1)有|P|+k-|∪P|≥|Pb|+k-|∪Pb|,从而必有|NB′(d)|≥|Pb|+k-|∪Pb|,|Pb|+k-|∪Pb|≤|R(d)|≤k。② 当|NB(d)|<|P|+k-|∪P|时,R(d)=NB(d)。则若|NB′(d)|<|Pb|+k-|∪Pb|,由|NB(d)|=|NB′(d)|<|Pb|+k-|∪Pb|≤|P|+k-|∪P|,可得R(d)=NB(d)进而R(d)=NB′(d)。综合①和②可知,R(d)也必满足Pb简指派图的要求。再由d作为非新块的任意性,只要第10～14行按Pb简指派图的定义对新块邻域R(b)进行更新,即可保证R∈R(Pb)。具体来说,由于Pb的全指派图是B′,更新应使R(b)⊆NB′(b),且当|∩{U(t)|t∈b}|=|NB′(b)|≥|Pb|+k-|∪Pb|时,应使|Pb|+k-|∪Pb|≤|R(b)|≤k,否则,应使R(b)=NB′(b),这正是该段代码所做的。因此,第14行结束后,R∈R(Pb)。

(2) 当P=∅时,只能有Pb={{s}},其中{s}是标识为b的块。由定义1,全指派图B′=B(Pb)右侧为U,而左侧只有一个块b,其邻域为NB′(b)=U(s)。若|NB′(b)|≥|Pb|+k-|∪Pb|=k,由第10～14行代码,易知其结束后R(b)⊆U(b)=U(s),且|Pb|+k-|∪Pb|=k=|R(b)|,而若|NB′(b)|<|Pb|+k-|∪Pb|=k,该段代码也使得R(b)=NB′(b),满足Pb简指派图的定义,故其结束后R∈R(Pb)。

证毕。

算法1中增量指派和增量匹配的时间复杂度分别是O(kn)和O(k2)。第8行的资源独立约束验证通常可以在O(k)或O(k2)时间内完成。故算法1总时间复杂度为O(Bk(kn+k2)),其中超指数函数Bk是第k贝尔数,等于k集合的划分数,即S的全模式数量。

算法1的空间占用主要是问题实例的授权、约束信息以及求解时所用指派图结构,分别占用O(kn)、O(k2)和O(k2)空间,故总的空间复杂度为O(k2+kn)。

4 实验研究

本章将简指派用于IPB模式枚举计数的两种实现,以验证其改进效果。首先用C++复现了IPB,并改造为模式计数算法,记为IPB21。IPB有公开的C#源代码(http://researchdata.essex.ac.uk/114)。本文也将其转换为C++,经程序优化后(在Windows平台上测试,其性能通常优于C#版本),改造为模式计数算法,记为IPB19。将上述两种实现所用k指派改为简指派,分别得到RIPB21和RIPB19。实验涉及的几种资源独立约束很容易快速验证。4种算法均采用文献[7](增强约束剪枝)的变量排序规则。而为突出指派图结构和指派计算方法所致性能差异,未使用块指派邻域缓存技术。其中21版和19版分别使用文献[21]的边界收缩方案和位运算来加速指派计算。另外,两者分别采用深度和广度优先方式进行匹配增广。最后,将根据19和21版本中较小的改进幅度来报告本文方法的优势。

此外,目前尚无基于通用求解器进行模式枚举的工作,作为一条可能的途径,其建模问题还有待研究。文献[16]的PDP决策算法系统化构造并缓存已找到的所有模式,很容易修改用于模式计数。本文复现了该算法,验证了其决策版本的性能水平,但其计数版本对后文两个实验中各自规模最小的一批实例,仍无法按时解出,故未纳入正式对比。

本文的实验环境为:主频4 GHz/睿频4.6 GHz的Intel Core i3-9350kf CPU(未超频)、8 G RAM、CentOS 8、GNU C++(-O3优化)、GMP6.2大整数库。对每个实例的执行时间,以30分钟为上限。

表1 4种算法的时间(s)和空间(KB)代价

将IPB19与IPB21比较。由表1,在两者均完全解出的前5组实例上,后者的时间性能高达前者的1.66～3.45倍。这主要源于以下两个因素:

(1) IPB19的实现存在一个性能缺陷:若某个模式节点P所有验证通过,则深入到以P为根的子树,当根子树搜索完成回溯到P时,为恢复P的指派图,重复计算了P处新块(P相对于其父结点的唯一新块)的邻域。在前述公开的C#源代码(IPB决策版本)中,该缺陷体现为:初次搜索某节点P时,若其新块中含多个任务,调用AddStepsToNode()更新指派图,而回溯到P时,需要维护指派图结构,为此调用RemoveStepsFromNode()。这两个函数均调用ComputeIncidenceList()计算块邻域,并在该函数内,通过局部变量短暂备份了块邻域,以便匹配失败后恢复,但缺乏稳定可持续的备份,造成了回溯时的重复计算。该实现的块邻域缓存机制有助于缓解相关影响,但写入缓存后进入子树搜索,若期间缓存到达容量上限而清空,则回溯时无法从缓存中查出,无法保证消除重复计算。本文实验中关闭缓存以对比不同指派图及计算方法的原始性能差距,会使上述缺陷充分暴露。为分析其影响,本文针对其进行优化得到IPB19opt,在前5组实例上再次进行测试,所得平均时间依次为4.77155、15.5722、1.04655、85.24735和830.7432s。由此重新计算IPB21的性能优势,将分别下降到1.33、1.16、2.39、1.63和1.21倍,仍比较显著。这表明除了IPB19的自身缺陷,还存在IPB21与IPB19的特性差异,共同导致了IPB21在本实验中的优势。

(2) IPB21和IPB19的主要差异在于任务块指派邻域的计算加速方式。IPB19在整个资源集U上搜索邻点,但借助位运算快速验证每个候选资源(预先为每个资源计算授权任务集,用64位图表示,而任务块也有位图表示,可借助位运算判断前者是否包含了后者),其实际代价为常数,不妨设为1次操作。但块越大,其邻点在U中的分布越稀疏,为找到一个而验证的候选越多。本实例集互斥约束密度很低,使得剪枝模式树边缘更接近完全树叶端,有利于增大近叶节点处新块的大小(从根到叶的每个结点引入一个新任务,但多数时候是将其加入旧块,故所得新块趋于变大),这对IPB19的性能不利。而IPB21的边界收缩加速方案利用任务授权资源之间的空隙(以及两侧的边缘)来缩小搜索范围,但其可能将一个候选资源与块中每个任务进行一次授权关系判断,每次判断需要常数时间,故候选验证代价与块大小有关。设给定块大小为x,验证一个候选的平均代价是x/y次操作(1≤y≤x,任务授权比例越高时,块授权资源越稠密,y越趋于1),若块中存在授权资源稀疏的任务,可使每个邻点的搜索范围缩小z倍,则只要yz>x,IPB21便会优于IPB19。降低授权比例可增大z值和y值,将有利于提高IPB21与IPB19的性能比。若固定授权比例及相应的z和y值,则当约束密度降低导致x增大时,IPB19搜索一个邻点的范围将指数级扩张,而IPB21验证每个候选的代价只是线性增大,故IPB21与IPB19的性能比也会提高,而且速度很快。为排除因素(1)的作用,观察前述IPB21与IPB19opt的比较结果,可知IPB21处于优势,这与本实例集的低约束密度有关。进而,IPB21的最大/小优势分别出现在第3/2组实例上,分别与其授权比例较低/高有关。尽管第5组实例的授权比例高于第2组,对IPB21优势的抑制作用更强,但其资源配比不高,资源数量较少,影响了要计算的邻点数,故未更有效地抑制IPB21的优势。

由于IPB21和IPB19作为IPB的不同实现出现了极大性能差异,以上详细分析了有关因素。本文主题在于简指派对k指派的改进,后文将重点考查RIPB较对应版本IPB的性能提升情况。

现在将IPB21与RIPB21进行比较。由表1可知,在两者均完全解出的前6组实例上,后者的时间性能达到前者的0.97～1.24倍,平均为1.11倍。这表明使用简指派图有效控制了邻点的计算数量,进而提高了授权验证和整体搜索性能。特别地,在第2、5、6组,RIPB21的优势达到1.15～1.24倍。这几组实例的特点是资源配比和授权比例都较高。此时,各任务的授权资源集较大,任务块的全邻域较大,有利于达到第3章的实施条件(2),使简指派较k指派出现式(2)描述的优势。

再将IPB19与RIPB19进行比较。由表1,两者均完全解出了前5组实例,后者的时间性能达到前者的1.14～1.43倍,平均为1.3倍。19版本回溯时重复计算块邻域,将导致指派代价在总验证代价中所占比例扩大(注意回溯时不必重新验证约束),故使用简指派导致的优势也超过了21版本。

仍对前述50组四参数,将m取作原来的2倍,然后每组生成2次,得到100个较高约束密度的实例,按前述三参数分10组进行测试,结果如表2所示。相对于表1,同一算法在对应实例组上的时间性能大大提高,其原因主要是稠密约束有效增强了剪枝,加快了枚举计数搜索。

表2 2倍约束下4种算法的时间(s)和空间(KB)代价

将IPB19与IPB21比较。由表2,在两者均完全解出的前6组实例上,后者的时间性能达到前者的1.64～3.18倍。相对于表1,第3、4、5组优势均下降,且3、4组下降较多,只有第2组优势略有提高。再对IPB19opt进行测试,在前6组实例上的平均时间依次为1.49175、4.51175、2.21755、44.04355、238.53475和412.5632s,相应的IPB21优势为1.32、1.20、2.13、1.30、1.21和1.22倍。相对于约束倍增前,第1、3、4组优势均下降,且3、4组下降较多,只有第2组优势略有提高。与IPB21较IPB19优势的变化相比,基本同步。这表明IPB21对IPB19性能优势在约束倍增后的变化(总体上是下降的)主要不是由IPB19自身缺陷导致的,而与IPB21和IPB19指派计算方式的差异有关。在之前的因素(2)中,也已分析过较稀疏约束对IPB19更不利的原因。

将IPB21与RIPB21比较。由表2,在两者均完全解出的前6组实例上,后者的时间性能达到前者的0.96～1.21倍,平均1.11倍。再将IPB19与RIPB19比较。由表2,在两者均完全解出的前6组实例上,后者的时间性能达到前者的1.14～1.40倍,平均为1.26倍。总体上,仅约束密度变化时,简指派较k指派的优势略有下降。这是因为较多的约束增强了剪枝,降低了该技术发挥优势的机会。

上述倍增前后的约束密度均处于较低水平。实验2将在较复杂约束配置下,通过施加充分的互斥约束达到相变条件,然后减少约束观察其影响。

表1和表2中,4种算法的空间占用相差很小。它们都使用唯一的指派关系存储,其内容随着搜索不断变化,动态部分在堆上分配。表中RIPB和对应IPB的峰值空间完全相同。尽管RIPB使用了更小的简指派图,预期空间占用会有所下降,但系统以4KB页为单位分配堆空间(表中的空间为平均值,不一定是4KB的整数倍),每次可能分配较多的页,除了满足当前申请的需要,还给出较大的预留,通常可以容纳以字节为单位的指派图变化。

现在限定k=16,m=18(ω=15),使μ从200以步长200增加到1000,再分别取AP为L、M和H,得到15组四参数配置,每个配置生成10个实例,对4种算法进行测试,观察其随资源配比μ和授权比例AP增加的变化,结果如表3所示。

表3 资源增加时3种算法时间(s)与空间(MB)代价

固定AP=L时,随着μ的增加,每种算法的时间性能呈现出较强的下降趋势。这是因为μ增加会增大任务授权资源集,有利于块邻域的扩大,这将使授权匹配更容易成功,剪枝模式树规模相应扩大,而搜索性能随之降低。而当AP=M和L时,性能下降趋势减缓。这是因为授权比例较高时,较低的资源配比就可使任务和块的授权资源集足够大,授权匹配基本可以成功,故继续增加资源配比基本不会导致剪枝树规模增大,而只是增加了与n有关的预计算开销。从另一角度观察表3的数据,固定μ=200时,随着AP的升高,每种算法的性能都在下降。而当μ达到400或600以后,随着AP的升高,同一算法的性能出现明显的先下降后上升的变化。先下降仍是由于授权剪枝削弱导致搜索树规模增大,后上升是因为剪枝树规模基本不变,而同样任务块的授权资源在U中密度增大,只要检查更少的候选就可找到足够的邻点,导致了块指派邻域计算代价下降。

统计表3的数据,在μ=200的3组实例上:RIPB21(较IPB21)的提升倍数为0.97～1.17,平均为1.04;RIPB19(较IPB19)的提升倍数为1.05～1.36,平均为1.17。在μ=600的3组实例上:RIPB21的提升倍数为0.97～1.20,平均为1.11;RIPB19的提升倍数为1.18～1.41,平均为1.31。在μ=1000的3组实例上:RIPB21的提升倍数为0.97～1.29,平均为1.16;RIPB19的提升倍数为1.28～1.56,平均为1.40。随着资源配比以步长4增加,简指派的平均优势在21版本上从1.04增加到1.11再增加到1.16;在19版本上从1.17增加到1.31又增加到1.40。

在AP=L的5组实例上:RIPB21(较IPB21)的提升倍数为0.967～0.973,平均为0.971;RIPB19(较IPB19)的提升倍数为1.05～1.28,平均为1.17。在AP=M的5组实例上:RIPB21的提升倍数为0.98～1.29,平均为1.13;RIPB19的提升倍数为1.11～1.56,平均为1.37;两者的最大提升倍数1.29和1.56均出现在μ=1 000处。在AP=H的5组实例上:RIPB21的提升倍数为1.17～1.22,平均为1.20;RIPB19的提升倍数为1.349～1.365,平均为1.358。随着AP增加,简指派的平均优势在21版本上从0.97增加到1.13再增加到1.20;在19版本上从1.17增加到1.37又下降到1.36。

下面对上述性能变化的原因进行分析。大体上,资源配比或授权比例越大,任务授权资源越多,节点Q新块bQ的全邻域NB(bQ)越大,越有利于条件(2)的满足,使简指派较k指派的优势扩大。不过,AP从M到L时,RIPB19的优势出现了下降。这是μ=1 000时,AP从M到L时,简指派优势显著下降导致的。其原因在于,μ=1 000和AP=M时,NB(bQ)已足够大,使得简指派的实施已经很充分,继续提高授权比例作用不大。特别地,提高授权比例仍将增加邻点在U中的密度,使得搜索更少的资源就可完成指派邻域计算,且其对19版本特别有利(因其候选验证代价为常数,指派效率主要取决于搜索范围)。这就会相应降低指派代价在整体验证中的比例,以及简指派的优势。

表3的空间数据表明,授权比例的增大对4种算法的峰值空间占用几乎没有影响,而资源配比增大使其有微弱增长。这是因为后者显著增大了资源总数,使以字节为单位的实例和索引数据规模明显增大,导致系统分配了更多的4KB页面。RIPB和对应IPB的空间占用都相同,其原因类似于之前的分析。

实验2文献[7]配置at-most-r和at-least-r两种全局约束(分别要求p≥3个任务至多/至少由3个不同资源执行,而p称为约束的元数)和(2元)互斥约束,研究了相变实例的生成,并公开了有关实例集(http://researchdata.essex.ac.uk/114)。其生成规则简介如下:将每个资源随机授权给[1,0.5k]个任务,相应的授权比例α%约为1/4;分别固定μ%=10和100,让k从18开始增长;对每个k,分别生成k个5元块at-most-3和at-least-3约束,以及导致实例难度相变的特定数量互斥约束,得到1个实例,如此重复100次,得1组实例。本实验只对每个算法完全解出的实例组进行统计,并对每组100个实例的性能结果取均值。

先用上述相变实例集测试4种算法,μ%=10和μ%=100的时间结果分别如图1和图2所示。由于k的变化导致最小和最大执行时间相差很大,本实验绘图均采用了对数纵坐标。其中IPB19较IPB21更有优势,这与实验1的情况相反。由于IPB19本身尚且存在性能缺陷,该优势必然源于IPB19和IPB21指派计算方式的差异。实验1中已分析表明,给定授权比例,则降低约束密度(特别是互斥约束密度)有利于提高IPB21与IPB19的性能比。此处两个相变实例集在固定1/4授权比例等条件下,通过增加互斥约束来到达“欠约束”到“过约束”的临界点,将快速抑制块大小,迅速降低IPB21与IPB19的性能比,使后者占据优势。对于μ%=100设置下各算法按时解出的实例组,每种算法的平均峰值空间均在19M左右。而在μ%=100的解出实例组上:当k从18增至43时,21版本的峰值空间从19M+增至22M+;当k从18增至43时,19版本的峰值空间从18M+增至77M+,且当k=43时,增至177M+。μ%=100时空间占用的增加较为明显,主要是问题实例和一些预计算索引的规模与n相关,增长更快。特别是19版本,在n>k2时,对指派图中的块邻域使用了耗空间的散列存储。

统计图1的原始数据可知:在4种算法共同解出的31组实例上,RIPB21的时间性能达到IPB21的1.03～1.08倍,且随k的增加呈微弱增大趋势,平均1.06倍,而RIPB19的时间性能达到IPB19的1.08～1.17倍,且随k的增加呈一定增大趋势,平均1.15倍。本实例子集n/k=10而授权比例约1/4,故当k=18～48时,新块大小|bQ|最大为4～5(当块增大时,块邻点数首次不足1)。而相应的相变点(互斥约束数量)为27～82(见该子集的e50值表),故k=18和48时,5元块bQ的互斥约束剪枝概率约为0.84和0.52,相应的Q较难进入授权验证。当k增加时,剪枝树规模扩大和搜索结点数增多,只是导致小的新块更频繁出现。对|bQ|=3,当k=18～48时,|NB(bQ)|约为2.8～7.5,但|∪Q|-|Q|很难达到16～41,导致条件(2)很难成立,|bQ|=4时更是如此。故RIPB主要在|bQ|≤2时可能取得优势,其整体优势也很受限。|bQ|=1时,|NB(bQ)|≥k,简指派达到充分优势|∪Q|-|Q|,当k增加导致剪枝树规模扩大时,|bQ|=1可发生在更深的结点处,相应的|∪Q|-|Q|会有所扩大,有利于简指派整体优势的扩大。在19版本上,简指派方法导致了更大的平均性能提升,其优势随k增大的趋势也更强,主要是因为该版本回溯时重新计算指派,扩大了指派代价在整体验证中的比例。

统计图2的原始数据可知:在共同解出的26组实例上,RIPB21的时间性能达到IPB21的1.13～1.24倍,最大倍数出现在k=21处,此后有一定下降趋势,最小倍数出现在k=42处,平均1.18倍;在共同解出的29组实例上,RIPB19的时间性能达到IPB19的1.15～1.35倍,最大倍数出现在k=21处,此后有下降趋势,最小倍数出现在k=46处,平均1.25倍。RIPB的优势较图1明显扩大,但其在k增加时,主要呈下降趋势。本实例集n/k=100而授权比例为1/4,当k=18～45时,|bQ|最大为6～7。但其相变点为39～125(见该子集的e50值表),故k=18和45时,5元块bQ的互斥约束剪枝概率为0.93和0.72,故进入授权验证的bQ较图1更小一些。对|bQ|=4,当k=18～45时,|NB(bQ)|约为7.0～17.6,难以满足条件(2)。对|bQ|≤3,当k=18～45时,|NB(bQ)|至少为28～70,均超过k而使简指派有充分优势,使其整体优势较图1明显扩大。但是图2的剪枝树达到更大规模,但进入授权验证的bQ反而小于图1,意味着搜索节点中有更高比例的剪枝节点。这不利于RIPB的整体优势(因约束剪枝不进入指派,授权剪枝的|NB(bQ)|通常非常小,简指派在剪枝处基本没有优势),只是图2大量剪枝由快速的约束验证导致,其负面作用有限。而当k增大导致剪枝树扩张时,这种负面作用将随之变得显著,不利于RIPB整体优势幅度的保持。简指派在19版本上的性能提升仍然更大,原因也与之前类似。相对于图1的情况,随着资源配比的扩大(但增加了互斥约束以保持相变),RIPB的性能优势明显扩大。对其原因,将与下面扩大授权的情形一起分析。

对μ%=10的情形,将授权方式分别改为每个资源[1,0.75k]和[1,k]个任务,相应的授权比例α%≈0.375和0.5分别是原来的1.5倍和2倍,保持其他参数不变,按前述方式生成实例集,对4种算法进行测试。α%≈0.375时的结果如图3所示,α%≈0.5时的结果如图4所示。4种算法的性能均明显下降,这是因为扩大授权比例造成实例,进入“欠约束”状态,模式剪枝树显著扩大,模式枚举搜索代价相应提高。每种算法对上述各解出实例组的平均峰值空间均在19M左右,与之前相近。这是因为扩大授权对实例和预计算索引的规模影响不大。

统计图3原始数据可知:在共同解出的20组实例上,RIPB21的时间性能达到IPB21的1.11～1.24倍,随k呈增长趋势,平均1.16倍;在共同解出的20组实例上,RIPB19的时间性能达到IPB19的1.19～1.48倍,随k呈增长趋势,平均1.26倍。统计图4原始数据可知:在共同解出的18组实例上,RIPB21的时间性能达到IPB21的1.45～2.10倍,随k呈增长趋势,平均1.76倍;在共同解出的17组实例上,RIPB19的时间性能达到IPB19的1.34～2.01倍,随k呈增长趋势,平均1.61倍。相对图1的情况,图3和图4中RIPB的优势明显扩大,其原因相似,这里仅分析图4的情况。该子集的授权比例为1/2,当k=18～35时,|bQ|最大为8～9。但是其相变点(注意授权比例增大时,原有约束不变)为27～62,故k=18和35时,5元bQ的互斥约束剪枝概率约为0.84和0.65,较难进入授权验证。而当|bQ|≤3时,必有|NB(bQ)|≥k,简指派均有充分优势,故其整体优势较图1明显扩大。同时由于k增大时,简指派优势不充分的|bQ|=4节点比例提高有限,简指派的优势也将随k增大而明显增长。2倍授权时,简指派在21版本上取得了更大优势,这是因为该实例集资源配比和授权比例都较大,任务和块的授权资源密度很高,对19版本的指派计算方式非常有利。这使得在19版本中,尽管存在重复指派缺陷,但指派代价占总验证代价的比例仍然低于21版本,从而简指派的改进效果相对难以凸显。

增大授权比例明显扩大了简指派方法的优势,而有关原因在实验1中已进行过分析。但这里2倍授权比例就导致了较10倍资源配比更大的优势,原因在于:

(2)μ%=100的相变实例集在增大资源配比时,也增加了约束数量。后者导致剪枝模式空间不会明显扩大,抑制了较大|∪Q|-|Q|值的增多。而由图2和图4相关分析可知,该值对简指派的优势程度起很大作用。而增大授权比例让实例进入“欠约束”状态,剪枝模式树边缘更逼近完全树叶端,导致更多较大的|∪Q|-|Q|值,从而简指派的作用效果也随之提升。

现在对μ%=10的情形,将约束数量减少为原来的0.75和0.5倍,保持其他参数不变,按前述方式生成实例集,对4种算法进行测试。0.75倍约束时的结果如图5所示,0.5倍约束的结果如图6所示。每种算法对上述各解出实例组的平均峰值空间均在19M左右,与之前相近。这是因为减少约束对实例和预计算索引的规模影响也不大。

统计图5原始数据可知:在共同解出的19组实例上,RIPB21的时间性能达到IPB21的1.03～1.13倍,平均1.09倍;在共同解出的18组实例上,RIPB19的时间性能达到IPB19的1.16～1.36倍,平均1.25倍。相对图1的情况,RIPB的优势有一定扩大。这主要是因为减少约束使实例偏离相变点,进入“欠约束”状态,使更多简指派有潜在优势的搜索结点Q(位于原来的剪枝边缘或其下方)进入了授权匹配验证。这些节点Q位置较深,其|bQ|必须很小,才能使|NB(bQ)|取满足条件(2)的值。而深度越大,这样的结点相对越少,故RIPB的优势较图1提高不多。

由统计图6原始数据可知:在共同解出的8组实例上,RIPB21的时间性能达到IPB21的1.06～1.12倍,平均1.09倍;在共同解出的8组实例上,RIPB19的时间性能达到IPB19的1.31～1.39倍,平均1.35倍。而在图5的前8组实例上,RIPB21的时间性能只是达到IPB21的1.03～1.10倍,平均1.07倍。可见,随着约束进一步减少,RIPB的优势仍有微弱扩大,其原因仍类似于图5相关分析。0.5倍约束的影响明显弱于2倍授权比例,这是因为单纯降低约束对简指派优势的影响比较局限,特别是不能增大NB(bQ)的值。