基于SGRASP-LP算法的混流裝配線排序問題*

劉巍巍，楊 浩，劉慧芳

(沈陽工業(yè)大學(xué) 機(jī)械工程學(xué)院，沈陽 110870)

0 引言

在實(shí)際生產(chǎn)過程中，只有對(duì)混流裝配線[1-2]上的產(chǎn)品進(jìn)行合理排序，才能有效地提高裝配線的生產(chǎn)效率、物流效率、縮短生產(chǎn)周期[3-5]。混流裝配線排序問題屬于典型的NP難題，目前關(guān)于該問題的研究多集中于模型構(gòu)建和算法研究?jī)蓚€(gè)方面。文獻(xiàn)[6-8]建立了考慮裝配線平衡相關(guān)因素的混流裝配線排序問題模型，該模型比較符合生產(chǎn)實(shí)際，但沒有考慮工作站上作業(yè)人員自主中斷作業(yè)對(duì)裝配線排序方案的影響；文獻(xiàn)[9-11]都采用遺傳算法求解了相應(yīng)的模型，得到了較優(yōu)的投產(chǎn)序列，但無法避免此類算法求解時(shí)容易陷入局部最優(yōu)的局限性；文獻(xiàn)[12]設(shè)計(jì)一種改進(jìn)貓群算法求解多目標(biāo)混流裝配線排序問題，雖然貓群算法局部和全局搜索的能力較好，但將其應(yīng)用在實(shí)際的混流裝配線排序問題時(shí)需要提前離散化，求解過程相對(duì)復(fù)雜。

本文設(shè)計(jì)的SGRASP-LP算法在建模時(shí)引入的 “保持生產(chǎn)混合” 與“作業(yè)自主中斷”兩個(gè)約束條件，更符合實(shí)際生產(chǎn)要求；在求解時(shí)為基本的GRASP(Greedy Randomized Adaptive Search Procedures)算法增加了閾值參數(shù)選擇機(jī)制，并將其與線性規(guī)劃(Linear programming，LP)方法相結(jié)合，提升了算法的求解效率與精度，改善了算法的全局尋優(yōu)性能。

1 模型設(shè)計(jì)

1.1 模型描述

混流裝配線排序問題是指對(duì)于采用最小生產(chǎn)循環(huán)(Minimal Production Set，MPS)模式生產(chǎn)的混流裝配線，確定一個(gè)MPS中產(chǎn)品的投產(chǎn)順序的問題。假設(shè)裝配線生產(chǎn)節(jié)拍固定，不同型號(hào)的產(chǎn)品在各個(gè)工作站上的加工時(shí)間不同。模型的變量符號(hào)說明如下：

R：產(chǎn)品類型集合R={1,…,r,…R} ；

J：工作站集合J={1,…,j,…J} ；

T：制造周期T={1,…,t,…T} ；

c：每個(gè)工作站的節(jié)拍時(shí)間；

lj：每個(gè)工作站的時(shí)間窗j∈J；

bj：分配給每個(gè)工作站的處理器數(shù)量j∈J；

p：產(chǎn)品在序列中的位置；

ρr,j：作業(yè)的處理時(shí)間(r∈R，j∈J)(正常的活動(dòng)下的測(cè)量值)；

D：一個(gè)最小生產(chǎn)循環(huán)單元中，所有類型產(chǎn)品的總需求數(shù)量，且T≡D=Σ?rdr；

θ：產(chǎn)品類型比例。θ=(θ1，…，θr,…θR)，其中θr是需求計(jì)劃中r(r∈R)類產(chǎn)品所占的比例，θ=d/D；

Xr,t：表示包含在序列β(t)=(β1,…βt)?β(T) (?t=1,…,T)中r(r∈R)類產(chǎn)品的單位數(shù)量。

1.2 模型建立

本文設(shè)計(jì)的的問題優(yōu)化模型如下：

(1)

(2)

0≤wj,t(βt)≤max(0,sj,t(βt)+ρβt,j-ej,t(βt))

(3)

uj,t(βt)=sj,t(βt)-ej,t-1(βt-1)

(4)

sj,t(βt)=max(ej,t-1(βt-1),ej-1,t(βt),(j+t-2)c)

(5)

ej,t(βt)=sj,t(βt)+ρβt,j-wj,t(βt)

(6)

ej,t(βt)≤(j+t-2)c+lj

(7)

ej,0(β0)=e0,t(βt)=0

(8)

?θrt」≤Xr,t≤|θrt|,Xr,T=dr

?j∈J?t∈T?r∈R?t∈T

(9)

式(1)和式(2)分別確定由序列β(T)產(chǎn)生工作過載W和無效時(shí)間U；式(3)限制了所有工作站j上的所有周期時(shí)刻t對(duì)應(yīng)的部分工作過載。等式(4)定義了在每個(gè)工作站和循環(huán)中關(guān)于序列β(T)的無效時(shí)間。方程(5)確定最小起始時(shí)刻sj,t，而式(6)、式(7)和式(8)確定J×D個(gè)作業(yè)的最小完成時(shí)刻ej,t，不等式(9)是“保持生產(chǎn)混合”約束，強(qiáng)制在整個(gè)周期內(nèi)保持生產(chǎn)混合。

2 算法設(shè)計(jì)

2.1 初始解序列構(gòu)造

初始解序列的具體的構(gòu)造步驟如下：

(1)初始化

輸入：L,R，J,D,c, (dr,ρr,j,wj)， ?r∈R,?j∈J；設(shè)定初始值：T=D,t=0,β(t)={?}，

(nr=0,θr=dr/D)?r∈R。

(2)候選產(chǎn)品類型集合創(chuàng)建

t←t+1

Cl(t)={r∈R:nr

CL(t)={?}?CL(t)={r∈R:nr

(3)候選產(chǎn)品類型評(píng)定

?r∈CL(t)，Xr,t-1

(4)候選產(chǎn)品排序

如果：

那么：

(5)從限制列表里選擇產(chǎn)品類型

(6)更新Rr*Rr*←Rr*+1；β(t)≡β(t-1)∪{r*}

(7)記錄Λi

(8)完成測(cè)試。如t

2.2 改進(jìn)解決方案的局部搜索

本文設(shè)計(jì)了如下4種鄰域結(jié)構(gòu)，其中p位置與p′位置的產(chǎn)品類型相同。

(1)向前交換。如圖1中產(chǎn)品類型4與產(chǎn)品類型9的交換。

圖1 向前交換示意圖

(2)向后交換。如圖2中產(chǎn)品類型3與產(chǎn)品類型5的交換。

圖2 向后交換示意圖

(3)向后插入。如圖3中，產(chǎn)品類型6從p+2位置插入到p′-2位置。

圖3 向前插入示意圖

(4)向后插入。如圖4中，產(chǎn)品類型9從p-1位置插入到p′+3位置。

圖4 向后插入示意圖

2.3 整體工作過載及無效時(shí)間優(yōu)化

LP階段的目標(biāo)函數(shù)為：

(10)

約束條件：

(11)

(j+t-2)c≤sj,t

(12)

sj,t-1+vj,t-1≤sj,t

(13)

sj-1,t+vj-1,t≤sj,t

(14)

sj,t+vj,t≤(j+t-2)c+lj

(15)

uj,t≤ej,t-sj,t

(16)

vj,t,wj,t,uj,t≥0

(17)

?j=1,...,J;?t=1,...,T。其中，vj,t代表第j個(gè)工作站的t時(shí)刻已完成的工作。

3 實(shí)例驗(yàn)證

以某汽車企業(yè)底盤裝配線為例驗(yàn)證算法的有效性，相關(guān)數(shù)據(jù)如下：

工作站數(shù)量：J=16

產(chǎn)品類型數(shù)量：|R|=8(r=1,…,8)

節(jié)拍時(shí)間：c=150s，時(shí)間窗：l=170s(?j=1,...,16)

同類處理器數(shù)量：bj=1(?j=1,...,16)

工作站上產(chǎn)品的加工時(shí)間：ρr,j(?∈R,?j∈J)

訂單數(shù)量：|E|=18(ε=1,...,18)所有的訂單有相同的日需求量

日需求量：T=Dε=240×訂單ε內(nèi)產(chǎn)品的單位數(shù)量(?ε=1,...,18)

程序在Lenovo(Intel i5，CPU3.5GHz，內(nèi)存8GB)的PC上運(yùn)行。

3.1 選擇閾值參數(shù)Λ

通過實(shí)驗(yàn)確定閾值參數(shù)Λ的一組取值為A={0.00,0.15,0.25,0.35,0.45,0.55,0.65,0.75,0.85,0.95,1.00}，且每個(gè)Λi的選擇概率相等。在算法運(yùn)行結(jié)束后，統(tǒng)計(jì)每個(gè)Λ取值下解的平均值，統(tǒng)計(jì)結(jié)果如圖5所示。

圖5 閾值參數(shù)Λ取不同值時(shí)的平均解

由圖5可知，按照平均解升序排列，參數(shù)Λ的取值排序?yàn)?.25，0.75，0.45，0.35，0.65，0.85，0.95，0.55，1.00，0.00。最后，確定Λ的取值范圍列表A，A由能獲得較好平均解的Λ值組成，其中a∈[1,11]。例如，當(dāng)a=3時(shí)，A={0.25，0.75，0.45}。a∈[1,11]時(shí)統(tǒng)計(jì)結(jié)果如圖6所示。

圖6 閾值參數(shù)Λ取不同值時(shí)的平均解

由圖6可知，a=3時(shí)SGRASP-LP算法的平均解最優(yōu)。當(dāng)a=6時(shí)算法平均解最差；當(dāng)7≤a≤9時(shí)，平均解逐漸變優(yōu)，但是仍然大于a=3時(shí)的平均解。因此，參數(shù)Λ的取值應(yīng)選取得較好平均解的前3個(gè)值，即A={0.25,0.75,0.45}。

3.2 SGRASP-LP與GRASP對(duì)比

為驗(yàn)證增加閾值參數(shù)選擇機(jī)制后的SGRASP-LP算法優(yōu)勢(shì)，將其與基本的GRASP算法進(jìn)行比較。兩種算法在最優(yōu)解和求解時(shí)間方面的比較結(jié)果詳見表1，TSG和TG分別代表兩種算法的找到最優(yōu)解的求解時(shí)間。

表1 兩種算法的最優(yōu)解和求解的平均時(shí)間

由表1可以看出，與GRASP算法相比，SGRASP-LP算法找到的最優(yōu)解更優(yōu)，所用時(shí)間更短。因此，SGRASP-LP算法能夠利用歷史信息，在迭代過程中更改Λ取值，提升整體求解速度與解的質(zhì)量。

3.3 SGRASP-LP與MILP對(duì)比

兩個(gè)程序均在Lenovo(Intel i5，CPU3.5GHz，內(nèi)存8GB)的PC上使用MATLAB編程。調(diào)用8.0.1版Gurobi求解器對(duì)MILP方法進(jìn)行求解；調(diào)用12.7.1版CPLEX對(duì)SGRASP-LP方法進(jìn)行求解。

表2給出了兩種算法計(jì)算出的目標(biāo)函數(shù)值Z(ε)，以及18個(gè)需求計(jì)劃下的優(yōu)勝算法和兩種算法的優(yōu)勢(shì)對(duì)比結(jié)果SGvM，SGvM計(jì)算公式如下：

表2 優(yōu)勢(shì)對(duì)比結(jié)果

從表2的分析可以看出：

(1)SGRASP-LP算法找到最優(yōu)解的次數(shù)更多、找到的平均最優(yōu)解更優(yōu)，且兩者在計(jì)劃8中都找到最優(yōu)解。

(2)SGRASP-LP與MILP的整體平均優(yōu)勢(shì)對(duì)比結(jié)果約為9%。SGRASP-LP優(yōu)于MILP時(shí)的優(yōu)勢(shì)對(duì)比結(jié)果為15%，MILP優(yōu)于SGRASP-LP時(shí)的優(yōu)勢(shì)對(duì)比結(jié)果為7.5%。

(3)MILP和SGRASP-LP平均分別需要2978.5s和311.6s。

此外，本文將每種類型產(chǎn)品在每個(gè)需求計(jì)劃對(duì)應(yīng)的生產(chǎn)周期下的理想生產(chǎn)量θr,εt和實(shí)際生產(chǎn)量Xr,t,ε之間的方差之和ΔQ作為評(píng)價(jià)指標(biāo)，以比較采用兩種算法產(chǎn)生的序列在生產(chǎn)時(shí)的裝配線穩(wěn)定性。

表3也總結(jié)了每個(gè)計(jì)劃下的裝配線穩(wěn)定性ΔQM(X,ε)和ΔQ SG(X,ε)以及兩者中的優(yōu)勝算法和優(yōu)勢(shì)對(duì)比結(jié)果ΔSGvM。

?ε∈E,?δ∈{SG},?δ′∈{M}

由表3可得：

(1)SGRASP-LP算法在18個(gè)需求計(jì)劃中14次勝出，MILP算法4次勝出，兩者在計(jì)劃1中裝配線穩(wěn)定性一致。

(2)SGRASP-LP與MILP的整體平均優(yōu)勢(shì)對(duì)比結(jié)果約為4%。GRASP-LP優(yōu)于MILP時(shí)的優(yōu)勢(shì)對(duì)比結(jié)果為6%，MILP優(yōu)于SGRASP-LP時(shí)的優(yōu)勢(shì)對(duì)比結(jié)果為4%。

(3)最后，雖然SGRASP-LP和MILP在第8個(gè)需求計(jì)劃中計(jì)算出的目標(biāo)函數(shù)值相等，但是SGRASP-LP產(chǎn)生的序列在生產(chǎn)時(shí)裝配線穩(wěn)定性更高。

4 結(jié)論

本文結(jié)合混流裝配線的生產(chǎn)實(shí)際情況建立了MASP-W&U/PPM/F問題模型，在考慮模型的線性目標(biāo)函數(shù)和標(biāo)準(zhǔn)GRASP算法求解特點(diǎn)的基礎(chǔ)上，設(shè)計(jì)了線性規(guī)劃輔助下的帶有閾值參數(shù)選擇機(jī)制的SGRASP-LP算法。實(shí)例的分析及對(duì)比結(jié)果表明，本文提出的模型和算法更符合企業(yè)的生產(chǎn)實(shí)際，求解過程呈現(xiàn)出較好的可行性與規(guī)律性，而且算法求解速度較快，所求解的質(zhì)量較高，是求解裝配線投產(chǎn)順序排列問題的有效方法。

DOI:10.1007/s00170-014-6153-4.