(完整版)智能算法在柔性車間調度中的應用

智能算法在柔性作業(yè)車間調度中的應用摘要：為提高企業(yè)生產效率，合理的流水車間生產調度顯得尤為重要。本文介紹了三種智能算法(蟻群算法、遺傳算法、改進粒子群算法)在車間生產調度中的應用，主要介紹了算法的基本思想、模型結構、算法實現以及運用前景。對智能算法在生產調度中的應用做出總結。關鍵字：智能算法；蟻群算法；遺傳算法；改進粒子群算法；生產調度0.前言柔性作業(yè)車間調度問題(Flexiblejob-shopsche-dulingproblem,JSP)是傳統(tǒng)作業(yè)車間調度問題的擴展，是實際生產中迫切需要解決的一類問題。在傳統(tǒng)的作業(yè)車間調度問題中，工件的每道工序只能在一臺確定的機床上加工。而在柔性作業(yè)車間調度問題中，每道工序可以在多臺機床上加工，并且在不同的機床上加工所需時間不同。柔性作業(yè)車間調度問題減少了機器約束，擴大了可行解的搜索范圍，增加了問題的難度。作業(yè)車間的主要特點是：n個工件需要在m臺機器上進行加工，每個工件都有其獨特的加工步驟，但無明顯的順序約束，并且加工時間是已知的，調度的目標是在不允許兩個工件同時在同一臺機器上加工的前提下，如何安排工件在每臺機器上的加工［f呢、一■—ifkeallowed上日1禺林虬工止0crhei^ise其中，P是個系數，1P表示在時間t和t+1之間信息素的蒸發(fā)，Q為常數，Tk為完成所有加工步驟后最短的總加工時間。初始時刻t(0)=c(c為常ij數)。這個規(guī)則包含了兩個方面：(1)圖1中所有邊緣上的信息素都要蒸發(fā)；(2)完成所有的加工后要將該解的效果加到各邊緣上。蒸發(fā)可以防止搜索局限在局部最小的鄰域中，另一方面又能根據已有解的效果好壞來更新信息素，進行增強學習。另一個關鍵的問題就是如何保證螞蟻按照工件的工藝路線產生一組可行解。這里用到3個集合：順序使這些工件能夠盡快加工完畢［1］。對每個螞蟻k,首先要有集合Gk順序使這些工件能夠盡快加工完畢［1］。k的節(jié)點集合；S「表示根據技術路線下一步允許訪k1.蟻群算法在作業(yè)車間的應用［2］問的節(jié)點集合；還需要一個禁忌表，存放已經訪問過的節(jié)點。在我們的例子中，G1.蟻群算法在作業(yè)車間的應用［2］k以3個工件2臺機器的問題作為例子，如圖1。1-All.Oil"5-4>m,1-On,5—Chi.4Ok其中.a叢云利始節(jié)點"碩中】為工件的類型.j為工件的該步捉柞在第幾臺機器上進行「圖1三個工件兩臺機器的JSP問題為確定先對哪個工件進行加工，需要設置一個初始節(jié)點00，所有的螞蟻最初都放置在00。圖1中除與00相連的有向弧表示同一個工件的加'工順序，工件必須按照該順序進行加工。其它則為無向弧。每個弧與表示節(jié)點間信息素的量和啟發(fā)式距離的一對值｛a,d｝有關。d通常為對節(jié)點j的第i步ijijij操作的加工時間，t使用蟻周方式進行更新：ij5，6｝，S=｛1,2,3｝。轉移概率是通過下式計k算的：ifkifkealicmvdkT為工件i在機器j上的加工時間。每選擇一個節(jié)ij點，該節(jié)點就被追加到禁忌表中并從G和S中刪kk除；如果被選的節(jié)點不是工件的最后一步，那該工件中緊鄰的下一個節(jié)點會被加到Sk中。該過程一直重復到G=?。最后禁忌表中得到的節(jié)點的排列k順序就是螞蟻k找到的解。參數a和B決定了算法的收斂速度并對解的性能好壞有重要影響，同時蒸發(fā)常數也需要進行適當的調整以使搜索能在好的搜索空間中進行，并防止陷入局部最優(yōu)的鄰域中。蟻群算法已經被成功地運用于10個工件、10臺機器和10個工件、15臺機器的JSP例子中，該算法總能得到最優(yōu)解的10%以內的解，只是該方法的計算復雜性占用了部分執(zhí)行時間，但我們仍可以認為這是一個比較有希望的結果。遺傳算法在作業(yè)車間調度中的應用遺傳算法編碼和解碼［3］編碼與解碼是指染色體和調度解之間進行相互轉換，是遺傳算法成功實施優(yōu)化的首要和關鍵問題。對于傳統(tǒng)的作業(yè)車間調度問題，大多數研究采用基于工序的編碼。但是柔性作業(yè)車間調度問題不僅要確定工序的加工順序，還需為每道工序選擇一臺合適的機器，僅采用基于工序的編碼方法不能得到問題的解。因此，對于柔性作業(yè)車間調度問題，遺傳算法的編碼由兩部分組成，第一部分為基于工序的編碼，用來確定工序的加工先后順序；第二部分為基于機器分配的編碼，用來選擇每道工序的加工機器。融合這兩種編碼方法，即可得到柔性作業(yè)車間調度問題的一個可行解。基于工序的編碼這部分編碼染色體的基因數等于工序總數，每個工件的工序都用相應的工件序號表示，并且工件序號出現的次數等于該工件的工序數。根據工件序號在染色體出現的次序編譯，即從左到右掃描染色體，對于第k次出現的工件序號，表示該工件的第k道工序。對表1所表示的柔性作業(yè)車間調度問題，一個基于工序編碼的基因串可以表示為［12213123］，其中1表示工件J1，2和3意義相同。基因串中的3個1依次表示工件J1的3個工序，分別為工序1、工序2和工序3。2.1.2基于機器分配的編碼設工序總數為l,工序號分別用1,2,3,…，l表示。對于這l道工序，形成l個可選擇機器的子集｛S1,S2,S3,…，Sl｝，第i個工序的可加工機器集合表示為Si,Si中元素個數為ni,表示為｛mi1,mi2,…，mni｝。基于機器分配的編碼基因串的長度為l，表示為［g1,g2,…,gi,…,gl］。其中第i個基因gi為［1,ni］內的整數，是集合Si中的第gi個元素mgi，表示第i個工序的加工機器號。具體地說，若第1道工序有三臺機器作為可選擇機器，則n1=3。設S1=｛M11,M12,M13｝，則第1道工序有M11,M12,M13這3臺機器作為可選機器，根據g1的值從集合S1中確定加工第1道工序所用的機器。若g1=1，則機器M11為加工第1道工序所用的機器。以此類推，確定加工第2,3,…，l道工序所用的機器。對于表1所示的柔性作業(yè)車間調度問題，總共有8道加工工序，假設基于機器分配編碼的基因串為［21231232］，則表示這8道工序的加工機器號分別為［22352344］。解碼時先根據基于機器分配編碼的基因串選擇每道工序的加工機器，然后按基于工序編碼的基因串確定每臺機器上的工序順序。但是確定每臺機器上的工序順序時，按一般解碼方式只能得到半主動調度，而不是主動調度。這里介紹一種插入式貪婪解碼算法，能保證染色體經過解碼后生成主動調度。該解碼算法描述如下：按照工序在該序列上的順序進行解碼，序列上第1道工序首先安排加工，然后取序列上第2道工序，將其插入到對應機器上最佳可行的加工時刻安排加工，以此方式直到序列上所有工序都安排在其最佳可行的地方。交叉操作交叉操作是將種群中兩個個體隨機地交換某些基因，產生新的基因組合，期望將有益的基因組合在一起。染色體中兩部分基因串的交叉分別進行，其中第一部分基于工序編碼基因串的交叉操作采用張超勇等［8］提出的P0X交叉算子，第二部分基于機器分配編碼基因串的交叉采用一種新提出的多點交叉方法。基于工序編碼基因串的交叉這部分交叉操作的過程為：將所有的工件隨機分成兩個集合J1和J2,染色體子代1/子代2繼承父代1/父代2中集合J1內的工件所對應的圖2基于工序編碼的交叉基因，子代1/子代2其余的基因位則分別由父代2/父代1刪除已經繼承的基因后所剩的基因按順序填充，交叉操作過程如圖2所示?；跈C器分配編碼基因串的交叉這部分基因串采用一種新的多點交叉的方法，交叉操作的過程為：首先隨機產生一個由0、1組成與染色體長度相等的集合RandO_l,然后將兩個父代中與RandO_l集合中0位置相同的基因互換,交叉后得到兩個后代。圖2顯示了兩個父代基因父代1/父代2交叉后得到的兩個子代基因子代1/子代2的過程。此外,對于部分柔性作業(yè)車間調度問題,當交叉產生的機器號大于對應工序可利用的機器總數時,在該工序加工機器中隨機選擇一臺機器加工(加工時間短的優(yōu)先選擇)。子吒1213>31123223132*ttt1tt1121I23112J12S232RaiidO1010011D100I1011父代221323111J2Ii1JJiI14!于tv21L23211i113233圖3基于機器分配編碼的交叉變異操作變異操作的目的是改善算法的局部搜索能力,維持群體多樣性,同時防止出現早熟現象。對于改進遺傳算法,基于工序編碼和基于機器分配編碼的變異分別設計如下。2.3.1基于工序編碼的變異這部分基因實施插入變異,即從染色體中隨機選擇一個基因,然后將之插入到一個隨機的位置。2.3.2基于機器分配編碼的變異由于每道工序都可以由多臺機器完成,所以隨機選擇兩道工序,然后在執(zhí)行這兩道工序的機器集合中選擇一臺機器,并將選擇的機器號置入對應的基于機器分配編碼的基因串中,這樣得出的解能確保是可行解?；跈C器分配編碼的變異由于每道工序都可以由多臺機器完成,所以隨機選擇兩道工序,然后在執(zhí)行這兩道工序的機器集合中選擇一臺機器,并將選擇的機器號置入對應的基于機器分配編碼的基因串中,這樣得出的解能確保是可行解。選擇操作在遺傳算法中,選擇是根據對個體適應度的評價從種群中選擇優(yōu)勝的個體,淘汰劣質的個體。在改進遺傳算法中,選擇操作采用最佳個體保存和錦標選擇兩種方法。最佳個體保存方法就是把群體中適應度高的個體不進行配對交叉而直接復制到下一代中，DEJ0NG［9］最早對這種方法作了定義。在本文的改進遺傳算法中,最佳個體保存方法是將父代群體中最優(yōu)的1%個體直接復制到下一代中。錦標選擇是由GOLDBERG等［10］提出的，它是從種群中隨機選擇兩個個體，如果隨機值(在0?1之間隨機產生)小于給定概率值r(概率值r是一個參數，一般設置為0.8)，則選擇優(yōu)的一個，否則就選擇另一個；被選擇的個體放回到種群，可以重新作為一個父染色體參與選擇。2.5基于柔性作業(yè)車間調度問題的改進遺傳算法在傳統(tǒng)遺傳算法求解調度問題時，交叉產生的子代總是被接受，這可能造成優(yōu)良解被丟失或破壞,因此傳統(tǒng)遺傳算法易于早熟且收斂慢。求解柔性作業(yè)車間調度問題比傳統(tǒng)調度問題更復雜，它首先確定工序的加工順序，接著為每道工序選擇一臺加工機器；前者由染色體中基于工序編碼的基因串確定,后者由基于機器分配編碼的基因串確定，結合這兩個基因串可得到一個可行解。針對柔性作業(yè)車間調度問題的這些特點，提出一種雙層子代產生模式的改進遺傳算法，它的交叉操作過程為：對于兩個父代中基于工序的編碼的基因串交叉n次，基于機器分配編碼的基因串交叉nXk次；具體地說，基于工序的編碼的基因串每交叉一次產生兩子代，基于機器分配編碼基因串就交叉k次，這樣能為這兩子代分配更合適的機器，使子代能更好地繼承父代的優(yōu)良特征。這樣兩個父代相當于交叉了nXk次，從所有后代中選擇最優(yōu)的兩個染色體存入下一代。測試結果顯示該方法求解柔性作業(yè)車間調度問題比傳統(tǒng)遺傳算法更有效。改進遺傳算法的步驟如下。初始化隨機產生P個染色體個體，P為種群規(guī)模。評價每個個體適應度值。判斷是否達到終止條件，若滿足則輸出最優(yōu)解；否則轉步驟4。將1%最優(yōu)個體直接復制到下一代中。按選擇策略選取下一代種群。(6a)若兩父代個體適應度不相等并滿足交叉概率Pc，基于雙層子代產生模式對兩父代個體進行交叉，即基于工序編碼的基因串交叉n次，基于機

器分配編碼的基因串交叉nXk次，從所有后代中選擇兩個最優(yōu)的染色體作為下代。(6b)按變異概率Pm,進行變異操作生成新個體。(7)生成新一代種群，返回到步驟(3)。粒子群算法在柔性作業(yè)車間中的應用⑷FJSP描述FJSP問題可以描述為:作業(yè)車間存在M種工件在N臺機器上加工，工件Mi各有Ji道工序(不指定工序的加工機器，允許工序從被選機器中任意選擇)。工件的工序是預先確定的，每道工序可以在一臺或多臺不同的機器上加工。R和X為決策ijegkijk變量。'I0「件的第it匚序和工件喲第髓匸序、在機器吐執(zhí)伉若I［序itJ'-匚序說.o淇他)Lcr.ft的第逍匸庁任機器也執(zhí)疔)調度目標是為每道工序選擇合適的機器，以及確定每臺機器上各工序的最佳加工順序，使系統(tǒng)的總目標達到最優(yōu)。并且加工過程需要滿足以下假設和約束條件：所有機器一開始均處于空閑狀態(tài)；在零時刻，所有的工件都可被加工;工序一旦進行，不能中斷;不同工件的工序之間沒有先后約束，工件之間具備相同的優(yōu)先級;各工件的準備時間和移動時間計入加工時間；同一工件工序間的加工順序約束;同一機器上一個加工任務完成后才能開始另一個任務的加工資源約束。FJSP多目標優(yōu)化模型本文面向的柔性作業(yè)車間多目標調度考慮3個優(yōu)化目標(T,C,D)。T、C、D分別表示制造工期、加工成本和工件提前/拖期懲罰值。

<1制造I：期丁此中凡一匚件任機器啲亢|［葉間式(】威示機器啲完匸時間取決r在其上加匚的所有工件中彊后-個工件的完工時間.◎血I匚成本cMJ,N

minCUmin^工VG上帝⑵1I.—I成中G——匸件帕第適丁序衽機器加丄成本門就前施期懲罰值1>i［ib1'^V|?=］萼巾感⑴Ei-\\}|(3)通過工廠日歷、訂單交貨期和車間加工情況分析確定工件i的最早交貨期D'i和最晚交貨期時間Di，Ei是工件i的完工時間。同時根據工件的交貨優(yōu)先級確定不同工件的提前懲罰系數ri和拖期懲罰系數wi。(4闕束條件順用約範工件的當前匚庁完■后才能開始后道匸序的加T(IV奄1^ii}o=U(4)資源約束;在機罄k上開始個新任務必須在『任務完成后.%—Mg"(\=尬=1I)<5)式中碼人——［件帕第適丁序衽機器町：的抓匚時間冊——L件的第血匚序在機器k|［的完丨.時間CDMOPSO算法在MOPSO運算過程中，各粒子向所經歷的某個非支配的歷史位置(Pb)學習，同時從外部種群中按照一定規(guī)則選擇一個解作為引導者(Gb),在外部種群中存儲從開始到結束運行時粒子群所發(fā)現的非支配解。在運算過程中不斷更新外部種群，在運行結束時其中的解基本就是最終輸出結果。MOPS0算法位置更新公式仍相似于單目標優(yōu)化，即Vj=^rl‘一$畫咄i）〔1饗-W）-聲=耳1十呼⑺式中—速度—粒子位置'J懺性從IJ-tV——丿川速1人仃創(chuàng)誠]h^Iid（2j——1|QIJ間的隨機數3.2.1編碼和解碼FJSP問題的解包含機器選擇和工序調度，因此編碼也要反映這兩方面的內容，為此使用基于工序和機器的兩層編碼方案[15]。粒子的位置向量用2個相互對應的L維向量Xp[L]和Xm[L]來表示，L是工件的總工序數。表1所示是一個3X4的FJSP粒子編碼。解碼時，先通過粒子的Xm[L]向量值確定工序的加工機器，同時將對應的Xp[L]向量轉換為一個有序的操作表，向量中的順序決定了工序調度的優(yōu)先級。然后根據該表，將工序按其調度的優(yōu)先順序在指定的機器上以最早允許加工時間進行加工，產生調度方案。表1某一粒子前編碼TM1CcdhSofa粒子L123斗567萄1|2L323123和||41133J2計算位置和速度粒子的速度矢量也由2部分組成，即Vp[L]和Vm[L]來表示，分別根據式（6）來計算。Xp[L]和Xm[L]根據式（7）來計算。由于FJSP是滿足優(yōu)先權約束的整數規(guī)劃問題，因而粒子在更新時還需進行修正。對計算得到的新值X'p[L]的各分量先按升序排列，再根據排序結果重新排列Xp[L]的各分量。粒子的位置更新過程如表2和表3所示。

表2按陽更新公式計算后xjq2l[ftFtcruPdaticiRTOC\o"1-5"\h\z^I'l2I32312JX；[】}3I22J44.5J.8255.218表3排序更新后的新Xp（]|Tfib3X]l|aftt-'r塔|]}L4].S22251I3.845512Xr|1}3112322因為町SP中工序存在機器約束的情況，在Xm[L]的粒子更新時需要進行修正:①若該分量所對應的工序只存在一臺機器能夠加工，則選擇該工序所對應機器序號更新Xm[L]的分量值。②若存在l臺機器能夠加工該分量對應的工序，其Xm[L]的分量對應值為k1，k2,…,kl,Xm[L]的分量值x在計算后得到x，，則對|ki-x'|（i=l,2，…，1）進行排序，選出其最小值k*，該分量值更新為x=k*。多目標粒子群算法的改進PSO應用于多目標問題時最重要的操作是保持Pareto最優(yōu)解集的多樣性和更新粒子群的全局最優(yōu)值。本文提出的CDMOPS0算法，借鑒密集距離計算方法對個體按密集距離排序，同時采用精英策略保留進化過程中的優(yōu)勢個體，從而保持Pareto集的多樣性和更新全局最優(yōu)值，并引入小概率的變異機制增強算法的全局尋優(yōu)能力。主要采用如下：策略：（1）外部種群更新和縮減在多目標進化算法中，精英策略是在外部種群中存儲每代進化過程中產生的非支配優(yōu)勢個體，并排除外部種群中可能產生的劣勢個體，從而有利于保證多目標進化算法的收斂性和多樣性。本文采用精英策略保留每代進化過程中產生的非支配個體。設內部粒子群為P,外部優(yōu)勢種群為A,在粒子群完成一代飛行后，首先選出P中的非支配個體，然后將所有非支配個體拷貝到A,并且刪除A中的重復個體和被支配個體。若A中個體數超過其種群規(guī)模S,基于Deb在NSGAII中提出的個體密集距離計算方法[17]，計算A中所有個體的密集距離并按降序排列。僅保留前S個個體，刪除多余的最密集個體。否則，不對A進行縮減操作。該方法既通過精英策略保留運算過程中的優(yōu)良粒子，同時保證了外部種群的規(guī)模，避免了運算過程中隨著循環(huán)代數的增加非支配個體數增多，從而保證

了運算的效率;同時,當外部種群個體數超過其規(guī)模時,刪除多余的最密集個體,保留分散個體,從而有效保證了Pareto前沿的均勻分布。全局最優(yōu)值更新完成外部種群A的更新和縮減之后，需更新內來。②對Xm［L］進行基于機器選擇的變異，把可加工該道工序的所有機器放進一個集合，進行變異時則從該工序對應的機器集合中隨機選擇一個機器來替換原有機器，再將變異前后適應度值較優(yōu)的個體保留部粒子群P的全局最優(yōu)值。Gb從A中選擇一個下來。刪除險隼的雪余牛低.保持」1■個悴數対M,離肢婕鈦萌區(qū)橫運霾計尊刪除險隼的雪余牛低.保持」1■個悴數対M,離肢婕鈦萌區(qū)橫運霾計尊A中個悴的密隼距離井按降序排列吏新毎牛粒子的片輸出外部種群兒撫得撾優(yōu)前誥執(zhí)冇基于丁錚駅序和堆?］?機書選擇的竟異處于最分散區(qū)域的個體，引導粒子群向Pareto最優(yōu)前沿分散區(qū)域的進化。Gb的更新分為兩種情況：①當A中僅包含邊界個體時，即A中所有個體的密集距離為無窮大，Gb則從中隨機選擇一個邊界個體。②當A中包括若干個密集距離不為無窮大的個體時，則隨機選擇一個密集距離較大的個體作為Gd，其計算公式為A訃譏應叫|⑴.丫忙｝)(S)式屮rn一外部種群/沖包含個休數呈°—種胖/沖按密菠距離降序排列時訂個密集蹈離不為無芳人的個體序號I且nl0.I<ni眄保證逸擇范懵在費集距離粒大的個體區(qū)間內.在該區(qū)問內隨機選樣「個個體作為G呻％q》——|%引之間一個隨機整數的