动态单机调度的一种滚动时域策略及全局性能分析

200499:100026788(2004)09200652071,2(1.,264209;2.,200030):,,LFIFO,,,,,,,,L,,L:;;;;:TB49:AARollingHorizonStrategyforDynamicSingle2machineSchedulingProblemandAnalysisoftheGlobalPerformancesWANGBing1,2(1.SchoolofInformationEngineering,ShandongUniversityatWeihai,Weihai264209,China;2.InstituteofAutomation,ShanghaiJiaotongUniversity,Shanghai200030,China)Abstract:Arollinghorizonstrategyforthesingle2machineschedulingproblemswithincompleteglobalinformationwaspresented.Aterminalpenaltyfunctionwasappendedtotheobjectivefunctionofeachsub2problemintherollingschedulingstrategy.Theglobalperformanceswereanalyzed.TheglobalproceduralperformancewasestimatedbasedonavirtualscheduleforunknownjobsusingFIFOrule.Wheninformationofpartialjobsisobtained,thepartialvirtualscheduleisspecified,locallyschedulingismadebasedonknownjobs,andapartitionofthelocalscheduleisimplemented.Itisconcludedthatwhilethedecisiontimeisbeingputforward,theestimationoftheglobalperformanceisgettingclosetotheultimatelyimplementedactualcostandgettingbetterandbetterstepbystep.ItisassuredthatglobalperformanceisconsistentlynotworsethanthatofFIFOanyway.Thiskindofrollingschedulingstrategyismoreadvantageouswhenjobsreleaserapidly.Keywords:rollinghorizonscheduling;incompleteinformation;localscheduling;rollingwindow;terminalpenaltyfunction:2003209223:(60274013);(11010053187075);(Z203040):,,(1966-),,,.,1iripi,Ci,1öriö6CiL,,L©1995-2005TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.1öriö6Ci,,(off2line)L,NP2Hard,,L,L(on2line)(),,L,,(look2aheadsemion2line)L,,L,LMao[1]Look2ahead,CompetitiveRatio,n,,L,L,L[2]-[5],,L[5]1öriö6Ci,,,,[5],,,L,,,[5],,L2,L,,,,,,L,,,L,,L,,,LttLL,N,tD(t)LN,t,G(t)t,D(G(t))G(t),LBG(t)CG(t)JG(t)D(G(t))()(),ûG(t)ûG(t),J(t),L1L,,L2,t,F(t),F(t),6620049©1995-2005TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.DY(F(t))L,L3,tF(t),K(t),K(t)DY(F(t)),L4D(G(t)),,($t0)($tE0)û$tûD(G(t))$tL31öriö6Ci1öriö6Ci,L[0,T](ripi),L,L,,nL,L3.1,,,,,,L,,,,,,,L,,L,,FIFOD,,,,,,,DLD,L3.2t=1,[0,T],D,F(1),DY(F(1))D,,,LDY(F(1)),,,Lt,F(t)[t,t+T]LDY(F(t))LK(t)DY(F(t))k,kFmin{J,ûF(t)û},J,L,S(t)K(t)K(t),N=S(t)K(t)K(t)LK(t)Lt,DY(t),DY(t)D(S(t))DY(K(t))DY(K(t)),DY(t)=D(S(t))+DY(K(t))+DYK(t)),1(,,769©1995-2005TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.)L,LK(t),[5]6Ci,LminD(K(t))6iK(t)Ci+ûK(t)û$CK(t),(1)$CK(t)=CK(t)-CYK(t).(2)ûK(t)ûtK(t),CK(t)D(K(t)),CYK(t)K(t)DY(K(t))Z(1),6iK(t)Ci,,ûK(t)û$CK(t),L,[5]L,DR(K(t)),CRK(t),DY(K(t))CYK(t)$CRK(t)=CRK(t)-CYK(t)L,K(t),K(t)DR(K(t)),DR(K(t))DY(K(t))$CRK(t),BRK(t)=BYK(t)+$CRK(t),(3)BYK(t)BRK(t)DY(K(t))DR(K(t)),CRK(t)DR(K(t)),K(t)LDR(t)=D(S(t))+DR(K(t))+DR(K(t))L3.3DR(K(t)),K(1FKk)D(S(t)),KKL(t),DR(KL(t)),KLq(t),DR(KLq(t)),DR(K(t))=DR(KL(t))+DR(KLq(t)),DR(KL(t))CRKL(t)t+1,1L(a)t(b)tt+11t+1,F(t+1)CRKL(t)+TLt+1t,DY(t+1)=DR(t).(4)K(t+1)KLq(t)F(t+1),KL(t),KL(t),DR(KL(t))D,18620049©1995-2005TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.LDY(S(t+1))=DR(S(t))+DR(KL(t)),(5)DY(K(t+1))=DR(KLq(t))+DR(KL(t)),(6)DY(K(t+1))=DR(K(t))+DR(KL(t)).(7)tt+1,,,L,,L4,,,L(1),(2),n,ûK(t),CYK(t),L1,L,,,L,()L2,()LL12,3,,,[6]1L31öriö6ci,,,,,,,L,,,L,,L,,,,RHC,[7][8]L,,,,,L,,L,,,:4,,L4,[6]2L4L,,L969©1995-2005TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.51i123456789101112ri358202530405065708095pi41056810121213101510L112,T=30,6,,LJ=5,K=2,FIFO2L(a)FIFO(b)(c)(,2FIFO,,,,,,,,FIFOL,,,,FIFOL6,,,L,L,,,,L,,L0720049©1995-2005TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.1,K(t),K(t)DY(K(t),tZZ,t=1,K(1)F(1)DY(F(1))k,ûK(1)û=n-k,k,DY(F(1))DFIFO,DY(K(1))Dl1=k,CYl1=CDl1,CYK(1)=CYl1Z(1)(2)D(K(1)),,DR(K(1)),$CRk(1)=CRK(1)-CYK(1)Zt-1,DR(K(t-1))$CRK(t-1)Zt,F(t),Z(6),DY(K(t))=DR(KLq(t-1))+DR(KL(t-1)).DY(K(t))ltDR(KL(t-1))DR(K(t-1)),lt,D,lt=(t-1)K+k,DY(K(t))ltCYlt,DY(K(t))CYK(t)=CYltZ,ltt,ltK(S),S=1,2,,t-1,DR(K(S))DY(K(S))$CRK(S),DY(K(1))D,ltDCDlt,tK(t),CYlt=CDlt+6t-1S=1$CRK(S),CYK(t)CYK(t)=CDlt+6t-1S=1$CRK(S)(8)Zlt,Dlt,CDlt,$CRK(S),CYK(t),(1)ûK(t)û=n(t-1)K-k,t(1)(2)D(K(t)),,,Z2D(S(t))DR(K(t)),DR(K(t))Zt=1,DY(K(1))FIFO,CYK(1),$CRK(1)E1,DR(K(1))DY(K(1))$CRK(1),DY(K(1)),DR(K(1))Zt,K(t),1,K(t)DR(K(t)D6tS=1$CRK(S),DFIFO,,DR(K(t))D,6tS=1$CRK(S),DR(K(t))D,DDR(K(t)),DR(t),(4),Z(84)179©1995-2005TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.V1U2U3,V1,U2V1(0.0547)U3V1(-0.0002)Z:U1V3,U2V1,U4V2Z[1]Z,Jij,(,,),,Z6,;,,,,L,[1],L:[1],.[J].,1997,(11):4-8.[2].[J].,1995,15(2):41-48.[3],,.[J].,2002,22(1):108-111.[4],.[J].,2002,22(7):101-105.[5],,,.[J].,2000,20(6):32-36.(71):[1]WeizhenMao,RexKKincaid.Alook2aheadheuristicforschedulingjobswithreleasedatesonasinglemachine[J].ComputersOpsRes,1994,21(10):1041-1050.[2]OvacikIM,etal.Rollinghorizonalgorithmsforasingle2machinedynamicschedulingproblemwithsequence2dependentsetuptimes[J].InternationalJournalofProductionResearch,1994,32(6):1243-1263.[3]SingerMarcos.Decompositionmethodsforlargejobshops[J].Computers&OperationsResearch,2001,28:193-207.[4]FangJian,XiYugeng.Rollinghorizonjobshopreschedulingstrategyinthedynamicenvironment[J].InternationalJournalofAdvancedManufacturingTechnology,1997,13:227-232.[5]SureshChand,RodneyTraub,RehaUzsoy.Rolling