使带权总完工时间为最小的自由作业排序问题

274201008CHINESEJOURNALOFENGINEERINGMATHEMATICSVol.27No.4Aug.2010:1005-3085(2010)04-0612-09¤1,2(1-213002;2-201209):::AMS(2000)90B35;90C27:O224:A1[1]mM1;M2;¢¢¢;Mmnf1;2;¢¢¢;ngMij()Oijpij()Om°°nXj=1wjCj;Om°°mXi=1wMiCMi;Cj;CMijMiwj;wMijMijiNPAchugbueChin[2]O2°°nXj=1CjNPNPTimkovsky[3]1998O2jpij=1;chains¯¯nXj=1wjCj;O3jpij=1;chains¯¯nXj=1wjCj:2008-04-21.:(19713)..¤:()(70731160015)(yw06037).4613NP[4-6]Ojpij=1;outtree¯¯nXj=1Cj;O2jpij=1;tree¯¯nXj=1Cj;Omjpij=1;rj¯¯nXj=1Cj;O¯¯pij=1¯¯nXj=1wjCj:OmkPnj=1wjCjOmkPmi=1wMiCMiSMiQ=[B;C)(MiQ=[B;C)Mi)CMiQtMiSSAnnaRaczmany[7]1982[8,9]2Om°°mXi=1wMiCMi;Om°°nXj=1wjCj1233442OmkmPi=1wMiCMiOmknPj=1wjCj2.1OmkmPi=1wMiCMiOmkPmi=1wMiCMiwMi;CMi;i=1;2;¢¢¢;mMi1C¤Mi¸Li;i=1;2;¢¢¢;mC¤MiLi=nXj=1pij;i=1;2;¢¢¢;m:2maxi=1;2;¢¢¢;mC¤Mi¸maxj=1;2;¢¢¢;npjpj=mXi=1pij;j=1;2;¢¢¢;n:614273mPi=1C¤Mi¸nPj=1pj.4CMi=Li+¿i·Li+minj2Gifpj¡pijg;i=1;2;¢¢¢;m;GiMiMi¿iMimXi=1C¤Mi·mXi=1CMi=mXi=1Li+mXi=1¿i:(1)MiMij2Gi¿i·pj¡pij¿i·minj2Gifpj¡pijg:1OmkPmi=1CMiMi;Mk;i;k=1;2;¢¢¢;m£0;mini;kfCMi;CMkg¤2mXi=1¿i·mXi=1Li;(1)13mXi=1C¤Mi·mXi=1CMi·2mXi=1Li·2mXi=1C¤Mi:1OmkPmi=1wMiCMimPi=1wMiminfwM1;wM2;¢¢¢;wMmgCM1=L1+¿1·L1+p2;j1+¢¢¢+pm¡1;j1+pm;j1;¢¢¢CMm=Lm+¿m·Lm+p1;jm+¢¢¢+pm¡1;jm;4615ji2Gi;i=1;2;¢¢¢;mGiMimXi=1wMiC¤Mi·mXi=1wMiCMi·mXi=1wMiLi+mXk=1³Xi6=kwMi´Lk=³mXi=1wMi´³mXi=1Li´·mPi=1wMiminfwM1;wM2;¢¢¢;wMmg³mXi=1wMiC¤Mi´:OmkPmi=1wMiCMiwM1wM2·¢¢¢·wMmp1;1=p;p2;1=¢¢¢=pm;1=SmXi=1wMiCMi=mXi=1wMi¡p+(i¡1)¢:^SmXi=1wMi^CMi=mXi=2(m+1¡i)wMi+wM1¡p+(m¡1)¢;^CMiMi^SmPi=1wMiCMimPi=1wMiC¤Mi¸mPi=1wMiCMimPi=1wMi^CMi=mPi=1wMi(p+(i¡1))mPi=2(m+1¡i)wMi+wM1(p+(m¡1))¡!mPi=1wMiwM1(!0):2.2OmknPj=1wjCjwj;Cj;j=1;2;¢¢¢;nj1C¤j¸pj;j=1;2;¢¢¢;nC¤j2nPj=1C¤j¸nPj=1pj=mPi=1Li.3jCj=pj+X¿ij;(2)¿ijOijj¿ij·Li¡pij:(3)2OmkPnj=1wjCjnPj=1wjminfw1;w2;¢¢¢;wng;61627(2),(3)Cj·pj+mXi=1(Li¡pij);nXj=1wjCj·nXj=1wjpj+³nXj=1wj´³mXi=1Li´¡nXj=1³wjmXi=1pij´=³nXj=1wj´³nXj=1pj´·nPj=1wjminfw1;w2;¢¢¢;wngnXj=1wjpj:p1;1=1;pi;1=;i=1;2;¢¢¢;m;p1;j=;pi;j=0;i=2;¢¢¢;m;j=2;¢¢¢;n;w1·w2·¢¢¢·wnn¸m2;¢¢¢;n1^SnXj=1wj^Cj=w1+hw1(n¡1)+nXi=2(i¡1)wii;12;3;¢¢¢;nSnXj=1wjCj=nXi=1wi+h(m¡1)w1+nXi=2(i¡1)wii;nPj=1wjCjnPj=1wj^Cj¡!nPj=1wjminfw1;w2;¢¢¢;wng(!0):3OmjrjjmPi=1wMiCMiOmjrjjnPj=1wjCj3.1OmjrjjmPi=1wMiCMijrj;j=1;2;¢¢¢;nPmi=1wMiCMiwMi;CMi;i=1;2;¢¢¢;mMiMiwM1¸wM2¸¢¢¢¸wMmCijOij[j]j4617CMi=Ci[n];i=1;2;¢¢¢;mOmjrjjPmi=1wMiCi[n][10]Xj2ApjCj¸12³³Xj2Apj´2+Xj2Ap2j´;8AµN;(4)ANCjjpjA=f1;2;¢¢¢;jgpjCj¸12³jXk=1pk´2+12jXk=1p2k¡j¡1Xk=1pkCk¸12³jXk=1pk´2+12jXk=1p2k¡j¡1Xk=1pkCj;jXk=1pk·2Cj¡jPk=1p2kjPk=1pk·2Cj¡jPk=1pkj;jXk=1pk·21+1jCj:(5)(5)(4)OmjrjjPmi=1wMiCMi8:minmPi=1wMiCLPi[n]s:t:P[j]2Aph[j]CLPh[j]¸12³³P[j]2Aph[j]´2+P[j]2Ap2h[j]´;8AµN;h=1;2;¢¢¢;m;CLPh[j]¸CLP(h¡1)[j]+ph[j];h=2;¢¢¢;m;j=1;¢¢¢;n;CLP1j¸rj+p1j;j=1;¢¢¢;n;(6)CLPij(6)Oij(6)fCLPij:i=1;2;¢¢¢;m;j=1;2;¢¢¢;ngII1)CLPm[1]·CLPm[2]·¢¢¢·CLPm[n]2)(1;2;¢¢¢;n)3OmjrjjPmi=1wMiCMiI3mrj=02mCHijIOijCHhn·CH1n+hXi=2nXk=1pik;h=2;3;¢¢¢;m;(7)CH1n·maxjrj+nXk=1p1k·CLP1n+n¡1Xk=1p1k:(8)61827(5)(7),(8)CHhn·CH1n+hXi=221+1nCLPin;h=2;3;¢¢¢;n;CH1n·CLP1n³1+21+1n¡1´:W(H)=mXi=1wMiCHMi=wM1CH1n+mXh=2wMhCHhn·wM1CH1n+mXh=2wMh³CH1n+hXi=221+1nCLPin´·³mXh=1wMh´³1+21+1n¡1´CLP1n+mXh=2(h¡1)21+1nwMhCLPhn·m³1+21+1n¡1´wM1CLP1n+2(m¡1)1+1nmXh=2wMhCLPhn3mmXi=1wMiCLPin·3mW(OPT);I3mrj=0W(H)·2mW(OPT)I2m3.2OmjrjjnPj=1wjCjOmjrjjPnj=1wjCjwj;CjjOmjrjjPnj=1wjCj8:minnPj=1w[j]CLPm[j]s:t:P[j]2Aph[j]CLPh[j]¸12³³P[j]2Aph[j]´2+P[j]2Ap2h[j]´;8AµN;h=1;2;¢¢¢;m;CLPh[j]¸CLP(h¡1)[j]+ph[j];h=2;¢¢¢;m;j=1;¢¢¢;n;CLP1j¸rj+p1j;j=1;¢¢¢;n;(9)CLPij(9)OijI44OmjrjjPnj=1wjCjI2m+1rj=02mCHijIOijCHmj·CH1j+mXh=2jXk=1phk;j=1;2;¢¢¢;n:4619(5)CHmj·CH1j+mXh=221+1jCLPhj;j=1;2;¢¢¢;n;CH1j·rj+jXk=1p1k·CLP1j+21+1jCLP1j;CHmj·CLP1j+mXh=121+1jCLPhj(2m+1)CLPmj;j=1;2;¢¢¢;n:W(H)=nXj=1wjCHj·(2m+1)nXj=1wjCLPmj·(2m+1)W(OPT);I2m+1rj=0I2m4Om°°mXi=1wMiCMi;Om°°nXj=1wjCjNP[1]TangG,etal.TheoryofModernScheduling[M].Shanghai:ShanghaiPopularSciencePress,2003[2]AchugbueJO,ChinFY.Schedulingtheopenshoptominimizemean°owtime[J].SIAM-C,1982,11:709-720[3]TimkovskyVG.Isaunit-timejobshopnoteasierthanidenticalparallelmachines?[J].DiscreteAppliedMathematics,1998,85:149-162[4]BraeselH,etal.Apolynomialtimealgorithmforanopenshopproblemwithunitprocessingtimesandtreeconstraints[J].DiscreteAppliedMathematics,1995,59:11-21[5]TautenhahnT,WoegingerGJ.Minimizingthetotalcompletiontimeinaunit-timeopenshopwithreleasedates[J].OperationsResearchLetters,1997,20:207-212[6]BruckerP,etal.Openshopproblemswithunittimeoperations[J].MathematicalMethodsofOperationsResearch,1993,37:59-73[7]B¶ar¶anyI,FialaT.Nearlyoptimumsolutionofmultimachineschedulingproblems(inHungarian)[J].SzigmaMathematikaKÄozgadas¶agiFolyo¶³rat,1982,15:177-191[8]ChenB,StrusevichVA.Approximationalgorithmsforthreemachineopen-shopscheduling[J].ORSAJournalonComputing,1993,5:321-326[9]ChenR,YuW.Analysisofoperationchain'spropertiesofdenseschedulesforopen-shop[J].JournalofEastChinaUniversityofScienceandTechnology,2003,29(5):522-52662027[10]AndreasS,Schulz.Schedulingtominimizetotalcompletiontime:performanceguaranteesofLP-basedHeuriticsandlowbounds[J].Proceedingsofthe5thInternationalIPCOConference,1996:301-315OpenShopProblemto