基于混合遺傳算法的敏捷車間調(diào)度研

《基于混合遺傳算法的敏捷車間調(diào)度研》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、2006年2月航空精密制造技術(shù)Feb.2006第42卷第1期AVIATIONPRECISIONMANUFACTURINGTECHNOLOGYVol.42No.1工藝與設(shè)備基于混合遺傳算法的敏捷車間調(diào)度研究*王東成1,2,何衛(wèi)平1,王邦龍2(1.西北工業(yè)大學(xué),西安710072,2.中國航空救生研究所襄樊441003)[摘要]基于遺傳算法和模擬退火算法相結(jié)合的混合遺傳算法,研究了敏捷車間作業(yè)排序的初始化(靜態(tài)調(diào)度)和動(dòng)態(tài)重調(diào)度機(jī)制,通過與相關(guān)文獻(xiàn)中實(shí)例的分析比較表明調(diào)度算法性能良好,能夠應(yīng)用于實(shí)際的制造環(huán)境。[關(guān)鍵

2、詞]敏捷車間;調(diào)度;混合遺傳算法[中圖分類號(hào)]TH186[文獻(xiàn)標(biāo)識(shí)碼]B[文章編號(hào)]1003-5451(2006)01-0043-05HybridGeneticAlgorithmfortheAgileWorkshopSchedulingWANGDong-cheng,HEWei-ping,WANGBang-long(1.NorthwesternPolytechnicalUniversity,Xi'an7100722.ChinaAviationLife-SupportInstitute,Xiangfan441003

3、)[Abstract]Theframeworkofschedulingsystemusedforagileworkshopispresented.Basedonthehybridofgeneticalgorithmandsimulatedannealing,thestaticscheduling&dynamicreschedulingarestudied.Comparingtotheapproachandresultsofademonstrationincorrespondingliterature,itisp

4、rovedperformingwellandcanbeappliedtorealmanufacturingenvironments.[Keywords]agileworkshop;scheduling;hybridgeneticalgorithm引言法,提高解的次優(yōu)性,從而獲得實(shí)際工程問題的解決。調(diào)度功能是車間的核心功能之一,它直接關(guān)系遺傳算法(GA)是一種并行優(yōu)化搜索方法,在靜[12]著車間能否在指定的時(shí)間段內(nèi)合理利用有限的制造態(tài)調(diào)度問題中已經(jīng)有成功的應(yīng)用。但是遺傳算法資源完成相應(yīng)的加工任務(wù)。同時(shí),調(diào)度問題又

5、是一個(gè)是一類通用的優(yōu)化算法,對于特定問題其局部優(yōu)化相當(dāng)復(fù)雜的問題,不但本身的求解過程相當(dāng)復(fù)雜,而能力往往比較有限,因此單獨(dú)使用GA的性能往往且在不同制造環(huán)境下所考慮的約束、達(dá)到的目標(biāo)等不太滿意。許多傳統(tǒng)的局部搜索方法盡管容易陷入均不相同,這使得調(diào)度問題之間的差別很大,特別是局部極小,但其局部搜索能力很強(qiáng),這正好能夠克服[6]在敏捷制造模式下,車間虛擬生產(chǎn)單元的構(gòu)成與配GA的缺點(diǎn)。因此,鑒于GA和傳統(tǒng)局部搜索方法或置均處于動(dòng)態(tài)變化之中,導(dǎo)致了問題的更為復(fù)雜化。規(guī)則的互補(bǔ)特性,許多場合將二者結(jié)合使用,以提高由于調(diào)度

6、問題的復(fù)雜性,至今尚未形成一套系算法的優(yōu)化質(zhì)量和效率。本文采用以遺傳算法為基統(tǒng)的方法和理論,理論研究與實(shí)際應(yīng)用之間還存在礎(chǔ),嵌套模擬退火算法的混合遺傳算法(以下簡稱著很大差距。同時(shí)也由于尋找具有多項(xiàng)式復(fù)雜性的GASA)來彌補(bǔ)遺傳算法的局域搜索能力的不足,避最優(yōu)算法幾乎不可能,使得其研究趨向于以增加合免“早熟”收斂現(xiàn)象的發(fā)生,并用于車間實(shí)際調(diào)度問理的計(jì)算時(shí)間為代價(jià),探索更好的近似最優(yōu)調(diào)度算題。*國防基礎(chǔ)科研項(xiàng)目(K1800020502)·43·基于混合遺傳算法的敏捷車間調(diào)度研究*1敏捷車間計(jì)劃調(diào)度框架往往需要不斷

7、地進(jìn)行動(dòng)態(tài)重調(diào)度。VMC實(shí)時(shí)動(dòng)態(tài)調(diào)度也即系統(tǒng)在擾動(dòng)出現(xiàn)時(shí)迅速對擾動(dòng)情況進(jìn)行評估在敏捷制造模式下,傳統(tǒng)意義上的車間被分成判斷,決定是否進(jìn)行重調(diào)度,如果需要,系統(tǒng)必須實(shí)若干虛擬制造單元(VMC),因此車間的計(jì)劃調(diào)度相時(shí)快速調(diào)整作業(yè)排序及其相應(yīng)的資源。應(yīng)地分層進(jìn)行。本文基于這一特點(diǎn),將敏捷車間計(jì)劃限于篇幅及本文的研究目標(biāo),這里將不討論調(diào)度劃分為3個(gè)層次,即敏捷車間單元規(guī)劃(VMCVMC單元規(guī)劃問題,而重點(diǎn)研究敏捷車間VMC作的劃分與形成)、VMC作業(yè)計(jì)劃初始化(靜態(tài)調(diào)度)、業(yè)計(jì)劃初始化(靜態(tài)調(diào)度)和實(shí)時(shí)動(dòng)態(tài)調(diào)度,即圖

8、1VMC實(shí)時(shí)動(dòng)態(tài)調(diào)度。三者的關(guān)系如圖1所示。中的虛線所示部分。2基于混合遺傳算法的敏捷車間調(diào)度2.1問題描述敏捷車間的計(jì)劃調(diào)度問題屬于典型的JobShop調(diào)度問題(以下簡稱JSP),JSP研究n個(gè)工件在m臺(tái)機(jī)器上的加工,已知各操作的加工時(shí)間和各工件在各機(jī)器上的加工次序約束,要求確定與工藝約束條件相容的各機(jī)器上所有工件的加工開始時(shí)間或完成時(shí)間或加工次序,使加工性能指標(biāo)達(dá)到最優(yōu)。下面是該問