机器带准备时间的三台平行机排序问题的线性时间算法

32320055()JournalofZhejiangUniversity(ScienceEdition)http:öö:(10271110).:(1979),,,L,(,310027):,3,DA3(E)(E),E=15,DA31565,..:;;;:O223:A:1008-9497(2005)03-258-06FANJing,YANGQi2fan(DepartmentofMathematics,ZhejiangUniversity,Hangzhou310027,China)Lineartimealgorithmforschedulingonthreeparallelmachineswithnon-simultaneousmachineavailabletimes.JournalofZhejiangUniversity(ScienceEdition),2005,32(3):258263Abstract:Astotheschedulingproblemofparallelmachineswithnon2simultaneousmachineavailabletimes,threemachinesareinvestigated.ThelineartimealgorithmcalledDual2ThresholdAlgorithmClassDA3(E),whereEisanoptionalparameter,isproposed.Moreover,itisprovedthatifEequals15,theperformanceratioofDual2ThresholdAlgorithmDA315is65,whichisthetightone.Anduptonow,thisalgorithmisthebestalgorithmwiththeleastperformanceratioandlineartime.Keywords:scheduling;performanceratio;machineavailabletime;lineartime:m(identical)M1,M2,,Mm,J={J1,J2,,Jn},Jipi(i=1,2,,n),.,.,.,,,.:Pm,riCmax,LEELPT32=12m[1,2],LPT(MLPT)43[1].CHANGHUANGMultifit97+12k[3].1998KELLERER54[4].,,LS2-1m[5].,P2,riCmax,[6]MLPT54.Multifit65+12k,LPTMultifit©1994-2009ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.[7].2000,HE,87[8].3,,54[4],O(nlogn);LS,53[5].P3,riCmax65,,.AcA:cA=infc{c1ûCA(I)cCOPT(I),PI},CA(I)COPT(I)AI.:M={M1,M2,M3},Miri(i=1,2,3).J={J1,J2,,Jj,,Jn},Jjpj(j=1,2,,n),(pjJj).,,..,,.2DA3(Dual2ThresholdAlgorithmClass)[8],[9],m..,T1+E(E),.,(1+E)Töm,(1-Eö(m-1))Töm.,(m-1),m,,..,,,1+E.,.:DA3(E)1p1,p2,,pn[2öE],,pipi+1(1i[2öE]),p[2öE]Pi([2öE]in).2j=1,pj.3()pj,(1+E)Tö3.,pj,(1+E)Tö3.,pj.4()4.1[(1-Eö2)Tö3,(1+E)Tö3],,.4.2(1+E)Tö3,,.4.3j=n,.5j=j+1,3.DA3(E),1,pt(1tn),,,pt.,pt.1(1)DA3(E),CDöCOPT1+E.(2)DA3(E),ptETö2,t[2öE-2].(3)DA3(E),ptps(tsn),psETs[1öE-1].(1)COPTTö3.,2,M1,M2,[(1-Eö2)Tö3,(1+E)Tö3],.,M3T-2(1-(Eö2))Tö3=(1+E)Tö3.CD(1+E)Tö3(1+E)COPT.(2),DA3(E)9523,:©1994-2009ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.(1+E)Tö3-(1-Eö2)Tö3=ETö2.[2öE],piETö2(1it).pt,2(1+E)ö3E-1,(2-E)ö3E-1,pt,t(2(1+E)ö3E-1)+2((2-E)ö3E-1)+1=2öE-2.(3)pt(1+E)Tö3Tö3,,DA3(E),pt.ptM1,M2Ps(tsn),M2,M2M1,(1+E)Tö3.,M3T-2(1+E)Tö3,(1-2E)Tö3.ptLS,LS,ps(1+E)Tö3-(1-2E)Tö3=ET,T,s[1öE-1].1(3),:E=1ö5,3M1,M2,M3r1=r2=1,r3=0,p1=6+E,p2=11ö2,p3=3ö2-D,D.6,9ö2.,p1,6+D,p213ö2.DA3(E),[2öE],n[2öE];,,O(n[2öE]).,.E[9],,DA3(E)(),(),.,,.2E0(0E01),1+E0,E(0EE01),1+E,1+E0.P3,riCmax,54,,,E14.,E=15,DA31565,,,Z2,r1r2r3,r3=0.2[5]r3=0I,CA(I)COPT(I)c,I,CA(I)COPT(I)c.1E=15,P3,riCmax,DA31565.T,Pi={p1,p2,,pi}(in)p1,p2,,pi,CDCOPTDA315.,,,T=3i=1ri+ni=1pi=15.,COPTTö3=5,CD6.E=1ö5,DA31569ö2.1,:DA315,.DA315,pt3ö2,t8.,ptps(tsn),ps3s4.,DA315,CDöCOPT6ö5.t8,t.,:piMjpi(i=1,2,,n)Mj(j=1,2,3);062()32©1994-2009ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.(i=1,2,,n)Mj(j=1,2,3).r1M1,r2M2.t=8r1+p1+p2r1+r2+p1+p2T-8i=3pi15-63ö2=6,p1M1,p2M1,p3M2,p3M1,r1+p1+p2+p36,p7+p8r2+p4+p5+p6r1+p1+p2+p36,p86,p8.,p4M2,p5M3,p6M3p7M3.r1+p1+p2+p86,r2+p3+p4+p5r2+p3+p4+p86,p6+p73,T=3i=1ri+ni=1Pi15,T=15.t=8.,,ÉÊ.É,6;Ê,T15.,CDöCOPT6ö5..t=7,COPTp5+p6+p7.r1+p1r1+r2+p1=T-7i=2pi15-63ö2=6,,p1M1.É,M1p1p2.1p2M1,p3M2,p4M2,p5M3,p6M3,CD=p5+p6+p7,COPTp5+p6+p7CD,.2p2M2p3öM1,p4öM1,1.2.1p3M2,p4M3.,p4M2,p5M3,p6M3,p7M3,p5+p6+p7r2+p2+p3+p46,É.,p5öM2p6öM2.p5M1,p6M3,r1+p1+p46,r2+p2+p3+p76p5+p63,T15,Ê.p5M3,r1+p1+p46,r2+p2+p3+p56p6+p73,T15,Ê.2.2p3M3,r2+p2+p36,r1+p1(r2+p2+p3)ö23,7i=4pi6,T(r1+p1)+(r2+p2+p3)+7i=4pi15,Ê.t=7.t=6p1M1,p2öM1,p3M2,p4M2,p5M3,p6M3,,p5+p66,É.p2M2.,Ép3öM1.p3M2p3M3.p3M3,É,p4öM1,r1+p1+p46,r2+p2+p36,p5+p63,T15,Ê.p3M2,,p4M3,p5M3.CD=min{r1+p1+p6,p4+p5+p6}.CDöCOPT6ö5,P63M1,M2,M3.1P63,COPT6i=4piCD.,P62.,p1M1,COPTr1+p1+p6CD.,COPTp1+p4,CDöCOPT6ö5.,COPTr1+p5+p6..cDöCOPT6ö5,p4+p5+p6CD6COPTö56(p1+p4)ö5,5(p5+p6)6p1+p4,(1)r1+p1+p6CD6COPTö56(p1+p4)ö5,5r1p1+6p4-5p6,(2),p4+p5+p6CD6COPTö56(r1+p5+p6)ö5,5p46r1+(p5+p6),(3)(1)(2)(3)12p1+12p4-30p60.(4)r1+p1+p6CD6COPTö56(r1+p5+p6)ö5,5p1r1+6p5+p6,(5)1623,:©1994-2009ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.(2)(5)12p13p3+15p5.(6)(6)12p1+12p4-30p615p4+15p5-30p60.(7)(4)(7),CDöCOPT6ö5.,M3p1+p4.:(É)COPTp1+p5;(Ê)COPTp1+p6.,,COPTr1+p4+p6COPTr1+p4+p5,CDöCOPT6ö5,.p1M2p1M31,.t=5p1M1,p1M2p1M3,,p1M2.,r1+p16.p2M1,É,p3M3,p4M3,CD=min{r1+p2+p5,r2+p1+p5,p3+p4+p5}.CDCOPT,P53M1,M2,M3122.,M1p1.,COPTr1+p16.CDöCOPT6ö5,r1+p2+p536ö5,r2+p1+p4r2+p1+p536ö5,3p3p3+p4+p536ö5p312ö5.T(r1+p2+p5)+(r2+p1+p4)+p336ö5+36ö5+12ö5=84ö515,Ê.CDöCOPT6ö5.,3M1,M2,M3.M1,M2,M3P51,2,2,p1M2,COPTr2+p1+p5CD.3:(É)COPTr2+p3+p4,COPTp1+p5;(Ê)COPTr2+p3+p5,COPTp1+p4;(Ë)COPTr2+p4+p5,COPTp1+p3;(É),CDöCOPT6ö5.,.,CDöCOPT6ö5.r2+p1+p5CD6COPTö56(p1+p5)ö5,5r2p1+p5,(8)p3+p4+p5CD6COPTö56(r2+p3+p4)ö5,p52r2,(9)(9)(8)3r2p1.(10),r2+p1+p5CD6COPTö56(r2+p3+p4)ö5,5p1r2+6(p3+p4)-5p5r2+7p5,(9),p13r2.(11)(11)(10),CDöCOPT6ö5.M1,M2,M32,2,12,1,2,p2M1,COPTr1+p2+p5CD,3:(É)COPTr1+p3+p4,COPTp2+p5;(Ê)COPTr1+p3+p5,COPTp2+p4;(Ë)COPTr1+p4+p5,COPTp2+p3.3(É),.p2M2P2M3p2M1