组合优化中常见的优化问题有排序问题、最大流问题、顶点覆盖问题、指派问题、背包问题和最短路问题等，这些问题通常是被单独研究的．然而，这样已不足以解决日益复杂的现实问题，比如在某城市有道路若干，现将在一些道路的交汇处安装监控设备以监控所有的道路，并把设备的安装工作交由m个工人完成，要求尽快安装完监控，这须要将两个或者多个优化问题组合起来考虑．文献[1]首次提出顶点覆盖问题和排序问题的组合——Pm|vertex cover|Cmax(具有顶点覆盖约束的同型机排序问题)，并将该问题定义为：给定一个顶点带权重的赋权无向图，寻找此图的一个顶点覆盖并将该顶点覆盖中的每一顶点视作工件分配给m台同型机，目标是使得m台同型机的最大完工时间达到最小．文献[1]为具有顶点覆盖约束的同型机排序问题设计了一个近似比为[3-2/(m+1)]的多项式时间算法．当m=2时，文献[2]为Pm|vertex cover|Cmax设计了一个2-近似算法．当m=2,3及当m≥4时，文献[3]为具有顶点覆盖约束的同型机排序问题分别设计了一个[5/2-(2m)-1] -近似算法和一个[3-3/(m+1)] -近似算法．文献[4]对于该问题给出了一个(2+ε) -近似算法，并在m固定的情况下，给出了一个2-近似算法．文献[5]提出Q|vertex  cover|Cmax(具有顶点覆盖约束的同类机排序问题)，并为其设计了一个与机器速度和机器数有关的多项式时间算法．文献[6]将顶点覆盖约束推广为覆盖问题约束，提出Qm|covering|Cmax(具有覆盖问题约束同类机排序问题)，并给出一个与覆盖问题的近似比、机器速度和机器数有关的多项式时间算法．更多相关优化问题的组合研究见文献[7-10]．本研究考虑奖励收集顶点覆盖问题[11-12]和排序问题[13-14]的组合——具有部分顶点覆盖约束的同型机排序问题．给定一个赋权无向图，顶点和边上均有权重，寻找该图的一个部分顶点覆盖C并将每一j∈C视作工件分配给m台同型机，目标是使m台同型机的最大完工时间与所有未被覆盖的边的权重之和达到最小．当边的权重足够大时，奖励收集顶点覆盖问题就是顶点覆盖问题，所以具有部分顶点覆盖约束的同型机排序问题是具有顶点覆盖约束的同型机排序问题的推广．文献[1]指出即使分别求出排序问题和顶点覆盖问题的最优解，也无法保证Pm|vertex  cover|Cmax有较好的结果，显然具有顶点覆盖约束的同型机排序问题也有此结论，所以当研究该问题时必须将排序问题和奖励收集顶点覆盖问题放在一起考虑，通过这两个子问题的一些特殊性质设计出较好的算法．本研究首先介绍具有部分顶点覆盖约束的同型机排序问题，给出相应的线性规划，并简单介绍局部比值法和LS算法；其次考虑机器数m不固定的情形，给出一个多项式时间算法并证明其近似比为(3+ε)；然后考虑机器数m固定的情形，给出一个多项式时间算法并证明其近似比为2；最后总结本研究的结果并阐述未来研究方向．1 问题描述给定赋权无向图G=(V,E;ω,π)，其中：V为顶点集合，|V|=n；E为边集合；ω:V→R+；π:E→R+．C⊆V为图G的一个部分顶点覆盖，覆盖的边集为F={(a,b)∈E|a∈C或b∈C}，D=E\F为未被覆盖的边集，将C中每一个顶点j视作一个工件分配到m台同型机M1,M2,⋯,Mm中的某台机器上加工，记M={M1,M2,⋯,Mm}．工件j的加工时间为ω(j)，未被覆盖的边e∈D将产生一个惩罚费用π(e)．寻找图G的一个部分顶点覆盖C及关于工件集C的一个安排方案B:C→M，若B(j)=i，则将工件j分配给机器i加工．记在安排方案B下，m台同型机的最大完工时间为Cmax=maxi∈M∑j:B(j)=iω(j)，所有未被覆盖的边的惩罚费用和为π(D)=∑e∈Dπ(e)，目标是使Cmax+π(D)达到最小．给出具有部分顶点覆盖约束的同型机排序问题的线性规划并记为LP-IPCVC，即：minT；s.t.∑i=0mXij=1  (∀j=1,2,⋯,n),                                  (1)∑j=1nω(j)Xij+∑e∈Eπ(e)Xe≤T  (∀i∈M),         (2)∑i=1mXij1+∑i=1mXij2+Xe≥1  (∀e={j1,j2}∈E),  (3)Xij∈{0,1},Xe∈{0,1}  (∀i,j,e),                    (4)式中T为机器的最大完工时间与所有未被覆盖的边的惩罚费用之和．对任意j∈{1,2,⋯,n}和任意i∈M，当工件j分配给机器i加工时，Xij=1；否则Xij=0．当工件j未被分配给任何机器时，X0j=1；否则X0j=0．对任意e∈E，当e未被覆盖时，Xe=1；否则Xe=0．式(1)和式(4)表示对图G任意一个顶点对应的工件j，要么它不在任何一台机器上加工，要么它只在一台机器上加工；式(2)表示任意一台机器的完工时间与所有未被覆盖的边的惩罚费用之和不大于T；式(3)表示对图G任意一条边e={j1,j2}∈E，该线性规划要么选择点j1或点j2来覆盖边e，要么惩罚边e．给出具有部分顶点覆盖约束的同型机排序问题的一个实例．例1 给定赋权无向图G=(V,E;ω,π)(见图1，图中括号内的数为它们相应的权重，V={v1,v2,…,v9}，E={e1,e2,…,e10})和两台同型机M1,M2，记M={M1,M2}．寻找图G的一个部分顶点覆盖C及关于C的一个安排方案B：C→M．在方案B下，记机器的最大完工时间为Cmax=maxi∈M∑j:B(j)=iω(j)，所有未被覆盖的边的惩罚费用和为π(D)=∑e∈Dπ(e)，目标使Cmax+π(D)达到最小．10.13245/j.hust.241110.F001图1赋权无向图G通过计算可知例1有最优解：C={v1,v2}，B(v1)=M1，B(v2)=M2，即选择C={v1,v2}为图G的一个部分顶点覆盖，它所覆盖的边集为F={e1,e2,e3,e4,e5,e6,e7}，未被覆盖的边集为D={e8,e9,e10}．将工件v1分配给机器M1，工件v2分配给机器M2．此时，Cmax=max{2,4}=4，π(D)=∑e∈Dπ(e)=2+1+1=4，最优值为Cmax+π(D)=4+4=8．2 PCVC问题的局部比值法和同型机排序的LS算法本研究算法以局部比值法和LS算法为基础．算法1 PCVC问题的局部比值法[12]输入 赋权无向图G=(V,E;ω,π)，其中：ω:V→R+；π:E→R+输出 图G的一个部分顶点覆盖C及未被覆盖的边集D步骤1 置C=∅，D=∅，c=+∞．步骤2 当存在一条边e=(u,v)∈E时，使得min{ω(u),ω(v),π(e)}0，则执行步骤3；否则执行步骤5．步骤3 c=min{ω(u),ω(v),π(e)}．步骤4 ω(u)←ω(u)-c，ω(v)←ω(v)-c，π(e)←π(e)-c．步骤5 输出C={u|ω(u)=0}，D={e=(u，v)|ω(u)0,ω(v)0}．引理1[12] 算法1是PCVC问题的一个2-近似算法．LS算法是将当前工件分配给负载最小的机器．3 机器数m不固定时的具有部分顶点覆盖约束的同型机排序问题本研究考虑机器数m不固定的情形，给出具有部分顶点覆盖约束的同型机排序问题的一个(3+ε)-近似算法．算法的策略是对于图G的任意一个顶点v∈V，若ω(v)过大，则调整ω(v)为足够大以避免v对应的工件出现在须要被加工的工件集里．对调整过权重后得到的新图调用PCVC问题的局部比值法，得到新图的一个顶点子集(工件集)和未被覆盖的边集．对得到的工件集运用LS算法，最终得到所有工件的分配方案及所有未被覆盖的边集．对任意小的固定正常数ε，令ti=(1+ε)i，其中i=1,2,⋯,k，k=log(1+ε)∑v∈Vω(v)．Gi表示图G的顶点权重ω经过ti调整后得到的新图，ωi表示图Gi新的顶点权重．Ci和Di分别对应对图Gi调用算法1后选中的顶点集(工件集)和未覆盖的边集，(S1i,S2i,⋯,Smi)和Cmaxi分别对应当前调度中的分配方案和机器的最大完工时间，π(Di)=∑e∈Diπ(e)，Ti=Cmaxi+π(Di)．C˜i和D˜i分别对应图Gi的PCVC问题最优解选中的顶点集(工件集)和未覆盖的边集．T为算法输出的机器的最大完工时间与所有未被覆盖边的惩罚费用之和，(S1,S2,⋯,Sm)为算法输出的分配方案．C*和D*分别对应该问题最优解选中的顶点集(工件集)和未覆盖的边集．T*为该问题的最优值．方便起见，不妨设给定无向图中不存在权重小于1的顶点和边，因此T*≥1．注意到当选中图中全部顶点并将其视作工件，将全部工件分配给m台同型机时产生的解为该问题的一个可行解，所以该问题的最优值不大于图中所有顶点权重之和，即T*≤∑v∈Vω(v)．算法2 当机器数m不固定时的具有部分顶点覆盖约束的同型机排序问题算法输入 赋权无向图G=(V,E;ω,π)及m(m不固定)台同型机M={M1,M2,⋯,Mm}，其中：ω:V→R+；π:E→R+输出 机器的最大完工时间与所有未被覆盖边的惩罚费用之和T及工件的分配方案(S1,S2,⋯,Sm)步骤1 对任意小的固定常数ε0，令k=log(1+ε)∑v∈Vω(v)．步骤2 初始化i=1,并执行以下循环．步骤3 令ti=(1+ε)i．对∀v∈V，若ω(v)ti，令ωi(v)=+∞；否则令ωi(v)=ω(v)/m．步骤4 令Gi=(V,E;ωi,π)，对图Gi调用算法1得到Ci和Di．步骤5 调用LS算法将Ci中工件按原加工时间分配至m台同型机上，记该分配为(S1i,S2i,⋯,Smi)，机器的最大完工时间为Cmaxi．步骤6 令Ti=Cmaxi+π(Di)．若i  k，则令i = i + 1，并返回步骤3；否则执行步骤7．步骤7 记T=Th=mini∈{1,2,⋯,k}Ti，(S1,S2,⋯，Sm)=(S1h,S2h,⋯,Smh)．输出T和(S1,S2,⋯，Sm)．无论ti取何值，算法1都返回图Gi的PCVC问题的一个可行解，该可行解也是图G的一个部分顶点覆盖．LS算法返回选中的顶点的一个安排方案，因此算法2每次循环均能返回具有部分顶点覆盖约束的同型机排序问题的一个可行解．算法1在Ο(|E|)时间内完成，LS算法在Ο(nlogm)时间内完成，注意到该算法有k次循环，因此算法2的时间复杂度为Ο(max{k|E|,knlogm})．定理1 算法2是机器数m不固定时的具有部分顶点覆盖约束的同型机排序问题的一个(3+ε)-近似算法，其中ε0为任意小的固定常数．证明 T为算法的返回值，因为算法输出所有可行解中最小的Ti，所以对任意Ti都有T≤Ti．T*为该问题的最优值．由T*≤∑v∈Vω(v)知，∃τ∈{1,2,⋯,k}，满足T*∈[(1+ε)τ-1,(1+ε)τ]．记tτ=(1+ε)τ，则有T*≤tτ≤(1+ε)T*．考虑tτ，对应的目标值为Tτ，有T≤Tτ=Cmaxτ+π(Dτ)≤ω(Cτ)/m+maxv∈Cτω(v)+π(Dτ)≤ωτ(Cτ)+tτ+π(Dτ)≤2(ωτ(C˜τ)+π(D˜τ))+tτ≤2(ωτ(C*)+π(D*))+tτ≤2(ω(C*)/m+π(D*))+tτ≤2T*+(1+ε)T*≤(3+ε)T*.第4个不等号由引理1可得．综上，算法2是机器数m不固定时的具有部分顶点覆盖约束的同型机排序问题的一个(3+ε)-近似算法．4 机器数m固定时的具有部分顶点覆盖约束的同型机排序问题本研究考虑机器数m固定的情形，给出具有部分顶点覆盖约束的同型机排序问题的一个2-近似算法．首先对于给定的赋权无向图，任意选中至多m个顶点并将其视作“大工件”(用向量s表示)，猜测出这些“大工件”构成的“大工件集”的分配方案(用向量z表示)．对每一次选中的“大工件”，将“大工件集”对应的顶点及与这些顶点相关联的边从原图中删去，然后调整剩余图中顶点的权重．对得到的新图调用算法1，得到新图的一个部分顶点覆盖(“小工件集”)和未被覆盖的边集．运用LS算法将“小工件集”中的工件分配到已经分配完“大工件集”的m台机器上，最终得到所有工件的分配方案及所有未被覆盖的边．G'=(V',E';ω',π)表示当前方案中删除图G的部分顶点和部分边且余下顶点的权重经过调整后得到的新图，其中：V'为图G'的顶点集；E'为图G'的边集；ω':V'→R+．C'和D'分别对应当前方案中对图G'调用算法1后选中的顶点集(“小工件集”)和未覆盖的边集，π(D')=∑e∈D'π(e)．令H=∪si0{si}，其中H为当前方案中所有“大工件”构成的“大工件集”．(A1',A2',⋯,Am')为其分配方案，Lmax'为机器的最大完工时间，N'=Lmax'+π(E')；C'⋃H表示当前方案中所有工件构成的集合，(S1',S2',⋯,Sm')为其分配方案，Cmax'为机器的最大完工时间，T'=Cmax'+π(D')．Δ为当前方案中所有“大工件”的加工时间之和，δ为当前方案中加工时间最小的“大工件”的加工时间．T*为该问题的最优值．C*和D*分别对应该问题最优解选中的顶点集(工件集)和未被覆盖的边集，记Copt为C*中权重较小的顶点构成的集合．算法3 当机器数m固定时的具有部分顶点覆盖约束的同型机排序问题算法输入 赋权无向图G=(V,E;ω,π)及m(m固定)台同型机M={M1,M2,⋯,Mm}，其中：ω:V→R+；π:E→R+输出 机器的最大完工时间与所有未被覆盖边的惩罚费用之和T及工件的分配方案(S1,S2,⋯，Sm)步骤1 初始化Qs=∅，Qz=∅．步骤2 对所有s ∈ S={(s1, s2,⋯,sm) | si ∈{0,1,⋯,n}，且∀si,sj∈{0,1,⋯,n},当i≠j 时有si≠sj}，令H=∪si0{si}．取Qs=Qs⋃{s}.步骤3 对所有z∈Z={(z1,z2,⋯,zm) | zi ∈{0,1,⋯,m},zi=0当且仅当si=0}．取Qz=Qz ⋃{z}．步骤4 令Δ=∑i:si0ω(si),δ=mini:si0ω(si)．步骤5 对∀i=1,2,⋯,m，若si0，则将工件si分配给机器zi，在原图G中删除顶点si及与之相关联的边．记剩下的顶点集为V'，剩下的边集为E'．对∀v∈V'，若ω(v)δ，则令ω'(v)=+∞；否则令ω'(v)=ω(v)/m．步骤6 令G'=(V',E';ω',π)，对图G'调用算法1得到C'和D'．步骤7 调用LS算法，将C'中工件按原加工时间分配到m台机器上(在之前的步骤中，工件集H已被分配到这m台机器上)，记C'⋃H的分配方案为(S1',S2',⋯,Sm')，机器的最大完工时间为Cmax'，令T'=Cmax'+π(D')．步骤8 记H的分配方案为(A1',A2',⋯,Am')，机器的最大完工时间为L'max．令N'=L'max+π(E')．步骤9 若N'≤T'，则令(S1',S2',⋯,Sm')←(A1',A2',⋯,Am')，T'←N'，Cmax'←L'max．若Qz≠Z，则返回步骤3；若Qz=Z且Qs≠S，则返回步骤2；否则执行步骤10．步骤10 记T=minT'，对应分配方案为(S1,S2,⋯,Sm)．输出T和(S1,S2,⋯,Sm)．无论s取何值，算法1都返回图G'的PCVC问题的一个可行解，该可行解也是图G的一个部分顶点覆盖．LS算法返回选中的顶点的一个安排方案，因此算法3每次循环均能返回具有部分顶点覆盖约束的同型机排序问题的一个可行解．对每一个向量s处理的过程记为一次循环，对每一向量对s和z处理的过程记为一次子循环，则总子循环的次数为Ο((n+1)m(m+1)m)，其中m为常数．对于每一个给定的s，G'在线性时间内得到，算法1在Ο(|E|)时间内完成，LS算法在Ο(nlogm)时间内完成．因此，算法3的时间复杂度为Ο(max{|E|(n+1)m(m+1)m,nlogm(n+1)m(m+1)m}).定理2 算法3是机器数m固定时的具有部分顶点覆盖约束的同型机排序问题的一个2-近似算法．证明 给定一个输入G=(V,E;ω,π)，该问题最优解选择的顶点集为C*，Copt为C*中权重较小的顶点构成的集合．将C*中工件按其加工时间进行非增排序，令m˜=min{m,|C*|}，记C*中前m˜个工件为μ1,μ2,⋯,μm˜(即对i=1,2,⋯,m˜，有μi∈C*，ω(μ1)≥ω(μ2)≥⋯≥ω(μm˜)．当m˜=m时，对∀j∈C*\{μ1,μ2,⋯,μm˜}，有ω(j)≤ω(μm˜))．定义向量(s1*,s2*,⋯,sm*)如下：对∀i∈{1,2,⋯,m˜}，令si*=μi；若m˜m，则对∀i∈{m˜+1,m˜+2,⋯,m}，令si*=0．定义向量(z1*,z2*,⋯,zm*)如下：对∀i∈{1,2,⋯,m˜}，最优解将工件si*分配给机器zi*；若m˜m，则对∀i∈{m˜+1,m˜+2,⋯,m}，令zi*=0．考虑某一子循环，其中：s=(s1,s2,⋯,sm)=(s1*,s2*,⋯,sm*)=s*；z=(z1,z2,⋯,zm)=(z1*,z2*,⋯,zm*)=z*．当m˜=|C*|≤m时，该算法返回最优解；当m˜=m≤|C*|时，记Gτ为此次子循环产生的新图，Cτ和Dτ分别对应对图Gτ调用算法1得到的顶点集和未被覆盖的边集，j'为Cτ中加工时间最大的工件，ω(j')为工件j'的加工时间，Cmaxτ为此次子循环机器的最大完工时间，Tτ为此次子循环机器的最大完工时间与所有未覆盖的边的惩罚费用之和．C˜τ和D˜τ分别对应图Gτ的PCVC问题最优解中选中的顶点集和未覆盖的边集．根据Gτ，Δ和δ的定义，有ω(j')≤δ;Δ≥mδ(即Δ/m≥δ)．LS算法的完工时间至多是调度工件总加工时间的1/m加上Cτ中加工时间最大的工件的加工时间的(1-1/m)[4]．记T*为该问题的最优值，有T≤Tτ=Cmaxτ+π(Dτ)≤(1/m)(Δ+ω(Cτ))+(1-1/m)ω(j')+π(Dτ)=Δ/m+ω(Cτ)/m)+π(Dτ)+(1-1/m)ω(j')=Δ/m+(ω'(Cτ)+π(Dτ))+(1-1/m)ω(j')≤Δ/m+2(ω'(C˜τ)+π(D˜τ))+(1-1/m)ω(j')≤Δ/m+2(ω'(Copt)+π(D*))+(1-1/m)ω(j')=Δ/m+2(ω(Copt)/m+π(D*))+(1-1/m)⋅ω(j')≤Δ/m+2ω(Copt)/m+2π(D*)+(1-1/m)δ≤Δ/m+2ω(Copt)/m+2π(D*)+δ≤2(Δ/m+ω(Copt)/m)+2π(D*)≤2T*.第3个不等号由引理1可得，倒数第4个不等号由ω(j')≤δ可得，倒数第2个不等号由Δ/m≥δ可得．综上，算法3是机器数m固定时的具有部分顶点覆盖约束的同型机排序问题的一个2-近似算法．5 结语对于机器数不固定时的具有部分顶点覆盖约束的同型机排序问题，给出了一个(3+ε)-近似算法；对于机器数固定时的具有部分顶点覆盖约束的同型机排序问题，给出了一个2-近似算法．基于文献[15-16]，未来可以考虑研究作业车间调度与顶点覆盖的组合型问题．