孫 虎，周晶燕

(武漢理工大學(xué) 物流工程學(xué)院，湖北 武漢 430063)

裝配作業(yè)車間調(diào)度(AJSS)是生產(chǎn)中常見的生產(chǎn)組織形式，具有復(fù)雜的物料清單結(jié)構(gòu)，包含多層裝配節(jié)點，其生產(chǎn)調(diào)度更加有挑戰(zhàn)性，相關(guān)研究相對較少。為充分利用制造資源，提升企業(yè)核心競爭力,有必要對裝配車間生產(chǎn)調(diào)度進(jìn)行優(yōu)化。

目前，學(xué)者多采用遺傳算法求解AJSS問題，較少見粒子群算法和免疫粒子群算法在這一領(lǐng)域的應(yīng)用研究。故筆者采用免疫粒子群算法求解最小化最大完工時間的裝配作業(yè)車間調(diào)度模型，綜合考慮粒子群算法和免疫算法各自的求解特點，通過多次重復(fù)試驗驗證免疫粒子群算法求解的高效性和實用性。

1 裝配作業(yè)車間調(diào)度

1.1 問題定義

AJSS問題是在調(diào)度的初始時刻，知道所有要調(diào)度產(chǎn)品的詳細(xì)信息，包括產(chǎn)品結(jié)構(gòu)和工序詳細(xì)信息。該問題的優(yōu)化目標(biāo)是確定每個工序在每一臺機(jī)器上的開始時間和完成時間，使得總加工時間最小。

1.2 研究現(xiàn)狀

近年來，針對AJSS這一類NP-hard問題，學(xué)者們已提出一系列求解該問題的調(diào)度算法。如TAVAKKOLI-MOGHADDAM等[1]研究了一個層次化的分支定界算法來解決裝配操作的混合流裝配作業(yè)車間調(diào)度問題。TIAN等[2]提出了一種離散粒子群優(yōu)化算法來解決兩階段裝配調(diào)度問題。SUNG等[3]利用解的性質(zhì)給出了一種分支定界算法，來求解兩階段的多機(jī)器裝配調(diào)度問題。 SHOKROLLAHPOUR等[4]研究了一個以最大完工時間和平均完工時間加權(quán)和最小化為目標(biāo)的兩階段裝配流程車間調(diào)度問題，提出了一種新的元啟發(fā)式帝國競爭算法。LIAO等[5]研究了N個產(chǎn)品的裝配調(diào)度問題，將該問題表述為一個混合整數(shù)規(guī)劃模型，并提出了求解最優(yōu)解的若干性質(zhì)。MOZDGIR等[6]提出了一種混合變量鄰域搜索類電磁機(jī)制算法來求解一個兩階段裝配流程車間調(diào)度問題。WONG等[7]提出了兩種拉格朗日松弛技術(shù)的混合進(jìn)化算法，以最小化最大完工時間為目標(biāo)。AL-ANZI等[8]提出了一種AJSS人工免疫系統(tǒng)，目標(biāo)是最小化總工時或平均完成時間,并提出了用混合禁忌搜索(TS)啟發(fā)式算法來求解AJSS問題[9]。

2 粒子群算法模型

首先初始化n個D維粒子的位置與速度，第i(i=1,2,…，n)個粒子的位置為xi=[xi1,xi2,…,xiD]。速度為vi=[vi1,vi2,…,viD],d=1,2,…,D。粒子在飛行過程中不斷迭代更新自己的速度和位置，其迭代規(guī)則為：

v′id=ωvid+c1r(pid-xid)+c2R(pgd-xid)

(1)

x′id=xid+vid

(2)

式中：c1，c2為常量，通常在0到2之間取值；r和R服從0到1的均勻分布；pi為第i個粒子經(jīng)歷過的具有最好適應(yīng)度值的位置，記作pi=[pi1,pi2,…,piD]；pg為整個粒子群經(jīng)歷過的具有最好適應(yīng)度值的位置，記作pg=[pg1,pg2,…,pgD]；ω為慣性權(quán)重。這里采用自適應(yīng)調(diào)節(jié)，即ω隨著迭代次數(shù)的增加線性減少：

ω=ωmax-in(ωmax-ωmin)/imax

(3)

式中：ωmax和ωmin分別為ω的初始值與終止值；imax為最大迭代次數(shù)；in為當(dāng)前迭代次數(shù)。

3 免疫粒子群算法實現(xiàn)

粒子群算法的一個問題在于容易過早收斂，導(dǎo)致局部最優(yōu)，免疫算法特有的濃度抑制機(jī)制可以防止適應(yīng)度較高的粒子過度繁殖，幫助維持粒子的多樣性，彌補了粒子群算法過早收斂的缺陷。免疫粒子群算法(immune particle swarm optimization, IPSO)就是將兩者進(jìn)行結(jié)合的混合算法。

劉國聯(lián)等[10]針對遺傳算法提出了“精英替代”策略，其基本思想是將種群中適應(yīng)度最低的個體淘汰，用精英個體替代。筆者嘗試對免疫粒子群算法做這樣的改進(jìn)，研究其在解決AJSS問題中是否有效，算法簡稱為EIPSO。

3.1 算法重要參數(shù)

(1)種群大小(n)。種群大小指粒子的總數(shù)，粒子數(shù)目的多少對搜索效率有一定的影響，需要通過實驗確定合適的數(shù)目。

首先.對于三維歐式空間3的一組不共面的向量e1,e2,e3,我們可以唯一以其作為一組基底構(gòu)造仿射坐標(biāo)系.記gij=ei·ej,由于內(nèi)積的交換性,故

(3)粒子間的距離(distance)。選擇Euclidean距離，將粒子x1=[x11,x12,…,x1D]和x2=[x21,x22,…,x2D]的距離定義為：

(4)

(4)濃度(density)。粒子的濃度即抗體的濃度，指群體中相似抗體所占的比重。這里設(shè)定一個濃度抑制半徑σ，取值為0.1，將距離小于σ的粒子看作是相似。粒子濃度的計算公式為：

(5)

(5)激勵度(actuation_probability)。激勵度這個概念出現(xiàn)在免疫算法中，指抗體群中抗體應(yīng)答抗原和其他抗體激活的綜合能力。

(6)

其中,β取值為2。

(6)選擇概率(selection_probability)。選擇概率是該粒子(抗體)的激勵度占所有粒子激勵度的比重：

(7)

3.2 編碼與解碼

某實例的裝配作業(yè)結(jié)構(gòu)圖如圖1所示，可知兩個裝配產(chǎn)品，一共有6個工序。不同工序的加工時間、所需機(jī)器如表1所示。

圖1 裝配作業(yè)結(jié)構(gòu)圖

工序加工時長/min編碼隨機(jī)數(shù)加工機(jī)器130.3M1250.5M2370.2M3460.6M2520.6M1640.8M2

筆者采用隨機(jī)數(shù)編碼，對每個工序給一個0～1之間的隨機(jī)數(shù)。這里規(guī)定隨機(jī)數(shù)越小表示優(yōu)先級越大，即粒子的編碼為x1=(0.3,0.5,0.2,0.6,0.6,0.8)。

對于解碼問題，定義所有前序工序都完成的工序為可調(diào)度工序。如對于工序4，只有工序5和工序6都完成時其才為可調(diào)度?？紤]所有產(chǎn)品的可調(diào)度工序，每次從中選取一個隨機(jī)數(shù)最小的優(yōu)先安排到最早的時間進(jìn)行加工，重復(fù)進(jìn)行一直到所有工序都被完成。按照這個規(guī)則，工序的加工順序為3、2、1、5、6、4，最終調(diào)度結(jié)果如圖2所示。

圖2 工件加工順序圖

3.3 算法步驟

(1)初始化系統(tǒng)。用戶設(shè)定相應(yīng)的參數(shù)，隨機(jī)產(chǎn)生規(guī)模為population_size的種群，此為第一代。

(2)基于免疫的選擇、交叉、變異更新。根據(jù)式(7)，每次選擇2個粒子作為父代，交叉變異后得到2個粒子作為子代，從父代和子代4個粒子中選擇適應(yīng)度最好的1個粒子作為下一代。重復(fù)population_size次，得到新的種群。

(3)對步驟(2)得到的種群根據(jù)粒子群算法進(jìn)行更新，得到下一代種群。

(4)如果達(dá)到循環(huán)終止條件，則退出循環(huán)，否則返回到步驟(2)。

3.4 算例

算例應(yīng)用Visual Studi.Net編程實現(xiàn)，比較EIPSO、IPSO和PSO在不同問題規(guī)模和復(fù)雜度下的表現(xiàn)。系統(tǒng)生成3種不同類型的產(chǎn)品，類型1～3的層級分別為2,3,4，第1～3層的下屬分支數(shù)分別服從[2-5],[2-4],[2-3]的均勻離散分布。每個分支的工序數(shù)服從[1-8]的均勻分布。每個工序的加工時間為均值為1的負(fù)指數(shù)分布。

3.4.1 重復(fù)試驗求解

為了在相同條件下比較不同算法，統(tǒng)一設(shè)定3種方法的計算時間上限為10 s，交叉和變異概率分別取0.8和0.1。對于每種產(chǎn)品類型，生成6個產(chǎn)品作為一個算例。對于每個算例，種群大小n取5、10、15共3種設(shè)定，并采用3種不同的算法計算，一共有3×3=9種設(shè)定。

(1)針對最簡單的類型1、雙層結(jié)構(gòu)的產(chǎn)品，不同設(shè)定的求解結(jié)果如表2所示，類型1產(chǎn)品不同種群大小結(jié)果對比如圖3所示，類型1產(chǎn)品不同算法結(jié)果對比如圖4所示。由于類型1產(chǎn)品相對簡單，求解結(jié)果差異不大。唯一的例外是IPSO、種群大小為5的情況，取值較差，但絕對數(shù)值相差并不大。結(jié)合圖3和圖4可知，其均值數(shù)據(jù)也反映了這種差異。

表2 類型1產(chǎn)品優(yōu)化結(jié)果表

圖3 類型1產(chǎn)品不同種群大小結(jié)果對比

圖4 類型1產(chǎn)品不同算法結(jié)果對比

(2)類型2產(chǎn)品的具體運行結(jié)果如表3所示，類型2產(chǎn)品不同種群大小結(jié)果對比如圖5所示，類型2產(chǎn)品不同算法結(jié)果對比圖6所示。結(jié)合圖5和圖6可知，當(dāng)種群大小為15時，算法尋得的當(dāng)前最優(yōu)解最好。而在3種算法之中，EIPSO算法尋得的當(dāng)前最優(yōu)解最好，PSO算法最差，IPSO居中。

表3 類型2產(chǎn)品優(yōu)化結(jié)果表

圖5 類型2產(chǎn)品不同種群大小結(jié)果對比

圖6 類型2產(chǎn)品不同算法結(jié)果對比

(3)類型3產(chǎn)品的具體運行結(jié)果如表4所示，類型3產(chǎn)品不同種群大小結(jié)果對比如圖7所示，類型3產(chǎn)品不同算法結(jié)果對比如圖8所示。可知當(dāng)種群大小為15時尋得的當(dāng)前最優(yōu)解最好，而在這3種算法之中，EIPSO算法尋得的當(dāng)前最優(yōu)解是最好的，PSO算法表現(xiàn)最差。

表4 類型3產(chǎn)品優(yōu)化結(jié)果表

圖7 類型3產(chǎn)品不同種群大小結(jié)果對比

圖8 類型3產(chǎn)品不同算法結(jié)果對比

3.4.2 算法收斂性分析

由上文可知，在短時間內(nèi)EIPSO的表現(xiàn)最佳，但是較短的時間不能保證3種算法都達(dá)到收斂，因此無法得出定論。故針對不同類型的產(chǎn)品，保持其他參數(shù)不變，延長運行時間至100 s進(jìn)行收斂性分析，重點比較這3種算法解決問題的不同表現(xiàn)。種群大小為上述短時間內(nèi)不同產(chǎn)品求解的最佳設(shè)定，依次為10,10,15。

圖9 類型1產(chǎn)品優(yōu)化結(jié)果折線圖

(1)類型1產(chǎn)品運行結(jié)果如圖9所示。在100 s內(nèi)，PSO、IPSO、EIPSO這3種算法分別迭代了2 370次、1 317次、1 315次。其中，PSO在第12次迭代時收斂到了最優(yōu)值，IPSO和EIPSO在第3次迭代時收斂到了最優(yōu)值，三者最優(yōu)值相同。類型1產(chǎn)品的結(jié)構(gòu)比較簡單，包含的工序數(shù)少，解的搜索空間比較小，所以3種方法基本上都能夠迅速收斂到一個值。不同之處在于收斂速度，其中PSO收斂最慢，IPSO和EIPSO收斂速度相似。

(2)類型2產(chǎn)品運行結(jié)果如圖10所示。在100 s內(nèi)，PSO、IPSO、EIPSO這3種算法分別迭代了1 818次、773次、777次。其中，PSO在第49次迭代時收斂到了最優(yōu)值42.974，IPSO在第11次迭代時收斂到了最優(yōu)值42.965，EIPSO在第175次收斂到了最優(yōu)值42.965。IPSO和EIPSO最后找到的最優(yōu)值相同，都好于PSO的最優(yōu)值。另外，值得注意的是，IPSO在這個例子中比EIPSO收斂得更快。

圖10 類型2產(chǎn)品優(yōu)化結(jié)果折線圖

(3)類型3產(chǎn)品運行結(jié)果如圖11所示。在100 s內(nèi)，PSO、IPSO、EIPSO這3種算法分別迭代了790次、352次、370次。其中,PSO在第66次迭代時收斂到了最優(yōu)值103.025，IPSO在第246次迭代時收斂到了最優(yōu)值102.079，EIPSO在第37次收斂到了最優(yōu)值102.163?？梢钥闯?，PSO表現(xiàn)最差，EIPSO次之，IPSO最好。

圖11 類型3產(chǎn)品優(yōu)化結(jié)果折線圖

4 結(jié)論

作業(yè)車間調(diào)度問題是現(xiàn)代制造業(yè)技術(shù)的基礎(chǔ)，而裝配環(huán)節(jié)更是產(chǎn)品制造中不可或缺的部分。筆者通過設(shè)置多次的重復(fù)試驗求解AJSS問題，證實了免疫粒子群算法求解裝配作業(yè)車間調(diào)度問題的實用性和有效性。研究還發(fā)現(xiàn)：對于相對簡單的產(chǎn)品，PSO與兩種基于免疫的算法(IPSO、EIPSO)的差別比較小；但是對于規(guī)模較大(類型3)的產(chǎn)品，IPSO比PSO更好地避免早熟，得到的結(jié)果也更好。如果給定比較合理的搜索時間，IPSO和EIPSO基本上都能夠找到比PSO更好的解。

在收斂性分析中，針對免疫粒子群算法加入“精英替代”策略的改進(jìn)問題，由于“精英替代”策略減少了粒子的多樣性，導(dǎo)致EIPSO比IPSO更容易陷入局部最優(yōu)解。因此，在未來的研究中，如何權(quán)衡“擇優(yōu)”與“保留粒子多樣性”仍是一個值得深入探索的問題。