搜索
200422:100026788(2004)0220116207FMS,,(,100044):CQNFMS,CQN,2L,,,L,FMS,LL:;;;;:TH165:ATheConfigurationandProcessRouteOptimizationofFMSBasedonHybridGALIJian2yong,CHAJian2zhong,EMing2cheng(CollegeofMechanical&ElectronicalControlEngineering,NorthernJiaotongUniversity,Beijing100044,China)Abstract:Hybridgeneticalgorithms(HGA)wasproposedforconfigurationofFMSbasedonClosedQueueingNetworks(CQN).ThemonotonicityofthroughputfunctionandcostfunctionintheCQNmodelwasfullyutilizedtodesignanoperatorcalledasMaximumGradientofThroughput2Cost.Thisoperatorcanguidenewpopulationsintofeasibleregionfrominfeasibleregion.ThealgorithmsforprocessrouteoptimizationimbeddedanoperatorcalledasOperatorDistributingRemainderRandomlyinGAtoresolvetheconstraintoptimalproblem.Theoperatordistributedequationconstraintsoverindividualsrandomlyandmakesallindividualsfeasibilitybyheuristicrules.Accordingly,HGAarecapableofsolvingthefconstraintoptimalproblemandenhancingtheirabilityoflocalsearch.AnillustrationofthemethodshowedthatthesolutionqualitybytheHGAisbetterthanthatbyImplicitEnumerationmostinuse.Keywords:FMS;optimalconfiguration;processrouteoptimization;geneticalgorithms;closedqueueingnetworks:2003201220:(50175001):(1962-),(),,,,,Email:jyli@center.njtu.edu.cn1(FlexibleManufacturingSystems,FMS),FMSLFMS(Configuration)FMS,FMS,,FMSFMSLFMS,(ClosedQueueingNetworks,CQN)[1]LFMS©1995-2005TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.,CQN,,NPLVinodSolbergCQNFMS,(ImplicitEnumeration,IE)[2],VinodSolberg,[3-6]L,,L(GeneticAlgorithms,GA),,,,GACQNFMSL,GAFMS[7]LCQNFMS(HybridGeneticAlgorithms,HGA),,,L2CQNFMS2.1FMS,,,FMSL,::FMSG,M(),gRg,grmPTmgr,VImgr;:Tmin,gTming,gFg,Fg=TmingTmin6Gg=1Tming=Tmin;:mIFm,IVm,gIPg,msmaxm,NmaxZ:grqgr,msm,NZ,m=1,2,,M;g=1,2,,G;r=1,2,,Rg,S=[sm],q=[qgr]Z2.2FMS[6]FMS:C=6Mm=1[Cm(sm)+Cp(N)],6Mm=1Cm(sm)=6{mûsm0}(IFm+IVmsm),Cp(N)=N6Gg=1FgIPgZ2.3FMSCQN,[8]ZNM1:minN,q,S6Mm=1Cm(sm)+Cp(N)s.t.T(N,q,S)ETmin6Rgr=1qgr=FgPg0FqgrFFgPg,r;0FNFNmax;N,sm7112FMS©1995-2005TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.,T(N,q,S),T=1VMG(N-1,q,S)G(N,q,S),G(N,q,S),Buzen[9]ZVM,VM=6M-1m=1Vm,Vmm,Vm=6Gg=16Rgr=1VImgrqgr,PmZNM1,FMS,,ZNM1,NM2LNM2SN,q,,ZNM2:minqD(q)=NG(N,q,S)G(N-1,q,S)s.t.6Rgr=1qgr=FgPg0FqgrFFgPg,rNM2Z3NM13.1,[6]NLBTUB:NLB=Tmin6Gg=1[Fgminr6Mm=1(PTmgrVImgr)]TUB=T(N,qopt(N))NmaxnT(Nmax,qopt(Nmax))(AsymptoticBoundAnalysis)[10],Z3.22Z,,,,,,[11]Z,2Z,,2Z,ZS+1mS,m1Zm2:$m=T(S+1m,N)-T(S,N)IVm,ifC(S+1m,N)0,ifC(S+1m,N)Em=1,2,,MNM1,,()Z,FMSZ2max1FmFM{$m},max1FmFM{$m}m1Z,Z3.3:1,NLBZS(0FsmFsmmax)N(NLBFNFNmax)ZZI=1Z81120042©1995-2005TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.2IZ3,1Z4NM2,qoptT(N,qopt)ZT(N,qopt)Tmin,N,N1NM2,qoptT(N,qopt)TUB,T(N,qopt)ETminNNmaxTUBTminZT(N,qopt)ETmin,=F(C),5ZNNmaxTUBTmin,2,3Z5I=I+1,5,Z6,,,,SN,,I=1,2Z,225,,Z,,,2,Z,2,,ZF(C)=Cmax-C,CmaxSmaxNmaxFMSZ[11],Z1,[11]Z,0.95;,0.005;20;100Z4NM2,,LNM2FMS,,LNM2LGAL,MichalewicaGENOCOP[12]L,,L,,LHGAGA(OperatorDistributingRemainderRandomly,ODRR),L4.1gRg(,qgr0,)Z,1qgr,qgrZ,ZDggZR=6rDgqgr-Fgg,R0,qgr,ODRRZODRRRqgr,,GALODRR1LODRR,,,ODRR,L4.2HGANM21)1,,Zqgr,qgr(0F9112FMS©1995-2005TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.1qgrFFg)ZZI=1;2I;3R=6rDgqgr-Fg0,ODRR;4F=G(N-1,q,S)NG(N,q,S),qgr=Fg-6rDgqgr;5I=I+1,2,;6,,,,q,,I=1,2;2)GA,{0,1}Z,,Z,,NM2,,,;,,ZZ,NM2,[q11,q12,,q1D1,q21,q22,,q2D2,,qG1,qG2,,qGDG],0FqgrFFg,1FgFG,rDgZZ3),Z,g,[0,Fg]qg1,[0,(Fg-qg1)]qg2,,[0,(Fg-6Dg-1rqgr)]qgDgZ4)NM2,0,T(q)=G(N-1,q,M)G(N,q,M)Z1,Z,0.95;,0.01;30;80Z02120042©1995-2005TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.51,VImgr,Tmin=30000Nmax=80smmax=6Z1(minutes)M1M2M3M4M5M6M7AGVFgIPg1110(1)5(2)30(1)22(1)10(1)5(1)30(1)2(8)210(2)30(1)010(2)30(1)002(6)320(1)020(1)20(1)30(1)20(1)30(1)2(6)400015(2)40(1)15(2)30(1)2(6)530(1)15(2)10(2)30(1)0002(6)0.2500002120(1)10(1)20(1)10(1)10(1)28(1)10(1)2(7)220(1)10(1)020(1)30(1)15(1)02(5)340(1)33(1)050(1)30(1)002(4)410(1)5(2)30(1)22(1)10(1)5(1)30(1)2(8)510(2)30(1)010(2)30(1)002(6)0.3600003120(1)020(1)20(1)10(1)20(1)30(1)2(6)200015(2)40(1)15(2)30(1)2(6)330(1)20(1)10(1)30(1)014(1)02(5)410(1)10(2)20(2)10(1)20(1)28(1)20(1)2(9)520(1)30(1)020(1)20(1)20(1)02(5)0.2400004140(1)33(1)050(1)30(1)002(4)230(1)20(2)10(2)20(1)0002(6)320(1)10(1)20(1)10(1)20(1)28(1)10(1)2(7)420(1)30(1)020(1)30(1)20(1)02(5)540(1)43(1)050(1)20(1)002(4)0.350000IFm(1000)1030020010015010020030IVm(1000)50100015001000120010001100100PIII800L2-3L30L,HGA,L,,,HGA1,IEL2smM1M2M3M4M5M6M7AGVN(1000)(min)IE55243202502149018HGA650552034121381561212FMS©1995-2005TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.31234IEr252352qgr0.1990.0010.30.1860.0140.3Tgr59723090035582420900330010HGAr2255145qgr0.20.2660.0340.20.0620.1040.134Tgr6007798910216007186231244025300346FMS,LFMS,,,LCQNFMS,GA,,,,LHGA,L,,L:[1]PHILIPPES,MARIOVV.AnalyticalmodelsforFMSdesignoptimization:asurvey[J].InternationalJournalofflexiblemanufacturingsystems,1994,6:209-233.[2]VINODB,SOLBERGJJ.Theoptimaldesignofflexiblemanufacturingsystems[J].InternationalJournalofProductionResearch,1985,23(6):1141-1151.[3]DALLERYY,FREINY.Anefficientmethodtodeterminetheoptimalconfigura