多目標排序中的幾個結果.pdf

1、本文的工作是Baker，Smith，Agentis等人的研究工作的發(fā)展。研究的目標函數(shù)有Cmax，∑Cj，Lmax，maxWjCj，∑WjCj以及maxVj。主要結果如下：定理1問題1‖∑Cj+maxW′iC′i是多項式時間可解的，算法如下：Step1令u：=n1，v：=n2，F(xiàn)：=0.Step2如果u=0，則定義π(i)=J′i，1≤i≤v，停止.Step3如果v=0，則定義π(i)=Ji，1≤i≤u，令F：=F+∑t(i，0)，停止

2、.Step4若maxW′vt(u，v)＞y，則定義π(u+v)=Ju，令u：=u-1，F(xiàn)：=F+t(u，v)；轉(zhuǎn)Step2.若maxW′vt(u，v)≤y，則定義π(u+v)=J′v，令v：=v-1；轉(zhuǎn)Step2。定理2問題1‖∑Ci：maxW′iC′i是多項式時間可解的，算法如下：Step1令u：=n1，v：=n2.Step2若u=0，則定義π(i)=J′i，1≤i≤v，停止.Step3若v=0，則定義π(i)=Ji，1≤i≤u，停止

3、.Step4若maxW′ct(u，v)＞y，則定義π(u+v)=Ju，令u：=u-1轉(zhuǎn)Step2.若maxW′vt(u，v)≤y，則定義π(u+v)=J′v，令v：=v-1；轉(zhuǎn)Step2。定理3問題1‖∑WjCj+maxW′jC′j是強NP-困難的。定理4問題1‖∑WjCj≤Q：∑V′j≤0是強NP-困難的。定理5問題1‖∑WjCj+WmaxVj是強NP-困難的。定理6問題1‖(C(1)max，C(2)max，…，C(k-1)max，L