顶点覆盖约束下的同类机排序算法研究

嵇雯蕙 陈智斌

(昆明理工大学理学院,昆明,650000)

1 引言

经典的平行机排序问题(Parallel Machine Scheduling)是著名的NP-hard 问题.同类机作为同速机的推广,其排序问题显然也是NP-hard 的.近几十年来,关于排序问题,不管是离线还是半在线或在线版本,学者们都做了大量的研究工作[1,2,3].经典的平行机问题存在多项式时间近似方案[4],当机器数固定时,甚至存在完全多项式近似方案[5].2012 年,Wang 等[6]提出了平行机排序与顶点覆盖的组合问题(Combination of parallel machine scheduling and vertex cover).而一个顶点覆盖(Vertex Cover)指的是无向图的一个顶点子集,使得图中的任意一条边都至少存在一个顶点属于该子集.为求解平行机排序与顶点覆盖的组合问题,Wang 等基于local ratio 算法[7]和LPT(Longest Processing Time first)算法[8]给出了近似比为的算法.同年,Hong 等[9]在Wang 的基础上,提出了改进算法,当机器数为2 或者3 时,将近似比缩减至.相比排序问题,顶点覆盖问题虽然同为NP-hard,但它不存在小于1.36 的近似比,除非P=NP[10].

本文考虑如下的顶点覆盖约束下的同类机排序问题.给定m台机器M={M1,···,Mm}和n个工件J={J1,···,Jn},其中机器Mj的速度为sj(j=1,···,m),不失一般性,可设s1≤··· ≤sm; 工件Ji的加工时间为pi(i=1,···,n),工件Ji在机器Mj上的负载为(i=1,···,n,j=1,···,m).在这些工件之间,存在着一些“关系”,我们用一个无向图G=(V,E)来描述这些关系,图中n个顶点分别代表n个工件,图中的一条边表示该边的端点所对应的两个工件之间存在关系,对于图中的每个顶点v ∈V,都有一个非负权重w(v)代表相应工件的加工时间.我们的目标是将一部分工件分配到m台机器上,使得这些工件所对应的顶点集合构成G的一个顶点覆盖,同时使得最大完工时间(makespan)最小.针对该问题,我们首先采用分层算法选择顶点覆盖,然后结合同类机排序算法设计近似算法进行求解.当所有机器的速度都相差不大时,我们发现该算法具有较好的近似比.

2 顶点覆盖问题

给定一个无向图G=(V,E),且对于图中的每个顶点v ∈V,都有一个非负权重w(v).若存在C ⊆V,且对任意(u,v)∈E都有u ∈C或v ∈C,则称C为图G的一个顶点覆盖.顶点覆盖问题的目标是找到图G的一个顶点覆盖C,使得C中的顶点权重之和最小.

不难知道,采用原始对偶法(primal-dual)[11]或局部比值法(local ratio)[7],可以得到顶点覆盖问题的2-近似算法.1985 年,Bar-Yehuda 等[7]提出了一种基于局部比值法的-近似算法.此后,局部比值法被广泛应用于组合最优化问题中,并且该方法本身已发展为近似算法的一个统一框架[12].

下面,我们先介绍有关图的一些概念.

定义1([13]) 给定一个无向图G=(V,E),我们称G中与顶点v相关联的边的数目degG(v)为该顶点v的度.

定义2([14]) 给定一个无向图G=(V,E),且对于图中的每个顶点v ∈V,都有一个非负权重w(v).若存在常数c ＞0,使得对任意顶点v,都有w(v)=c·degG(v),则称顶点权重为度加权重,w为度加权重函数.

定义3([14]) 给定一个无向图G=(V,E),且对于图中的每个顶点v ∈V,都有一个非负权重w(v).若存在函数t(v),使得对任意顶点v,都有t(v)=c·degG(v),则称w′(v)=w(v)-t(v)为顶点的剩余权重,w′为剩余权重函数.

针对顶点覆盖问题,我们利用分层算法进行求解,策略如下.

第一轮开始:

令G0=G.

1.搜索G0的顶点,若G0中存在度为零的顶点,则将这些顶点放入集合D0并从G0中删除这些顶点.

2.计算集合VD0中每个顶点v的剩余权重,计算过程如下:

(1)令c=min

(2)计算顶点的度加权重t(v)=c·degG(v);

(3)根据度加权重计算顶点的剩余权重w′(v)=w(v)-t(v).

3.再次搜索顶点,若存在剩余权重为零的顶点,则将这些顶点放入集合C0.

第一轮结束.

当图G所有顶点的度均为零时,算法终止; 否则继续考虑由V(D0∪C0)导出的子图G1,在G1上重复第一轮的相关步骤.最后C=C0∪C1∪···∪Ck-1就是我们选择的顶点覆盖,而VC=D=D0∪D1∪···∪Dk是未被选择的顶点集合,其中k是算法从开始到结束的总轮数(k ＜n).

根据以上策略设计的分层算法具体描述如下.

在分析分层算法的近似比之前,我们先看一个引理.

引理1([14]) 给定一个无向图G=(V,E),对于图中的每个顶点v ∈V,都有一个非负权重w(v).若w为度加权重函数,则≤2OPT,其中OPT 表示顶点覆盖问题的最优顶点覆盖的总权重.

引理1 表明:在分层算法中,即使选择覆盖图G=(V,E)中的所有顶点,得到的顶点覆盖的总权重仍在最优顶点覆盖的总权重的两倍之内.由此引理,我们有以下定理.

定理1分层算法对于求解顶点覆盖问题的近似比至多为2.

证明根据分层算法,输入一个无向图G=(V,E),且对于图中的每个顶点v ∈V,都有一个非负权重w(v),算法结束时输出一个顶点集合C.设C*是图G的最小顶点覆盖.

首先,证明顶点集合C是图G的一个顶点覆盖.假设C不是G的顶点覆盖,则至少存在一条边未被覆盖,不妨设这条边为(u,v).不难发现,与该边关联的两个顶点均属于独立集D,这与degG(u)≥1（或degG(v)≥1）矛盾,从而顶点集合C为图G的一个顶点覆盖.

其次,证明顶点覆盖C中所有顶点的权重之和≤2OPT.对顶点集合V中的任意一个顶点v,有以下两种可能情形.

3 顶点覆盖约束下的同类机排序问题

3.1 LSPT 算法

对于经典的平行机排序问题,1969 年,Graham 首次提出了著名的LPT 算法[8].我们知道LPT算法是针对同速机提出的,当所有机器速度互不相同时,我们采用类似的思想,给出求解同类机排序问题的LSPT(Longest Scheduling Processing Time first)算法.

对于顶点覆盖约束下的同类机排序问题,即使找到顶点覆盖问题的最优顶点覆盖C*,然后将C*中的工件放到m台同类机上加工,得到的最大完工时间也未必是最优的.因此,为了得到一个相对满意的近似解,我们将这两个问题以及相应的算法进行结合,即通过替换策略将分层算法和LSPT 算法结合起来,给出求解该问题的一个近似算法,简记为LLSPT(Layering-Longest Scheduling Processing Time first)算法.

3.2 LLSPT 算法

下面给出LLSPT 算法.

4 LLSPT 算法的复杂度与近似比

4.1 复杂度

由LLSPT 算法知,第4 步的循环最多n次,算法的计算量主要集中在分层算法与LSPT 算法上,而前者的最大计算量为O(kn)，其中k是分层算法的循环次数(k ＜n),因此,整个算法的计算复杂度为O(n2(k+logn+m)).

4.2 近似比

定理2存在常数,使得LLSPT 算法为ρ-近似的,其中.

定理证毕.