智能算法在柔性車間調(diào)度中的應(yīng)用

《智能算法在柔性車間調(diào)度中的應(yīng)用》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、智能算法在柔性作業(yè)車間調(diào)度中的應(yīng)用摘要：為提高企業(yè)生產(chǎn)效率，合理的流水車間生產(chǎn)調(diào)度顯得尤為重要。本文介紹了三種智能算法（蟻群算法、遺傳算法、改進粒子群算法）在車間生產(chǎn)調(diào)度中的應(yīng)用，主要介紹了算法的基本思想、模型結(jié)構(gòu)、算法實現(xiàn)以及運用前景。對智能算法在生產(chǎn)調(diào)度中的應(yīng)用做出總結(jié)。關(guān)鍵字：智能算法；蟻群算法；遺傳算法；改進粒子群算法；生產(chǎn)調(diào)度0.前言柔性作業(yè)車間調(diào)度問題(Flexiblejob-shopsche-dulingproblem,FJSP)是傳統(tǒng)作業(yè)車間調(diào)度問題的擴展，是實際生產(chǎn)中迫切需要解決的

2、一類問題。在傳統(tǒng)的作業(yè)車間調(diào)度問題中，工件的每道工序只能在一臺確定的機床上加工。而在柔性作業(yè)車間調(diào)度問題中，每道工序可以在多臺機床上加工，并且在不同的機床上加工所需時間不同。柔性作業(yè)車間調(diào)度問題減少了機器約束，擴大了可行解的搜索范圍，增加了問題的難度。作業(yè)車間的主要特點是：n個工件需要在m臺機器上進行加工，每個工件都有其獨特的加工步驟，但無明顯的順序約束，并且加工時間是已知的，調(diào)度的目標是在不允許兩個工件同時在同一臺機器上加工的前提下，如何安排工件在每臺機器上的加工順序使這些工件能夠盡快加工完畢[1

3、]。1.蟻群算法在作業(yè)車間的應(yīng)用[2]以3個工件2臺機器的問題作為例子，如圖1。圖1三個工件兩臺機器的JSP問題為確定先對哪個工件進行加工，需要設(shè)置一個初始節(jié)點O0，所有的螞蟻最初都放置在O0。圖1中除與O0相連的有向弧表示同一個工件的加工順序，工件必須按照該順序進行加工。其它則為無向弧。每個弧與表示節(jié)點間信息素的量和啟發(fā)式距離的一對值{αij,dij}有關(guān)。dij通常為對節(jié)點j的第i步操作的加工時間，τij使用蟻周方式進行更新：其中，ρ是個系數(shù)，1?ρ表示在時間t和t+1之間信息素的蒸發(fā)，Q為常數(shù)

4、，Tk為完成所有加工步驟后最短的總加工時間。初始時刻τij(0)=c（c為常數(shù)）。這個規(guī)則包含了兩個方面：(1)圖1中所有邊緣上的信息素都要蒸發(fā)；(2)完成所有的加工后要將該解的效果加到各邊緣上。蒸發(fā)可以防止搜索局限在局部最小的鄰域中，另一方面又能根據(jù)已有解的效果好壞來更新信息素，進行增強學(xué)習(xí)。另一個關(guān)鍵的問題就是如何保證螞蟻按照工件的工藝路線產(chǎn)生一組可行解。這里用到3個集合：對每個螞蟻k，首先要有集合Gk，表示沒有訪問過的節(jié)點集合；Sk表示根據(jù)技術(shù)路線下一步允許訪問的節(jié)點集合；還需要一個禁忌表，存

5、放已經(jīng)訪問過的節(jié)點。在我們的例子中，Gk={1，2，3，4，5，6}，Sk={1，2，3}。轉(zhuǎn)移概率是通過下式計算的：Tij為工件i在機器j上的加工時間。每選擇一個節(jié)點，該節(jié)點就被追加到禁忌表中并從Gk和Sk中刪除；如果被選的節(jié)點不是工件的最后一步，那該工件中緊鄰的下一個節(jié)點會被加到Sk中。該過程一直重復(fù)到Gk=φ。最后禁忌表中得到的節(jié)點的排列順序就是螞蟻k找到的解。參數(shù)α和β決定了算法的收斂速度并對解的性能好壞有重要影響，同時蒸發(fā)常數(shù)也需要進行適當(dāng)?shù)恼{(diào)整以使搜索能在好的搜索空間中進行，并防止陷入局

6、部最優(yōu)的鄰域中。蟻群算法已經(jīng)被成功地運用于10個工件、10臺機器和10個工件、15臺機器的JSP例子中，該算法總能得到最優(yōu)解的10%以內(nèi)的解，只是該方法的計算復(fù)雜性占用了部分執(zhí)行時間，但我們?nèi)钥梢哉J為這是一個比較有希望的結(jié)果。2.遺傳算法在作業(yè)車間調(diào)度中的應(yīng)用2.1遺傳算法編碼和解碼[3]編碼與解碼是指染色體和調(diào)度解之間進行相互轉(zhuǎn)換，是遺傳算法成功實施優(yōu)化的首要和關(guān)鍵問題。對于傳統(tǒng)的作業(yè)車間調(diào)度問題，大多數(shù)研究采用基于工序的編碼。但是柔性作業(yè)車間調(diào)度問題不僅要確定工序的加工順序，還需為每道工序選擇一

7、臺合適的機器，僅采用基于工序的編碼方法不能得到問題的解。因此，對于柔性作業(yè)車間調(diào)度問題，遺傳算法的編碼由兩部分組成，第一部分為基于工序的編碼，用來確定工序的加工先后順序；第二部分為基于機器分配的編碼，用來選擇每道工序的加工機器。融合這兩種編碼方法，即可得到柔性作業(yè)車間調(diào)度問題的一個可行解。2.1.1基于工序的編碼這部分編碼染色體的基因數(shù)等于工序總數(shù)，每個工件的工序都用相應(yīng)的工件序號表示，并且工件序號出現(xiàn)的次數(shù)等于該工件的工序數(shù)。根據(jù)工件序號在染色體出現(xiàn)的次序編譯，即從左到右掃描染色體，對于第k次出現(xiàn)

8、的工件序號，表示該工件的第k道工序。對表1所表示的柔性作業(yè)車間調(diào)度問題，一個基于工序編碼的基因串可以表示為[12213123]，其中1表示工件J1，2和3意義相同。基因串中的3個1依次表示工件J1的3個工序，分別為工序1、工序2和工序3。2.1.2基于機器分配的編碼設(shè)工序總數(shù)為l，工序號分別用1,2,3,?,l表示。對于這l道工序，形成l個可選擇機器的子集{S1,S2,S3,?,Sl}，第i個工序的可加工機器集合表示為Si，Si中元素個數(shù)為ni，表示為{mi1,mi2