劉巍巍，楊 浩，劉慧芳

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

0 引言

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

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

1 模型設計

1.1 模型描述

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

R：產品類型集合R={1,…,r,…R} ；

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

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

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

lj：每個工作站的時間窗j∈J；

bj：分配給每個工作站的處理器數量j∈J；

p：產品在序列中的位置；

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

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

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

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

1.2 模型建立

本文設計的的問題優(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)產生工作過載W和無效時間U；式(3)限制了所有工作站j上的所有周期時刻t對應的部分工作過載。等式(4)定義了在每個工作站和循環(huán)中關于序列β(T)的無效時間。方程(5)確定最小起始時刻sj,t，而式(6)、式(7)和式(8)確定J×D個作業(yè)的最小完成時刻ej,t，不等式(9)是“保持生產混合”約束，強制在整個周期內保持生產混合。

2 算法設計

2.1 初始解序列構造

初始解序列的具體的構造步驟如下：

(1)初始化

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

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

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

t←t+1

Cl(t)={r∈R:nr

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

(3)候選產品類型評定

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

(4)候選產品排序

如果：

那么：

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

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

(7)記錄Λi

(8)完成測試。如t

2.2 改進解決方案的局部搜索

本文設計了如下4種鄰域結構，其中p位置與p′位置的產品類型相同。

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

圖1 向前交換示意圖

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

圖2 向后交換示意圖

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

圖3 向前插入示意圖

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

圖4 向后插入示意圖

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

LP階段的目標函數為：

(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個工作站的t時刻已完成的工作。

3 實例驗證

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

工作站數量：J=16

產品類型數量：|R|=8(r=1,…,8)

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

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

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

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

日需求量：T=Dε=240×訂單ε內產品的單位數量(?ε=1,...,18)

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

3.1 選擇閾值參數Λ

通過實驗確定閾值參數Λ的一組取值為A={0.00,0.15,0.25,0.35,0.45,0.55,0.65,0.75,0.85,0.95,1.00}，且每個Λi的選擇概率相等。在算法運行結束后，統計每個Λ取值下解的平均值，統計結果如圖5所示。

圖5 閾值參數Λ取不同值時的平均解

由圖5可知，按照平均解升序排列，參數Λ的取值排序為0.25，0.75，0.45，0.35，0.65，0.85，0.95，0.55，1.00，0.00。最后，確定Λ的取值范圍列表A，A由能獲得較好平均解的Λ值組成，其中a∈[1,11]。例如，當a=3時，A={0.25，0.75，0.45}。a∈[1,11]時統計結果如圖6所示。

圖6 閾值參數Λ取不同值時的平均解

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

3.2 SGRASP-LP與GRASP對比

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

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

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

3.3 SGRASP-LP與MILP對比

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

表2給出了兩種算法計算出的目標函數值Z(ε)，以及18個需求計劃下的優(yōu)勝算法和兩種算法的優(yōu)勢對比結果SGvM，SGvM計算公式如下：

表2 優(yōu)勢對比結果

從表2的分析可以看出：

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

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

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

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

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

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

由表3可得：

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

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

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

4 結論

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

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