多目标模糊作业车间调度问题研究

122Vol.12No.220062ComputerIntegratedManufacturingSystemsFeb.2006:1006-5911(2006)02-0174-06:2004-11-23;:2005-05-10Received23Nov.2004;accepted10May2005.:(70071017)Foundationitem:ProjectsupportedbytheNationalNaturalScienceFoundation,China(No.70071017).:(1968-),,,E-mail:[e-mail],(,200030):,,GT,,,,,:;;;:TP278:AResearchonMulti-objectivefuzzyjobshopschedulingLEIDe-ming,WUZhi-ming(Inst.ofAutomation,ShanghaiJiaotongUniv.,Shanghai200030,China)Abstract:Multi-objectivejobshopschedulingwithfuzzyprocessingtimeandfuzzyduedatewasstudied.Anewfuzzypriorityrules-basedrepresentationmethodwasfirstlypresented.EachgeneinthechromosomerepresentedthatintheprocedureofGTalgorithm,theconflictoccurredinthecorrespondingmachinewasresolvedbythecorrespondingpriorityrule.Secondly,Multi-ObjectiveEvolutionaryAlgorithm(CMOEA)basedonindividualcrowdingmeasurementwasdesigned,andexternalarchivesmaintenanceandfitnessassignmentwereconductedthroughthiscrowdingmeasurement.Finally,CMOEAwasappliedtosixfuzzyjobshopschedulingtomaximizetheminimumagreementindexandminimizethemaximumfuzzycompletetimeandwascomparedwithotheralgorithms.Thecomputationalresultsdemonstratedthegoodperformance(infuzzyscheduling)ofCMOEA.Keywords:fuzzyjobshopscheduling;crowdingmeasurement;priorityrule;multi-objectiveevolutionaryalgorithm01985Davis[1](GeneticAlgorithm,GA),,,,[2],makespan[3](Multi-ObjectiveGeneticAlgorithm,MOGA),,[4]MOGA,Giffler&Thompson(G&T),2:makespan[5],,,[6](multi-re-combinativeoperator),,,(Crowding-Measure-basedmulti-ObjectiveEvolutionaryAlgorithm,CMOEA),,CMOEA1nm(Multi-ObjectFuzzyJobShopSchedulingProblem,MOFJSSP),,,,ijp~ij=(a1ij,a2ij,a3ij),id~i=(d1i,d2i),1d~i,C~i,C~id~iAIiC~i,AIi=area(C~id~i)/area(C~i):maxAImin=mini=1,2,,nAIi,(1)minC~max=maxi=1,2,,nC~i(2),,,s~=(s1,s2,s3),t~=(t1,t2,t3),s~+t~=(s1+t1,s2+t2,s3+t3),s~!t~∀(s1!t1,s2!t2,s3!t3),s~=(s1,s2,s3),31c1(s~)=s1+2s2+s34,c122c2(s~)=s2,2c1,c23c3(s~)=s3-s1,22,c3d~i=(d1i,d2i),c(d~i)=d1i+d2i222,MOEA2,MOEA22.1,,[7]3n#mnm,,;[8],,nm,n#m(u1,u2,,unm),,uiG&T,i17512ui,G&T,[7]G&T;,,,,,,,,2,,p~ij=(a1ij,a2ij,a3ij),c1(p~ij),c(d~i)d~i=(d1i,d2i),,n#z(u11,u12,,u1z,,umz),z=(06~1)n,z1,z2,,uijG&T,i(kz+j)uij,k=0,12:∃;%5,FCFS,LPT,SPT,CRS/OPN,110FCFS-Firstcomefirstserved1SPT-Shortestprocessingtime2LPT-Longestprocessingtime3CR-Smallestcriticalrate4S/OPN-Smallestslackpernumberofoperationremaining(u11,u12,,u1z,,umz):(1)t=1,PSt=,mcj=0,j=1,2,,m(2)C~(o*)=min{C~(oij)|oij&St}m*(3)um*,ct={oim*&St|~im*C~(o*)}oim*,=mcm*mod(z)mcm*=mcm*+1,PSt+1=PSt∋{oim*},Stoim*,iStSt+1(4)t=t+1,(2),,mcjj,Stt,oijij,C~(oij)~ijoij2.2MOEAs,MOEA,,,,MOEAs,,PAES[9](paretoarchiveevolutionarystrategy),,,,;SPEA-2[10](strengthparetoevolutionaryalgorithm-2),k,1S,Si,,di1,di22,iScis=(di1+di2)/2S2,cis2cisi,,::∃,;%,,,,1762:2.3Pareto,MOEAs2,SPEA[11],1,1,Pareto,SPEA-2,fit(i)=Ri+Di,fit(i)i,Ri;Di=1/(2+ki),kiikNSGA-2(non-dominatedsortinggeneticalgorithm-2)[12],2front,MOEAs,,,:(1)P(iP(,fit(i)=ciP((2)2,iciG,fit(i)=ciG;,fit(i)=ciG,)05(3)2,P(,distiP(=min{distij,j&P(},fit(i)=-distiP(P(,2,N(,(N(+1)2,,,(),2a,3,2,A,23A,14A,1ii1iP(P(,iA,iP(A,,A,2.4CMOEA:1P,PP(2P∋P(,34P∋P(,5,;,2CMOEAO(MNN(max)O(MN2),M,N,N(max,22,2;,2,,3[5]6MOFJSSPCMOEA,C17712C(A,B):C(A,B)=|{b&B∗a&A,a!b}||B|(3)a!ba∀ba=b,:36#6MOFJSSP,N=60,N(max=15,gen_max=50;310#10MOFJSSP,N=80,N(max=15,gen_max=150,Pc=09,Pm=01,NSGA-2N=75,95,2[5](S)NSGA-2VisualC++,Pentium1.7GPC,20,20,(3)C,C(Xi,Xj)XjXiXj,Xi,i=1,2,3,4,CMOEA,NSGA-2,SPEAS2C,3,34310#10,,c1(C~max)24C(X2,X1)C(X3,X1)C(X1,X2)C(X3,X2)C(X1,X3)C(X2,X3)C(X4,X1)C(X1,X4)1234560.900000.60.909090.545410.888880.611.000001.01.000001.000011.000001.011.000001.01.000001.000011.000001.010.230700.00.666700.000011.000000.010.125000.00.600000.000011.000000.010.142850.00.500000.000011.000000.0134/s123456123456CMOEA1.631.851.7917.416.918.110151387NSGA-21.581.711.7816.417.116.31115654SPEA1.651.901.8218.319.618.5915948S34.2036.1031.10302.0331.0352.010159691782:2,1,SPEACMOEANSGA-2,CMOEASPEA,C(X2,X3)C(X3,X2)23,3,4,S310#10,SPEACMOEA,CMOEA4,NSGA-2CMOEA,SPEAS;CMOEA,NSGA-2,,C(X1,X2)C(X2,X1),,CMOEANSGA-2,SPEA,,4,CMOEA,,,CMOEA:[1]DAVISL.Jobshopschedulingwithgeneticalgorithms[A].ProceedingsoftheFirstInternationalConferenceonGeneticAlgorithms[C].Hillsdale:LawrenceErlbaumAssociates,1985.136-140.[2]SRIDHARJ,RAJENDRANCS.Schedulinginflowshopandcellularmanufacturingwithmultipleobjectives-ageneticalgorithmapproach[J].ProductionPlanningandControl,1996,7(4):374-382.[3]ISHIBUCHIH,MURATAT.Amulti-objectivegeneticlocalsearchalgorithmanditsapplicationtoflowshopscheduling[J].IEEETransactionsonSystems,ManandCybernetics(PartC),1998,28(3):392-403.[4]PONNAMBALAMSG,RAMKUMARV,JAWAHARN.Amulti-objectivegeneticalgorithmforjobshopscheduling[J].ProductionPlanningandControl,2001,12(8):764-774.[5]SAKAWAM,KUBOTAR.Fuzzyprogrammingformultiobjectivejobshopschedulingwithfuzzyprocessingtimeandfuzzyduedatethroughgeneticalgorithm[J].EuropeanJournalofOperationalResearch,2000,12(2):393-407.[6]ESQUIVELS,FERREROS,GALLARDR,etal.Enhancedevolutionaryalgorithmforsingleandmultiobjectiveoptimizationinjobshopschedulingproblem[J].Knowledge-BasedSystem,2002,15(1)