基于蚁群算法的模具制造动态调度研究

127计算机集成制造系统Vol.12No.720067ComputerIntegratedManufacturingSystemsJuly2006:1006-5911(2006)07-1028-09:2005-04-21;:2005-12-06Received21Apr.2005;accepted06Dec.2005.:Foundationitem:ProjectsupportedbytheCommissionofScienceTechnologyandIndustryforNationalDefense,China.:(1971-),,,,,E-mail:[e-mail],,,(,150001):,,,,,,:;;;;:TH166;TG76:ADynamicschedulingofmoldmanufacturingbasedonantcolonyoptimizationWANGYan-bin,WANGGang,ZHAOLi-zhong,GAOGuo-an(AdvancedManufacturingTech.Cent.,HarbinInst.ofTech.,Harbin150001,China)Abstract:Aschedulingsystemwasestablishedtosolvethedynamicschedulingprobleminmoldmanufacturing.ThesystemcombinedtheAntColonyOptimization(ACO)algorithmandthedispatchingpriorityheuristicalgorithmtosolvetheschedulingproblemsexistinginmoldpartswithworkpiecerestrictions.Firstly,ACOwasusedtodeterminethemachinesneededineachworkingprocedure,thenpriorityheuristicalgorithmwasusedtosetthesequenceofthepartstobemachinedinthesamemachine.Adynamicschedulingalgorithmbasedonmovingwindowandconsiderationoflocalandglobalupdatewasputforwardforreal-timemoldscheduling.Localupdatestrategywasadoptedforthoseturbulences,whichhappenedinhighfrequencybutwithlittleinfluenceonthescheduling;otherwise,globalupdatestrategywasadopted.Theschedulingefficiencywasimprovedaswellasthenear-optimumsolutionwasguaranteed.Keywords:workpiecerestriction;antcolonyoptimizationalgorithm;dispatchingpriorityheuristicalgorithm;moldmanufacturing;dynamicscheduling0[1],,;[2];[3](Job-shop),7:,,,,,1:,;,,,,:(1)M,,,(2),3,(3),,1Ci.j,Ei.j,Pi.ji,j:C3.232,38,8:C3.1,C3.2,!,C3.8(4),1,C3.2.1321(5),,Pi.j.kCi.l.m,[Ci.j.k,Pi.l.m],,,[Ci.j.k,Ei.l],Ci.j.k-1Ei.l,[Ci.j.k,Ei.l,Ei.m,!](6),,,,,,22.13,12.2(1)蚁群算法模块(2)监控评估模块,;(3)动态数据库管理模块()3,,,,102912,,,1;2[4]3.1Dorigo[5],3.1.1信息素和启发式信息引导下的解构造过程,[6]2,,v0,v(i.j.k)l,,v={x|x=C,E,P,};vi.j.kV(i.j.k),,V={x|x=C,E,P}v(i.j.k)lvi.j.kl∀Mv(i.j.k)(v={x|x=C,E,P})Mv(i.j.k),[7]vi.j.k.l,vi.j.k.lv0,,m∀Mv(i.j.k)m:m=argmaxl∀Mv(i.j.k)([vi.j.k.l(t)]#[vi.j.k.l(t)]!),qq0m∃,q%q0;(1),q∀[0,1],q0∀[0,1],q0[vi.j.k.l(t)]#[vi.j.k(t)]!l∀Mv(i,j,k),,1-q0,,Pi.j.k.m(t)m∃:Pi.j.k.m(t)=[vi.j.k.m(t)]#[vi.j.k.m(t)]!&l∀Mv(i.j.k)([vi.j.k.l(t)]#[vi.j.k.l(t)!]),m∀Mv(i.j.k);0,mMv(i.j.k)(2),vi.j.k.m(t)t;vi.j.k.m(t)3.1.2信息素踪迹更新,(),[6][8]∀,∀#g#b()∀Set,s∀Set∀,Qf(s),∀():vi.j.k.m(t+1)=(1-∃)vi.j.k.m(t)+∃U&{s|s∀Set,S(i,j)=m}Qf(s)&{s|s∀Set}Qf(s),(3)vi.j.k.m(0)=U/|Mv(i.j.k)|(4),∃,U,U∋&m∀Mv(i.j.k)vi.j.k.m(t),|Mv(i.j.k)|vi.j.k.m,Qf(s)s,maxT,Qf(s)1maxT;Q10307:,Qf(s)1/QQf(s)2(3)(4),,3.2,[9],:,,PStt;Stt,PSt;%ii∀St;&ii∀St,%iii%i,&i=%i+ti,tii,:1t=0,PSt,St2%*t=mini∀St{%i}%*tm*3m*i∀St%i=%*t,,PSt,PSt+14PSt+1,:(1)Sti(2)i,StiSt+1;ii,StiSt+1,St+1(3)t=t+152,3.3,[10],1GA(geneticalgorithm)[10],ACO_GA(antcononyoptimization-geneticalgorithms)[8]_,ACO_HA(antcononyoptimization-heuristicalgorithms)_ACO_HA,m=10,∃=0.3,=!=0.5,q0=0.6,Set=3,2,[8][10],ACO_HAACO_GA,[10]GA1GAACO_GAACO_HA8787.9944.1,,(1)局部更新动态调度策略103112,,,,,,,,,,,,(2)全局更新重调度策略,,,4.2[10],,:(,,,),,,,[11],/2,3:(1)事件驱动局部更新,(2)事件驱动全局更新,(3)周期驱动全局更新,,,,,;,,,2/∗∗∗∗∗∗4.3t0,:(1),:1),∋t,∋T:|∋t|∋T,∋t0,∋t,∋t0,;|∋t|∋T∋T2),3),4),(2),∋tj,Tn(n=1,2,!,m)Tn:10327:Tn=t0+T,∋tj+T;t0+∋tj,∋tjT(5)(3)(4)51,3,4311C1.1,C1.2,C1.3C1.4,C1.5,C1.6E1.1(C1.2),E1.2(C1.3),(E1.3,E1.4)(C1.5),(E1.5,E1.6)(C1.6)P1.1,P1.2~P1.722C2.1,C2.2,C2.3C2.4,C2.5,C2.6E2.1(C2.2),E2.2(C2.3),E2.3(C2.5),E2.4(C2.6)P2.1,P2.2~P2.74M1M2M3M4M5M6M7M8M9M1012312125(),,5M1M2M3M4M5M6M7M8M9M10C1.1.1466.55C1.1.2811([C1.1.3,C1.2.3,C1.3.3]678E1.1.111.21.31.51.5E1.1.255.36[E1.1,C1.2.4]811E1.2.111.21.31.51.5E1.2.255.36[E1.2,C1.3.4]811([C1.4.4,C1.5.4,C1.6.4]1111.51.51.5E1.3.12.52.52.63.33.3(:m=10,∃=0.3,=!=0.5,q0=0.6,Set=3200(3),4,30h,,;∋T,5%,,t=23,M11(),,52[4]∋T1:C1.3.1,C2.4.1,t=21,M2,7C1.3.1,C2.4.1,M1,,M2,,M2M1M3,30h10331210347:6,,;,,;103512:(;),,,,,,,,,:[1]JAINA,ELMARAGHYH.Productionscheduling/reschedulinginflexiblemanufacturing[J].InternationalJournalProductionResearch,1997,35(1):281-309.[2]ANDREAR,GINOD.DynamicschedulingofFMSsuingareal-timegeneticalgorithm[J].InternationalJournalProductionResearch,2000,38(1):1-20.[3]FANGJian,XIYugeng.Genetic-algorithm-basedscrollingschedulingstrategy[J].ControlSystemandApplications,1997,14(4):589-594(inChinese).[,.[J].,1997,14(4):589-594.][4]WANGYanbin,GAOGuoan,ZHAOLizhong.Researchonoptimizeschedulinginmoldmanufacturingwithwork-piececonstraints[J].ComputerIntegratedManufacturingSystems,2005,11(10):1419-1429(inChinese).[,,.[J].,2005,11(10):1419-1424.][5]DORIGOM,MANIEZZOV.Antsystem:optimizationbyacolonyofcooperatingAgents[J].IEEETransactionsonSystems,Man,andCybernetics-PartB,1996,26(1):29-41.[6]WANGXiaorong,WUTiejun.Anantcolonyoptimizationalgorithmforflowshopscheduling[J].SystemsEngineering,,,Theory&Practice,2003,23(5):65-71(inChinese).[,.Flowshop[J].,2003,23(5):65-71.][7]WANGYanbin,ZHAOLizhong.Applicationsoffuzzyprocessreasoninginagilemouldsmanufacturing[J].AerospaceManufacturingTechnology,2003,4(2):19-22.[8]WANGXiaorong,WUTiejun.Flexiblejob-shopschedulingbasedonPetri-netmodel[J].JournalofZhejiangUniversity(EngineeringScience),2004,51(3):286-291(inChinese).[,.Petri[J].(),2004,51(3):286-2