資源描述：
《基于遺傳和禁忌搜索算法求解車間調(diào)度優(yōu)化問題.pdf》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、第26卷第4期計(jì)算機(jī)應(yīng)用Vol.26No.42006年4月ComputerApplicationsApr.2006文章編號(hào):1001-9081(2006)04-0857-04基于遺傳和禁忌搜索算法求解車間調(diào)度優(yōu)化問題1,2111梁迪,謝里陽,隋天中,陶澤(1.東北大學(xué)機(jī)械工程與自動(dòng)化學(xué)院,遼寧沈陽110004;2.沈陽大學(xué)機(jī)械工程學(xué)院,遼寧沈陽110004)(ldcai@sohu.com)摘要:針對(duì)柔性生產(chǎn)環(huán)境下的車間調(diào)度問題,在考慮遺傳算法早熟收斂問題和禁忌搜索法自適應(yīng)優(yōu)點(diǎn)的基礎(chǔ)上,將遺傳算法和禁忌搜索法結(jié)合起來,提出了基于遺傳和禁忌
2、搜索的混合動(dòng)態(tài)優(yōu)化調(diào)度算法,并用實(shí)例對(duì)該算法進(jìn)行了仿真研究。結(jié)果表明,此算法有很好收斂精度,是可行的,并且能夠在擾動(dòng)發(fā)生后提供新的調(diào)度計(jì)劃,與傳統(tǒng)的調(diào)度算法相比較,體現(xiàn)了明顯的優(yōu)越性。關(guān)鍵詞:遺傳算法;禁忌搜索算法;車間調(diào)度;組合優(yōu)化中圖分類號(hào):TP311文獻(xiàn)標(biāo)識(shí)碼:AResearchonshopschedulingoptimizationbasedongeneticandtabusearchhybridalgorithm1,2111LIANGDi,XIELi2yang,SUITian2zhong,TAOZe(1.SchoolofMec
3、hanicalEngineeringandAutomation,NortheasternUniversity,ShenyangLiaoning110004,China;2.SchoolofMechanicalEngineering,ShenyangUniversity,ShenyangLiaoning110044,China)Abstract:InordertoavoidprematureconvergenceandtobalancetheexplorationandexploitationabilitiesofsimpleGA,ahy
4、bridalgorithmwasproposedtosolvedynamicschedulingprobleminflexibleproductionenvironment.ItisusingGAexcellentwholesearchabilityandself2adaptivemeritofTabuSearch(TS),andtheconvergenceofresearchwasimproved.Itiscapableofgeneratingalternativescheduleafteruncertaindisturbanceta
5、kesplaceonajobshop.Afterusingcrossoverandmutationoperations,abestorsecondbestschedulingplancanbefound.Theresultofthetestshowsthatthemethodisfeasibleandefficient.Keywords:geneticalgorithm;tabusearch;jobshopscheduling;combinationoptimization度問題進(jìn)行研究,這樣有利于豐富優(yōu)化過程中的搜索行為,增0引言強(qiáng)全
6、局和局部意義下的搜索能力和效率,與單純的遺傳算法生產(chǎn)調(diào)度是計(jì)算機(jī)集成制造系統(tǒng)(ComputerIntegrated和禁忌搜索算法相比有明顯的優(yōu)越性。ManufacturingSystem,CIMS)研究領(lǐng)域生產(chǎn)管理的核心內(nèi)容和1問題描述關(guān)鍵技術(shù),車間調(diào)度問題(JobshopSchedulingProblem,JSP)是最困難的約束組合優(yōu)化問題和典型的NP難問題,其特點(diǎn)是2.1JSP的數(shù)學(xué)模型建立[1,2]沒有一個(gè)有效的算法能在多項(xiàng)式時(shí)間內(nèi)求出其最優(yōu)解。JSP研究n個(gè)工件在m臺(tái)機(jī)器上加工,已知各操作的加工到目前為止,已有一些傳統(tǒng)的啟發(fā)式算
7、法求解JSP優(yōu)化時(shí)間和各工件在各機(jī)器上的加工次序約束,要求確定與工藝[3,4]調(diào)度問題。在文獻(xiàn)[3]中,作者先是用Petri網(wǎng)對(duì)JSP進(jìn)行約束條件相容的各機(jī)器上所有工件的加工開始時(shí)間或完成時(shí)建模,然后應(yīng)用L1算法搜索最優(yōu)解,L1算法其本質(zhì)是分枝定間或加工次序,使加工性能指標(biāo)達(dá)到最優(yōu)。界法和動(dòng)態(tài)規(guī)劃法的混合運(yùn)用。文獻(xiàn)[4]是用遺傳代碼先確1)機(jī)器順序陣JM,JM(i,j)表示加工i工件的第j個(gè)操作定各Job類型的調(diào)度先后順序,然后用傳統(tǒng)的人工智能中的的機(jī)器號(hào),JM(i,·)表示i工件的所有操作按優(yōu)先順序加工的FBS(FilteredBea
8、mSearch)搜索方法對(duì)各個(gè)Job的每道工序按各機(jī)器號(hào)的排列。順序進(jìn)行安排調(diào)度。這種FBS搜索方法是寬度優(yōu)先搜索法2)加工時(shí)間陣T,T(i,j)為j工件在機(jī)器上的加工時(shí)間。的一種改進(jìn)方法。3)工件排列陣M
