在非同型机平行机排序问题(简记为R||Cmax)中，设有n个工件和m台机器，每个工件j安排在机器i上的加工时间为pij，将n个工件安排在m台机器上，使得最大完工时间达到最小，对该问题设计最好的近似算法是调度领域中最具挑战性的问题之一．受航班时刻表问题的启发，文献[1]提出了图均衡问题，对于边赋权多重无向图中的边进行定向，使得所有顶点中的最大负载达到最小，其中顶点的负载是以该顶点为起点的边的总权重．若把图均衡问题实例中的顶点对应机器，边对应工件，每个工件可以分配到其顶点对应的两台机器，则图均衡问题可归约为R||Cmax的一个特殊情况．文献[2]指出图均衡问题是无关平行机排序问题的其中一种最简单的情况，该问题是(1.5-ε)-不可近似的．图均衡问题也被称为图定向问题，文献[3]对于具有边权重限制的图定向问题给出了几个不可近似结果和近似算法．文献[1]给出了图均衡问题的1.75-近似算法，并且证明了该问题不存在(1.5-ε)-近似算法，除非P=NP．文献[2]证明了图均衡问题构造的线性规划(LP)的整数间隙至多为1.749，这意味着可能存在基于LP的近似比低于1.75的近似算法．文献[4]设计了一个简单的11/6-近似算法．对于仅有两种边权重的特殊情况，存在1.5-近似算法[5-6]，更多相关结果参考文献[7]．文献[8]介绍了图均衡问题的另一种形式，称为最大最小加权出度图定向问题(MaxMinO)，对边赋权无向图中的每条边指定方向，使得所有顶点中最小的加权出度达到最大．文献[8]证明了除非P=NP，对于任意常数ε0，MaxMinO不存在(2-ε)-近似算法．MaxMinO可看作非同型机上最大最小均衡问题的一个特殊情况[9]，即每个工件最多能分配在两台机器上(在不同机器上的加工时间可以不同)．文献[9]对MaxMinO设计了一个最优的2-近似算法．MaxMinO也是限制性最大最小公平分配问题的特殊情况[10]，该问题具有常数近似算法，更多相关结果参考文献[11]．近年来，学者对路上的组合优化问题研究较多[12-14]．本研究针对路上的在线最大最小图均衡问题(MMGB)进行探讨，对于边权不可分的情形，证明了即使最大权重或总权重已知，任何算法都没有有限的竞争比，对于边权可分的情形，给出了相应的最优在线算法．1 问题模型最大最小图均衡问题也被称为最大最小加权出度图定向问题[8]，定义为：给定边赋权多重无向图G=(V，E，w)，其中V为顶点集合，E为边集合，权重w:E↦Z+，Z+为正整数集．G的一个定向Λ指定义在E上的一个函数Λ:{u,v}→{(u,v),(v,u)}，即对于每条无向边{u，v}∈E指定一个方向．对于G的一个定向Λ，顶点v∈V的加权出度dΛ是指以v为起点的边的权重之和，即dΛ(v)=∑{u,v}∈E,Λ({u,v})=v,uw({u,v})．最小加权出度δΛ(G)=minv∈VdΛ(v)，其目标是找到图的一个最小加权出度达到最大的定向．在线(半在线)算法A的性能用竞争比来衡量．给定一个实例，令CA为算法A得到的目标值，COPT为离线情况下的最优值．对于最大化问题的任何输入实例，满足COPT ≤cCA的最小c称为A的竞争比．若不存在竞争比小于下界ρ的在线(半在线)算法，则称在线(半在线)问题具有下界ρ．若在线(半在线)算法A的竞争比达到了问题的下界，则算法A称为最优算法．给定路P=(V，E，w)，其中：V={0，1，…，n}；E为e={k-1，k}(k=1，2，…，n)的多重边集合．把P上的MMGB问题分为不可分和可分两种情形进行研究，不可分情形指边权只能分配给一个顶点，可分情形指边权可以分开分配给两个顶点．令wmax=maxe∈Ew(e)为最大权重，W=∑e∈Ew(e)为边的总权重．用wj表示边ej的权重．2 不可分情形考虑边权不可分的情形，当n=1时，路上的在线MMGB问题为文献[15]中研究的问题，该问题存在竞争比为2的最优在线算法．当n≥2时，证明即使最大权重或总权重已知，任何算法都没有有限的竞争比．定理1 当n=2且最大权重wmax已知时，路上MMGB问题的任一在线算法没有有限的竞争比．证明 假设n=2，考虑算法A和下列边序列．第一条边e1={0，1}，w1=1．若Λ(e1)=(1，0)，则最后两条边e2=e3={1，2}，w2=w3=1，得CA=0，COPT=1，其中最优解Λ*为Λ*(e1)=(0，1)，Λ*(e2)=(1，2)，Λ*(e3)=(2，1)，故ρ=∞．若Λ(e1)=(0，1)，则第二条边e2={0，1}，w2=wmax，这里wmax为足够大的数．若Λ(e2)=(0，1)，则最后一条边e3={1，2}，w3=1，得CA=0，COPT=1，故ρ=∞．若Λ(e2)=(1，0)，则最后两条边e3=e4={1，2}，w3=w4=wmax，得CA≤1，COPT=wmax，随着wmax的增加，有ρ≥wmax→∞．定理2 当n≥3且总权重W已知时，这里W的取值与n有关，路上MMGB问题的任一在线算法没有有限的竞争比．证明 假设W=n+1，wj=1(∀j)．考虑算法A和下列边序列．第一条边e1={1，2}．若Λ(e1)=(1，2)，则再来n条边：e2=e3={0，1}，ej={j-2，j-1}(j=4，5，…，n+1)，得CA=0，COPT=1，故ρ=∞．若Λ(e1)=(2，1)，则再来n条边：e2={0，1}，ej={j-1，j}(j=3，4，…，n)，en+1={n-1，n}，得CA=0，COPT=1，故ρ=∞．定理3 当n=2且总权重W已知时，路上MMGB问题的任一在线算法没有有限的竞争比．证明 假设W为足够大的正数，考虑算法A和下列边序列．第一条边e1={0，1}，w1=W/3．若Λ(e1)=(1，0)，则最后两条边e2=e3={1，2}，w2=W/3，w3=W-2W/3，得CA=0，COPT=W/3，故ρ=∞．若Λ(e1)=(0，1)，则第二条边e2={0，1}，w2=W/3．若Λ(e2)=(0，1)，则最后一条边e3={1，2}，w3=2W/3-W/3，得CA=0，COPT=W/3，故ρ=∞．若Λ(e2)=(1，0)，则最后两条边e3=e4={1，2}，w3=W/3-W/3，w4=W/3，得CA≤W/3，COPT=W/3，其中最优解为Λ*(e1)=(1，0)，Λ*(e2)=(0，1)，Λ*(e3)=(1，2)，Λ*(e4)=(2，1)，故随着W的增加，有ρ≥W/3→∞．3 可分情形考虑边权可分的情形，即边权可以分开分配给两个顶点．对每一条边ej引入变量xj∈[0,wj]，xj为边ej={i-1，i}分配给(i-1，i)方向的权重．xj=wj意味着Λ({i-1，i})=(i-1，i)，xj=0意味着Λ({i-1，i})=(i，i-1)．顶点i的加权出度定义为dΛ(i)=∑j:ej={0,1}xj   (i=0);∑j:ej={i,i+1}xj+∑j:ej={i-1,i}(wj-xj)   (i=1,2,…,n-1);∑j:ej={n-1,n}(wj-xj)   (i=n). (1)对于k=1,2,…,n，令Wk为所有边{k-1，k}的权重之和，即Wk=∑j:ej=k-1,kwj，显然W1≥COPT，Wn≥COPT，Wk+Wk+1≥COPT，∀k=1，2,…,n-1．令Λ为由本节中算法产生的可行解，minidΛ(i)为Λ的目标值，针对n≥2的可分情形设计了算法1．算法1当边ej={i-1，i}到达时：令xj=wj/2．定理4 算法1的竞争比至多为2．证明 在任意可行解中，i的加权出度至多为Wi+Wi+1，此为COPT的一个上界．由算法1有dΛ(i)=∑j:ej=i,i+1wj/2+∑j:ej=i-1,i(wj-wj/2)≥COPT/2．顶点0的加权出度至多为W1，由算法1有dΛ(0)=∑j:ej=0,1xj=W1/2≥COPT/2．同样地，dΛ(n)≥COPT/2．证毕．3.1　在n≥3的情况下定理5 当n≥5且W已知时，路上MMGB问题的任一算法的竞争比至少为2．证明 假设n=5且W=12．考虑算法A和下列边序列．前三条边为e1={0，1}，e2={2，3}，e3={4，5}，w1=4，w2=2，w3=4．若x2≤1，则最后一条边e4={3，4}，w4=2．易知CA≤x2≤1，COPT=2，ρ≥2．若x21，则最后一条边e4={1，2}，w4=2．易知CA≤2-x21，COPT=2，ρ2．定理4和定理5表明：当n≥5时，无论W是否已知，算法1是路上MMGB问题的一个竞争比为2的最优算法．针对n=4时的可分情形设计了算法2．算法2当边ej={i-1，i}到达时：情况1 i=1，3，令xj=2wj/3；情况2 i=2，4，令xj=wj/3．定理6 当n=4时，算法2的竞争比至多为3/2．证明 由于在任意解中，顶点0(或4)的出度至多为W1(或W4)，即W1≥COPT，W4≥COPT．根据算法2有：dΛ(0)=2W1/3≥2COPT/3；dΛ(4)=2W4/3≥2COPT/3．由式(1)知顶点0和1的总出度不超过W1+W2，故W1+W2≥dΛ(0)+dΛ(1)≥2COPT．根据算法2有dΛ(1)=W1/3+W2/3≥2COPT/3；同样地，有dΛ(3)=W3/3+W4/3≥2COPT/3．根据式(1)，有W2+W3≥dΛ(2)≥COPT，因此有dΛ(2)=2W2/3+2W3/3≥2COPT/3．证毕．定理7 当n=4且W已知时，路上MMGB问题的任一在线算法的竞争比至少为3/2．证明 假设W=10．考虑算法A和下列边序列．前两条边为e1={1，2}，e2={2，3}，w1=w2=1．若1-x1+x2≤4/3，则最后两条边e3={0，1}，e4={3，4}，w3=w4=4，得CA≤1-x1+x2≤4/3，COPT=2，故ρ≥3/2．若1-x1+x24/3且x1≤1/3，则最后两条边e3={0，1}，e4={3，4}，w3=1，w4=7，易知CA≤(1+x1)/2≤2/3，COPT=1，故ρ≥3/2．若1-x1+x24/3且x11/3，此时x22/3，则最后两条边e3={0，1}，e4={3，4}，w3=7，w4=1，得CA≤(1+1-x2)/22/3，COPT=1，故ρ3/2．定理6和定理7表明：当n=4时，无论W是否已知，算法2是路上MMGB问题的一个竞争比为3/2的最优算法．针对n=3时的可分情形设计了算法3．算法3当边ej={i-1，i}到达时：情况1 i=1，令xj=2wj/3；情况2 i=2，令xj=wj/2；情况3 i=3，令xj=wj/3．定理8 当n=3时，算法3的竞争比至多为3/2．证明 与定理6类似，可以证明：dΛ(0)=2W1/3≥2COPT/3；dΛ(3)=2W3/3≥2COPT/3．根据式(1)，有W1+W2≥2COPT，故dΛ(1)=W1/3+W2/2≥W1/3+W2/3≥2COPT/3；同样地，dΛ(2)=W2/2+W3/3≥W2/3+W3/3≥2COPT/3．证毕．定理9 当n=3且W已知时，路上MMGB问题的任一在线算法的竞争比至少为3/2．证明 假设W=8，考虑算法A和下列边序列．第一条边为e1={0，1}，w1=2．若x1≤4/3，则最后两条边e2={1，2}，e3={2，3}，w2=4，w3=2，得CA≤x1≤4/3，COPT=2，故ρ≥3/2．若x14/3，则最后一条边e2={2，3}，w2=6，得CA≤2-x12/3，COPT=1，故ρ3/2．定理8和定理9表明：当n=3时，无论W是否已知，算法3是路上MMGB问题的一个竞争比为 3/2的最优算法．3.2　在n=2的情况下设W未知，针对n=2的可分情形设计了算法4．算法4当边ej={i-1，i}到达时：情况1 i=1，令xj=3wj /4；情况2 i=2，令xj=wj /4．定理10 当n=2时，算法4的竞争比至多为4/3．证明 由式(1)可知，W1≥COPT，W2≥COPT，(W1+W2)/3≥COPT．有：dΛ(0)=3W1/4≥3COPT/4；dΛ(2)=3W2/4≥3COPT/4；dΛ(1)=(W1+W2)/4≥3COPT/4．证毕．定理11 当n=2时，路上MMGB问题的任一在线算法的竞争比至少为4/3．证明 考虑算法A和下列边序列．第一条边为e1={0，1}，w1=2．若x1≤3/2，则最后一条边e2={1，2}，w2=4，得CA≤x1≤3/2，COPT=2，故ρ≥4/3．若x13/2，则最后一条边e2={1，2}，w2=1，得CA≤(2-x1+1)/23/4，COPT=1，故ρ4/3．定理10和定理11表明：当n=2时，算法4是路上MMGB问题的一个竞争比为4/3的最优算法．当n=2且W已知时，对于可分情形设计了半在线算法5．令dΛ(i，j)为前j条边定向后顶点i的加权出度，初始化dΛ(i，0)=0，i=0，1，2．算法5当边ej={i-1，i}到达时：情况1 i=1，令xj=min{W/3-dΛ(0，j-1)，wj}，计算dΛ(i，j)；情况2 i=2，令xj=wj-min{W/3-dΛ(2，j-1)，wj}，计算dΛ(i，j)．定理12 当n=2且W已知时，算法5是路上MMGB问题的一个最优算法．证明 当算法停止时，有：dΛ(0)=min{W/3,W1}≥COPT；dΛ(2)=min{W/3,W2}≥COPT；dΛ(1)=W-dΛ(0)-dΛ(2)≥COPT．即所有顶点的加权出度至少为COPT，这意味着算法5得到的解为最优解．4 结语研究路上在线MMGB问题，对于边权不可分的情形，在路的长度为2，且总权重已知或最大权重已知的情况下，该问题没有有限的竞争比．对于边权可分的情形，当n≥3时，总权重是否已知均不会改变路上最大最小图均衡问题的竞争比下界；当n=2时，总权重是否已知将令问题具有不同的竞争比下界.针对不同的n，本研究分别设计了最优在线算法．对于MMGB问题，未来可以考虑拓广到其他特殊图上，例如研究星图、圈图、仙人掌图和立方图上的MMGB问题的最优在线(半在线)算法．