基于改進(jìn)蛙跳算法的可重構(gòu)裝配線調(diào)度研究

，，，

(浙江工業(yè)大學(xué) 機(jī)械工程學(xué)院,浙江 杭州 310014)

近年來，制造企業(yè)都面臨著許多變化，在一個(gè)動態(tài)的市場環(huán)境中，企業(yè)需要新的生產(chǎn)條件來滿足市場個(gè)性化需求和市場的快速轉(zhuǎn)換，所以我們希望盡量減少制造系統(tǒng)和設(shè)備的投資，減少轉(zhuǎn)換所需的準(zhǔn)備工作，提高產(chǎn)品質(zhì)量，增強(qiáng)在競爭激烈的市場的適應(yīng)能力.因此，需要一種制造組裝線，來提供快速，有效的可重新配置的功能.在這種情況下，可重構(gòu)裝配裝配線調(diào)度有一個(gè)很現(xiàn)實(shí)的理論和實(shí)踐意義.

可重構(gòu)裝配線(Reconfigurable assembly line，RAL)[1-2]是一類基于現(xiàn)有的裝配線基礎(chǔ)結(jié)構(gòu)，重建和改變該裝配線的各種結(jié)構(gòu)，并調(diào)整裝配線的現(xiàn)有功能和裝配能力，來滿足市場需求變化.Ding等[3]研究使用的生產(chǎn)計(jì)劃周期P和品種k的可重構(gòu)裝配生產(chǎn)線調(diào)度和生產(chǎn)計(jì)劃問題，首先提出了兩個(gè)階段的方法，就是，所有的產(chǎn)品周期率的平衡式及平衡部件的消耗率和使用速率.Kubiak[4]可重構(gòu)裝配生產(chǎn)線計(jì)劃進(jìn)行全面闡述講解，但提出方法是難以滿足實(shí)際的調(diào)度的要求，尤其是當(dāng)規(guī)模的問題大的和非常復(fù)雜的.黃雪梅等[5]的agent和holon混合想法代理提供基于可重構(gòu)裝配生產(chǎn)線和其他基礎(chǔ)設(shè)施，以實(shí)現(xiàn)的基本結(jié)構(gòu)理論的分析，并提出了數(shù)字化制造技術(shù)下的結(jié)構(gòu)信息可重構(gòu)裝配生產(chǎn)線仿真平臺.余劍鋒[6]可重構(gòu)制造系統(tǒng)調(diào)度優(yōu)化過程中，具有系統(tǒng)的自我分析，以及其他相關(guān)功能，并且保持一定程度的靈活性和可重構(gòu)性.分析現(xiàn)有的研究，大多是單一的裝配生產(chǎn)線調(diào)度目標(biāo)優(yōu)化，但可重構(gòu)裝配生產(chǎn)線，簡單的優(yōu)化目標(biāo)，難以滿足實(shí)際需要，因此需要研究和組合更多的裝配線調(diào)度優(yōu)化的目標(biāo)，以及為重新構(gòu)裝配線多目標(biāo)優(yōu)化提出一個(gè)典型的組合優(yōu)化模型.數(shù)學(xué)編程方法可以解決一些問題但局限性較大，目前迫切需要一種新的高效算法解決去可重構(gòu)裝配線多目標(biāo)調(diào)度問題.

1 可重構(gòu)裝配線調(diào)度問題描述

1.1 可重構(gòu)裝配線

剛性裝配線的產(chǎn)生，以適應(yīng)高容量，高生產(chǎn)效率的裝配系統(tǒng)，但缺乏靈活性.柔性裝配線提供了冗余能力和生產(chǎn)能力，實(shí)現(xiàn)了系統(tǒng)的靈活性，但是其昂貴的系統(tǒng)及硬件投資是一個(gè)重要制約因素.可重構(gòu)制造系統(tǒng)的可重構(gòu)裝配裝配線是其一個(gè)非常重要的部分，它將被應(yīng)用到可重構(gòu)制造裝配系統(tǒng)中，以建立本地和全局化的模塊化、自動化生產(chǎn)的系統(tǒng)，讓系統(tǒng)具有靈活的生產(chǎn)能力，快速反應(yīng)能力和可重構(gòu)能力.

1.2 可重構(gòu)裝配線調(diào)度模型描述

注，這項(xiàng)研究是基于以下假設(shè)[8]：1)各類產(chǎn)品通過每個(gè)可重構(gòu)裝配順序裝配生產(chǎn)線工作站；2)可重構(gòu)裝配線工作站成立的每一塊設(shè)備，產(chǎn)品的標(biāo)準(zhǔn)處理時(shí)間已確定；3)如果一個(gè)任務(wù)需要多個(gè)處理設(shè)備，每個(gè)設(shè)備具有相同的生產(chǎn)容量；4)工人完成上一產(chǎn)品處理后，返回到下一單元產(chǎn)品的時(shí)間可以忽略不計(jì).

2 調(diào)度的目標(biāo)函數(shù)設(shè)計(jì)

可重構(gòu)裝配生產(chǎn)線，以反映調(diào)度負(fù)載均衡，產(chǎn)生平滑和低成本的生產(chǎn)理念，因此根據(jù)具體的工廠現(xiàn)狀，可同時(shí)考慮最小重構(gòu)裝配線成本、最小零部件需求變化率、最小延誤工作量三個(gè)優(yōu)化目標(biāo)，建立各目標(biāo)函數(shù).

2.1 最小重構(gòu)裝配線成本

假定在可重構(gòu)裝配線上[7]，線上有r個(gè)工作站，這些不同的工作站組成了一個(gè)集合Jw，Jw= {1,2,…,r}.且這些線上工作站的長度為Lj(j=1,2,…,r)，平順勻速的皮帶連接著各個(gè)工作站，并且傳送速度為vc，產(chǎn)品投產(chǎn)到可重構(gòu)裝配線上是以固定的周期tc，tjB為工作時(shí)間，特指制品j在工作站B上；在裝配區(qū)間里，Eij為第i個(gè)制品進(jìn)入第j個(gè)工作站的后，工人開始裝配過程中所需要的行走距離；E1j為制品開始投產(chǎn)的初始工人行走距離，且E1j=0.

為了調(diào)度在不同的生產(chǎn)工藝流水線中的可重構(gòu)裝配線，往往是對設(shè)備，工具和裝夾設(shè)備等進(jìn)行各種調(diào)整，甚至有時(shí)需要重建整個(gè)裝配生產(chǎn)線，因此調(diào)整的成本是不同的.因?yàn)橹圃鞓I(yè)的低率潤，所以應(yīng)將最小重構(gòu)裝配線成本作為最重要的調(diào)度目標(biāo)來考慮.給出了一個(gè)最小重構(gòu)裝配線的數(shù)學(xué)模型，并運(yùn)用到實(shí)際生產(chǎn)中，其目標(biāo)函數(shù)為

(1)

其中：Cjmn為在工作站j這個(gè)范圍內(nèi)，由裝配類型m轉(zhuǎn)變成n時(shí)所需要的調(diào)整總費(fèi)用；N為制品類別為n時(shí)總數(shù)量.

2.2 最小零部件需求變化率

可重構(gòu)裝配線調(diào)度要滿足的另一個(gè)重要目標(biāo)就為生產(chǎn)的順滑和穩(wěn)定性，就是要求裝配線對各種配件需求變化率小.引用Toyota公司經(jīng)典調(diào)度目標(biāo)函數(shù)[9]，構(gòu)建相應(yīng)模型為

(2)

其中：i為制品的約定標(biāo)識號；P為線上需求的零配件類別總數(shù)目；p為調(diào)度中子裝配的銘號；βi，p為在調(diào)度過程中，前i-1的位置總消耗零配件p的總和；K為裝配線上制品類別的總數(shù)目；k為制品型號數(shù)的標(biāo)識號；dk為在一個(gè)生產(chǎn)循環(huán)中型號k的數(shù)目；αp為零配件p的理想消耗速率；βkp為制造產(chǎn)品型號k時(shí)，需要的零配件p的數(shù)目之和.

2.3 最小延誤工作量

可重構(gòu)裝配線最小延誤工作量[10](包括工人等待時(shí)間可轉(zhuǎn)換成的工作量和產(chǎn)品過多投入而不能完成的工作量)，其可以反映裝配線效率高低和工人的勞動強(qiáng)度率，其目標(biāo)函數(shù)為

(3)

(4)

(5)

其中：I為一個(gè)生產(chǎn)循環(huán)中需要裝配的產(chǎn)品總數(shù)量；J為工作站總數(shù)；W1為工人等待時(shí)間可轉(zhuǎn)換的工作量；W2為產(chǎn)品過多投入而不能完成的工作量.

在現(xiàn)有算法中，通常將多個(gè)目標(biāo)糅合成一個(gè)目標(biāo)，雖然這樣操作可以得到一個(gè)顯而易見的結(jié)果，但也將弱化各個(gè)目標(biāo)各自的實(shí)際意義.并且，由于糅合方法的無標(biāo)準(zhǔn)性和各個(gè)企業(yè)的獨(dú)特性，糅合將導(dǎo)致調(diào)度結(jié)果的失真[11],所以給出的為一個(gè)非劣解集，決策者可以根據(jù)企業(yè)實(shí)際調(diào)度情況來選擇合適的調(diào)度方案.

約束條件如下：

1) 最小重構(gòu)裝配線成本目標(biāo)函數(shù)約束：

(6)

(7)

(8)

(9)

(10)

其中：式(6)為制品位置固定約束，確保制品在生產(chǎn)排序中，某個(gè)位置只被分配某一種制品；式(7)和式(8)保證不斷循環(huán)這個(gè)過程中，維持原先預(yù)設(shè)的調(diào)度方式；式(9)為滿足MPS要求；式(10)為一個(gè)布爾變量.

2) 最小零部件需求變化率目標(biāo)函數(shù)約束：

(11)

(12)

(13)

(14)

其中：式(11)為在生產(chǎn)中，某一個(gè)時(shí)間段時(shí)間內(nèi)，一個(gè)站只能生產(chǎn)一種制品；式(12)為確保一種制品的最小MPS.

3) 最小延誤工作量目標(biāo)函數(shù)約束：

(15)

(16)

(17)

其中：式(15)為為在生產(chǎn)中，某一個(gè)時(shí)間段時(shí)間內(nèi)，一個(gè)站只能生產(chǎn)一種制品；式(16)確保一種制品的最小的MPS.

3 求解模型的SFLA-PSO優(yōu)化算法

3.1 算法的流程

步驟1初始化青蛙種群的數(shù)量n和每個(gè)種群青蛙的個(gè)數(shù)m(即可行解)這兩個(gè)算法的基礎(chǔ)參數(shù)，并且每個(gè)青蛙個(gè)體的維數(shù)為D，因此，總的初始青蛙個(gè)數(shù)就為F=mn，最大迭代次數(shù)Tmax，加速常數(shù)c1和c2[12].

步驟2通過啟發(fā)式算法(EH，SPT與EDD)產(chǎn)生三個(gè)高質(zhì)量解和以隨機(jī)方式構(gòu)造的共F個(gè)初始解.

步驟3逐個(gè)計(jì)算種群內(nèi)青蛙個(gè)體的適應(yīng)度值，并從當(dāng)中得到種群的最優(yōu)解Pg，然后在全群體中進(jìn)行更新.

步驟4把經(jīng)過適應(yīng)度值計(jì)算過后的青蛙個(gè)體皆分配到m個(gè)種群當(dāng)中，來實(shí)現(xiàn)基于PSO算法的局部搜索[13].

1) 通過粒子群算法中的個(gè)體更新策略來更新最差青蛙PW的位置；

2) 對新產(chǎn)生的青蛙個(gè)體與舊的青蛙個(gè)體進(jìn)行比較，區(qū)分優(yōu)劣，選擇優(yōu)秀進(jìn)行保留；

3) 循環(huán)進(jìn)行蛙群種群內(nèi)部局部搜索，達(dá)到預(yù)設(shè)的迭代次數(shù)為止，則進(jìn)行步驟5.

步驟5判別是否已經(jīng)滿足預(yù)設(shè)優(yōu)化條件(理想的適應(yīng)值大小或預(yù)設(shè)的最大迭代次數(shù))，若已達(dá)到，則要輸出全群體最優(yōu)解.否則需循環(huán)步驟3到4.

改進(jìn)蛙跳算法求解多目標(biāo)可重構(gòu)裝配線調(diào)度流程如圖1所示.

3.2 算法的具體設(shè)計(jì)

在求解大規(guī)模非確定性困難問題(NP-hard)上，通過蛙跳算法，具有良好的表現(xiàn)，其進(jìn)化方程描述為

Si=rand()(Pb-Pw)

(18)

Pw(k+1)=Pw(k)+Si

(19)

Smax≥Si≥-Smax

其中：rand()∈[0，1](k=1，2，…，n)；Smax為最大步長.且針對多目標(biāo)可重構(gòu)裝配線調(diào)度問題，建模出了基于三個(gè)較不關(guān)聯(lián)和重要的目標(biāo)的可重構(gòu)裝配線數(shù)學(xué)調(diào)度模型，并提出了一種基于蛙跳算法的多目標(biāo)改進(jìn)算法綜合運(yùn)用了非劣解存放于精英解集當(dāng)中，并結(jié)合小生境法維護(hù)精英解集，從而使精英解集穩(wěn)定.用三種啟發(fā)式算法得到高質(zhì)量初始解[14].該算法在工廠實(shí)例進(jìn)行測試，通過與其他多目標(biāo)算法的結(jié)果對比分析，驗(yàn)證了算法求解的高效性.

圖1 改進(jìn)蛙跳算法求解多目標(biāo)可重構(gòu)裝配線調(diào)度流程圖

1) 個(gè)體編碼

運(yùn)用了隨機(jī)編碼(Smallnest position value，SPV)[15]方式來確定連續(xù)青蛙個(gè)體的位置，表示為Xi={xi，1，xi，2，…，xi，n}，蛙個(gè)體對應(yīng)到一個(gè)隨機(jī)的加工順序π=(j1，j2，…，jn).表1為制品加工順序和編碼中位置矢量的關(guān)系[12].

解得工件排序π=(3，5，6，4，2，1).

2) 初始化

采用啟發(fā)式算法和隨機(jī)方式兩種方式來產(chǎn)生初始解，EDD，NEH與SPT算法可產(chǎn)生三個(gè)較高質(zhì)量的初始解，剩余的解隨機(jī)產(chǎn)生.

3) 小生境法保護(hù)精英解集

精英解集保護(hù)用小生境法[12]，每一代生產(chǎn)的非劣解將進(jìn)入精英解集之中，且刪除相互關(guān)聯(lián)解.如果超過解集容量，則使用小生境法逐個(gè)計(jì)算，按照計(jì)算值排序，刪除小值.適應(yīng)度計(jì)算方法為

(20)

(21)

(22)

(23)

其中：F(p)為p的適應(yīng)度值；a為常數(shù)；Q為非劣解的個(gè)數(shù)；σshare為小生境半徑；sh(dpq)為個(gè)體p和q的共同享用數(shù)；dpq為兩蛙體間向量距離.

4) 蛙群多樣性

采用青蛙個(gè)體間的支配關(guān)系與密度聯(lián)系結(jié)合來確定適應(yīng)度值.先要將蛙群體內(nèi)所有非支配解按聚集距離值降序排列，求得解排序P1=(P1,P2,…,PL)，L為群體中非支配解的數(shù)量.

聚集距離P[i]distance計(jì)算式為

(24)

然后計(jì)算群體中支配的解和其距離最相近的非支配解，在解維度中的歐氏距離D[i]distance，且按照升序得到序列P2=(PL+1,PL+2，…,PF).按個(gè)體順序合并成兩個(gè)序列P1和P2，最終得到初始解個(gè)體排序集合P={P1,P2}=(P1,P2,…,PF)接著劃分到M個(gè)種群中，每個(gè)種群中有N個(gè)青蛙.

(25)

5) 基于PSO的局部搜索過程

針對調(diào)度解個(gè)體中無明顯關(guān)系，同時(shí)結(jié)合了粒子群算法中的粒子更新策略，提出了新的個(gè)體更新方法.種群內(nèi)采用的搜索方法[15]如下：

步驟1確定最優(yōu)蛙體為Pb、最差蛙體為Pw、種群最優(yōu)蛙體為Pg，且Pb對應(yīng)種群Y1，Pw對應(yīng)種群YN.且要從精英解集中獲得Pg，來引領(lǐng)解的進(jìn)化方向.

步驟2利用PSO算法的個(gè)體更新策略，變換Pw的運(yùn)動速度和位置，用Pb替代歷史最好位置的個(gè)體，個(gè)體更新計(jì)算式為

Xw=c1rand1()Vid+c2rand2()(Pb-Xw)

(26)

Xw=Xoldw+Xw

(27)

其中：rand1()，rand2()分別為[0，1]之間的隨機(jī)數(shù).

步驟3對比新產(chǎn)生的個(gè)體與舊個(gè)體的好壞，取優(yōu).

步驟4繼續(xù)進(jìn)行局部種群內(nèi)搜索，直到滿足預(yù)定迭代的次數(shù)為.

4 實(shí)際案例驗(yàn)證分析

YYFJ為一家專業(yè)生產(chǎn)各類吸塵器及其附件的公司.現(xiàn)在客戶需求逐漸由少品種大批量轉(zhuǎn)變?yōu)槎嗥贩N小批量的形式，客戶的訂單量大小及品種差異很大，為在激烈的市場競爭中生存，所以制定一個(gè)合理的可重構(gòu)裝配線調(diào)度方案對于企業(yè)來說為意義重大.本案例采用YYFJ產(chǎn)值和產(chǎn)量最高的第四車間PTVL1的可重構(gòu)裝配線，2013年7月份生產(chǎn)計(jì)劃進(jìn)行仿真實(shí)驗(yàn).

采用Matlab編寫了算法程序，該生PT產(chǎn)線生產(chǎn)6種類型的產(chǎn)品，其產(chǎn)品型號和月生產(chǎn)計(jì)劃如表2所示，以下表中產(chǎn)品數(shù)量和產(chǎn)品所需要的零件數(shù)都基于MPS取值.

表2 PTVL1生產(chǎn)線2013年7月份生產(chǎn)計(jì)劃

基礎(chǔ)參數(shù)值:vc=1,tc=15,m=10,n=50,c1=c2=2.0，w=9，Tmax=200；計(jì)算的基礎(chǔ)數(shù)據(jù)見表3—5.

表3 各產(chǎn)品所需求的子裝配零件數(shù)量

采用提出的進(jìn)蛙跳算法算法對該裝配線進(jìn)行調(diào)度優(yōu)化，所求出的Pareto非劣解集平均值與現(xiàn)有調(diào)度方案產(chǎn)生的目標(biāo)值比較如表6所示，Pareto非劣解集分布仿真圖如圖2所示.

表4 各工作站的裝配時(shí)間和長度

表5 不同種類產(chǎn)品轉(zhuǎn)換時(shí)的調(diào)整費(fèi)用

表6較為清晰的表明了改進(jìn)的蛙跳算法而得到的目標(biāo)值較明顯優(yōu)于原有方案，這也證明了算法的有效性和適應(yīng)性.由圖2可看出：pareto非劣解集分布的聚集性，從而也可得出算法有效性的結(jié)論.

表6 Pareto非劣解集平均值與現(xiàn)有調(diào)度方案產(chǎn)生的目標(biāo)值比較

圖2 Pareto非劣解集分布仿真圖

5 結(jié) 論

研究了可重構(gòu)裝配線調(diào)度存在的主要問題[7]，從而提煉出了影響其調(diào)度的三個(gè)主要因素，即最小重構(gòu)裝配線成本、最小零部件需求變化率、最小延誤工作量，根據(jù)這三個(gè)目標(biāo)，建立了調(diào)度模型，而且提出了基于改進(jìn)蛙跳算法的可重構(gòu)裝配線調(diào)度優(yōu)化算法.該算法綜合運(yùn)用了SPV規(guī)則編碼、啟發(fā)式算法和隨機(jī)方式初始化、自適應(yīng)小生境的精英解集維護(hù)、結(jié)合粒子群算法中的粒子局部更新策略保證蛙群的多樣性，很好避免了算法過早限于布局極值，且對蛙群整體尋優(yōu)能力進(jìn)行了改善，并以某吸塵器企業(yè)的一條可重構(gòu)裝配線為實(shí)際案例，運(yùn)用提出的算法模型進(jìn)行了仿真實(shí)驗(yàn)，與現(xiàn)有調(diào)度方案進(jìn)行了對比.仿真結(jié)果表明：該算法求出的Pareto非劣解平均值優(yōu)于現(xiàn)有調(diào)度方案較多，從而驗(yàn)證了該算法的有效性和可行性.

參考文獻(xiàn)：

[1] KOREN, HEISEL U, JOVANE F, et al. Reconfigurable manufacturing systems[J]. Annals of the CIRP,1999,48(2):527-540.

[2] MEHRABI M G, ULSOY A G, KOREN Y. Reconfigurable manufacturing systems: key to future maufacturing[J]. Journal of Intelligent Manufacturing,2000,1(1):113-130.

[3] DING F Y, TOLANI. Production planning to support mixed model assembly[J]. Computer&Industrial Engeering,2003,45(1):375-392.

[4] KUBIAK W. Minimzing variation of production rates in just in time systems: a survey[J]. European Joumal of Operational Research,1993,66(3):259-271.

[5] 黃雪梅,肖田元.智能可重構(gòu)汽車變速器裝配生產(chǎn)線制造系統(tǒng)研究[J].機(jī)械科學(xué)與技術(shù),2009,25(4):403-406.

[6] YU Jian-feng, YIN Yue-hong, Shen Xin-jun, et al. Modeling strategies for reconfigurable assembly system, Assembly Automation[J]. Assembly Automation,2003,13(3):266-272.

[7] 苑明海,白穎,李東波.可重構(gòu)裝配線多目標(biāo)優(yōu)化調(diào)度研究[J].中國機(jī)械工程,2008,19(16):1898-1903.

[8] 李富明;劉江峰.一種基于工作站Petri網(wǎng)模型的混流裝配線重構(gòu)方法[J].廣西大學(xué)學(xué)報(bào):自然科學(xué)版,2012,37(6):1204-1210.

[9] 朱劍英.現(xiàn)代制造系統(tǒng)模式、建模方法及關(guān)鍵技術(shù)的新發(fā)展[J].機(jī)械工程學(xué)報(bào),2000,36(8):1-5.

[10] 苑明海.可重構(gòu)裝配線建模、平衡及調(diào)度研究[D].南京：南京理工大學(xué)，2008.

[11] 陳勇,阮幸聰,王亞良.基于元胞機(jī)的大型機(jī)械構(gòu)件生產(chǎn)車間柔性調(diào)度求解[J].浙江工業(yè)大學(xué)學(xué)報(bào)，2011,39(4)：433-439.

[12] 鄭章元.蛙跳算法及其在置換流水車間調(diào)度中的應(yīng)用研究[D].武漢：華中科技大學(xué)，2011.

[13] 賀毅朝，曲文龍，許冀偉．一種改進(jìn)的混合蛙跳算法及其收斂性分析[J]．計(jì)算機(jī)工程與應(yīng)用，2011,47(22):37-40.

[14] CHUNG G, LANSEY K. Application of the shuffled frog leaping algorithm for the optimization of a general large-scale water supply system[J]. Water Resources Management,2009,23(4):797-823.

[15] 趙曉波,張鳴,羅振壁,等.可重組FMS中緩沖區(qū)容量的優(yōu)化配置問題[J].系統(tǒng)工程學(xué)報(bào),2000,15(2):158-162.

[16] 胥小波,鄭康鋒,李丹,等.新的混沌粒子群優(yōu)化算法[J].通信學(xué)報(bào),2012,33(1):24-37.