裝配作業(yè)車間調(diào)度的免疫粒子群算法實(shí)現(xiàn)

孫 虎，周晶燕

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

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

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

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

1.1 問(wèn)題定義

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

1.2 研究現(xiàn)狀

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

2 粒子群算法模型

首先初始化n個(gè)D維粒子的位置與速度，第i(i=1,2,…，n)個(gè)粒子的位置為xi=[xi1,xi2,…,xiD]。速度為vi=[vi1,vi2,…,viD],d=1,2,…,D。粒子在飛行過(guò)程中不斷迭代更新自己的速度和位置，其迭代規(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個(gè)粒子經(jīng)歷過(guò)的具有最好適應(yīng)度值的位置，記作pi=[pi1,pi2,…,piD]；pg為整個(gè)粒子群經(jīng)歷過(guò)的具有最好適應(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 免疫粒子群算法實(shí)現(xiàn)

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

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

3.1 算法重要參數(shù)

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

首先.對(duì)于三維歐式空間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è)定一個(gè)濃度抑制半徑σ，取值為0.1，將距離小于σ的粒子看作是相似。粒子濃度的計(jì)算公式為：

(5)

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

(6)

其中,β取值為2。

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

(7)

3.2 編碼與解碼

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

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

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

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

對(duì)于解碼問(wèn)題，定義所有前序工序都完成的工序?yàn)榭烧{(diào)度工序。如對(duì)于工序4，只有工序5和工序6都完成時(shí)其才為可調(diào)度。考慮所有產(chǎn)品的可調(diào)度工序，每次從中選取一個(gè)隨機(jī)數(shù)最小的優(yōu)先安排到最早的時(shí)間進(jìn)行加工，重復(fù)進(jìn)行一直到所有工序都被完成。按照這個(gè)規(guī)則，工序的加工順序?yàn)?、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個(gè)粒子作為父代，交叉變異后得到2個(gè)粒子作為子代，從父代和子代4個(gè)粒子中選擇適應(yīng)度最好的1個(gè)粒子作為下一代。重復(fù)population_size次，得到新的種群。

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

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

3.4 算例

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

3.4.1 重復(fù)試驗(yàn)求解

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

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

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

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

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

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

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

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

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

(3)類型3產(chǎn)品的具體運(yùn)行結(jié)果如表4所示，類型3產(chǎn)品不同種群大小結(jié)果對(duì)比如圖7所示，類型3產(chǎn)品不同算法結(jié)果對(duì)比如圖8所示?？芍?dāng)種群大小為15時(shí)尋得的當(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é)果對(duì)比

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

3.4.2 算法收斂性分析

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

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

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

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

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

(3)類型3產(chǎn)品運(yùn)行結(jié)果如圖11所示。在100 s內(nèi)，PSO、IPSO、EIPSO這3種算法分別迭代了790次、352次、370次。其中,PSO在第66次迭代時(shí)收斂到了最優(yōu)值103.025，IPSO在第246次迭代時(shí)收斂到了最優(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)度問(wèn)題是現(xiàn)代制造業(yè)技術(shù)的基礎(chǔ)，而裝配環(huán)節(jié)更是產(chǎn)品制造中不可或缺的部分。筆者通過(guò)設(shè)置多次的重復(fù)試驗(yàn)求解AJSS問(wèn)題，證實(shí)了免疫粒子群算法求解裝配作業(yè)車間調(diào)度問(wèn)題的實(shí)用性和有效性。研究還發(fā)現(xiàn)：對(duì)于相對(duì)簡(jiǎn)單的產(chǎn)品，PSO與兩種基于免疫的算法(IPSO、EIPSO)的差別比較??；但是對(duì)于規(guī)模較大(類型3)的產(chǎn)品，IPSO比PSO更好地避免早熟，得到的結(jié)果也更好。如果給定比較合理的搜索時(shí)間，IPSO和EIPSO基本上都能夠找到比PSO更好的解。

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