蚁群算法在车间调度问题中的应用

0Job-ShopSchedulingProblemJSPNP。JSP、〔1〕、〔2〕、〔3〕、〔4〕。AntColonyAlgorithmACAM．Dorigo2090、。“”stigmergy〔5〕。。。。TravelingSalesmanProblem〔6〕QuadraticAssignmentProblemJSP。ACAJSP。11．1JSPnn≥3mm＞2。J=J1J2…JnJiii=12…nM={M1M2…Mm}Mjjj=12…mk671003。。JSP。TP18A1672-2345201010-0010-05JOURNALOFDALIUNIVERSITY910201010Vol.9No.10Oct.2010AntColonyAlgorithmforSolvingJob-ShopSchedulingProblemZHANGXiaoling,HECaixiang,CHENJianhuaCollegeofMathematicsandComputerScienceDaliUniversity,Dali,Yunnan671003,China〔Abstract〕ThispaperproposesAntColonyAlgorithmACAtosolveJob-shopSchedulingProblemJSP.Job-ShopschedulingproblemisatypicalNPhardproblems,antcolonyalgorithmisadistributedevolutionarycomputationmethods,Themaincharacteristicsofthisalgorithmarerobustness,positivefeedback,parallelism,andsimple.Inthispaper,theflowofantcolonyalgorithmusedtosolveJob-shopschedulingproblemisgiven,thenumericalexperimentsofACAwereimplementedinasmallJSP,theexperimentalresultsshowthattheantcolonyalgorithmcanbeusedtosolvejobshopschedulingproblemandtheoptimalsolutionornearoptimalsolutioncanbeachieved.〔Keywords〕AntColonyAlgorithm;Job-ShopSchedulingProblem;pheromone;10muijijO={uij｜i∈〔1n〕j∈〔1m〕nm。Ttij∈TiJij。tij=0JiMj。JSP①1②③④。cij=cik+Tijuijuik→uijCmax。Cmax=maxalluij∈OCij=maxuik→uijcik+Tij11．2JSPD=NABJSPNuijN=m·n。A。B。O0O10。33。1。13／3／G／CmaxJSP10=O010=O101=u122=u133=u114=u215=u226=u237=u318=u339=u321125125O0O10。123145627893。mm。JSP{417823596。2ACAJSP1ACAJSPO0On+10010。GkSkJk。Gk={123456789}Sk={147}。0{αijTij}Tijji。JkGkSk。。Gk=覬。k。。。。。2．1ACA“”“”explorationexploitation98211rk1ss=argmaxu∈Sk〔τru〕·〔ηu〕βifq≤q0Sotherwis≤e22τηηs=1/TssSkkβ＞0。qq∈〔01〕0≤q0≤1。S3。Pkrs=〔τrs〕·〔ηs〕β/∑u∈Sk〔τru〕·〔ηu〕βifs∈Skotherwise%%。q0“”“”。rk0≤q≤1q≤q012。2．2ACA。4。τrs←1-α·τrs+α·Δτrs4Δτrs=1/Tgbifrs∈globalbesttour0otherwise←0＜α＜1Tgbk。2．35。τrs←1-ρ·τrs+ρ·τ050＜ρ＜1τ0“”。2．4ACAJSPnmJSPJSPACA。2。2JSP1τ0ρβαnnm2n032354n+lJSP452。821234JSPFT03FT06LA06LA07ACAJSP。3．1ACA1。1JSP1010。3．22ACA410。“OPT”。2ACAJSP。ACA。3FT06LA06ABZ6。21ACAJSPaFT06bLA06cABZ63ACAJSP3ACAJSPFT06LA06ABZ61000500ABZ6。23ACAJSPACAJSP。ACAJSPACA。4ACAJSPJSP。〔1〕．Hopfieldnet〔J〕．200423S88-90.〔2〕．〔J〕.20092682928-2930.〔3〕．q00.80.80.80.8FT03FT06LA06LA07β2.00.02.02.0α0.10.10.10.1ρ0.010.10.010.01OPT1255926-FT03FT06LA06ABZ6n361510m365101259.510341245ACA-1255926115498213《》2008—2009GRTHSNPrs5513732008782008712ECC2009842009842009842009882009882008712Araneae:Leptonetidae2008712200984200984200984200988-Hopf200988〔J〕．20093211173-188.〔4〕.〔J〕.200932112138-2145.〔5〕DorigoMStitzleT.AntColonyOptimization〔M〕.MAMITPress2004.〔6〕.TSP〔J〕.200915381-87.2010Y3492010-04-092010-05-20.8214