趙文燕, 張世哲, 師柳柳

(河北工業(yè)大學(xué) 經(jīng)濟管理學(xué)院,天津 300401)

0 引言

多人工作站裝配線平衡問題是客車、工程機械等大型產(chǎn)品生產(chǎn)線設(shè)計中的主要問題。目前多人工作站裝配線平衡問題的研究多針對單一產(chǎn)品，通過建立單目標(biāo)或多目標(biāo)數(shù)學(xué)模型，利用啟發(fā)式算法或智能算法求解，目標(biāo)多為裝配線總?cè)藬?shù)最小、工人負荷量均衡、各工作站裝配不同產(chǎn)品所需時間的差異最小等。Dimitriadis首先研究了多人工作站裝配線平衡問題，指出多人工作站裝配線能夠有效縮短裝配線長度[1]。Chen等針對多人工作站資源受限裝配線平衡問題，建立了以最小化工作站和工人數(shù)量為目標(biāo)的優(yōu)化模型，并采用混合遺傳算法求解[2]。Fattahi等則在節(jié)拍已知條件下，以最小化人員數(shù)量為第一目標(biāo)，最小化工作站數(shù)量為第二目標(biāo)，設(shè)計了一種蟻群算法求解該問題[3]。Roshani和Giglio在工作站數(shù)量已知情況下，對以節(jié)拍和裝配線總?cè)藬?shù)最小為目標(biāo)的多人工作站單一產(chǎn)品裝配線平衡問題利用模擬退火算法進行了求解[4]。童科娜等建立了以裝配線節(jié)拍、工人數(shù)量以及工人負荷標(biāo)準(zhǔn)差最小為目標(biāo)的多人工作站單一產(chǎn)品裝配線平衡問題的數(shù)學(xué)模型，并設(shè)計了一種結(jié)構(gòu)式譯碼遺傳算法對該問題求解[5]。張梅等考慮工序復(fù)雜程度與工人能力差異情況，建立了以最小化工作站數(shù)量和工人數(shù)量為目標(biāo)的優(yōu)化模型，提出了一種改進的離散水波優(yōu)化算法，并將其應(yīng)用于動車裝配線平衡優(yōu)化中[6]。Zhang等以最小化工作站和操作員的總數(shù)為目標(biāo)，采用模因蟻群算法求解了優(yōu)化模型[7]。Yilmaz 建立了在給定周期內(nèi)使工人數(shù)最小化的多人工作站裝配線優(yōu)化模型，采用禁忌搜索算法進行了求解[8]。

在多人工作站單一產(chǎn)品裝配線平衡問題的基礎(chǔ)上，學(xué)者們進一步研究了多人工作站混合裝配線平衡問題。Roshani和Nezami[9]以工作站數(shù)量和裝配線總?cè)藬?shù)最小為目標(biāo)，利用模擬退火算法求解多人工作站混合裝配線平衡問題。Kazemi和Sedighi[10]等則對以最小化生產(chǎn)成本為目標(biāo)的多人工作站混合裝配線平衡問題，利用遺傳算法和粒子群算法進行了求解。國內(nèi)學(xué)者針對多人工作站混合裝配線平衡問題的研究還相對缺乏。

綜上可知，現(xiàn)有多人工作站裝配線的研究多以單一產(chǎn)品裝配線為對象，混合裝配線的研究要么以工作站數(shù)量為優(yōu)化目標(biāo)，要么對工作站數(shù)量不加限制。然而，多人工作站混合裝配線設(shè)計或改造過程中，由于場地、成本等因素的影響，裝配線工作站數(shù)量可能受限或不易變更。針對這一特點，本文研究具有工作站數(shù)量約束的多人工作站混合裝配線平衡問題，在節(jié)拍已知情況下，以裝配線人數(shù)最小、工人負荷量均衡、各工作站裝配不同產(chǎn)品所需時間的差異最小為目標(biāo)，建立相應(yīng)的數(shù)學(xué)模型，并設(shè)計一種結(jié)合差分進化的多目標(biāo)混合遺傳算法對該問題求解。

1 模型建立

1.1 問題描述

設(shè)裝配線生產(chǎn)NP種類型的產(chǎn)品，裝配線共有NW個工作站，每個工作站最多容納Mmax名工人，給定NP種產(chǎn)品的生產(chǎn)比例、作業(yè)要素標(biāo)準(zhǔn)時間、裝配線節(jié)拍，在滿足作業(yè)要素優(yōu)先順序的情況下，為每個工作站合理分配工人數(shù)量，并合理安排每個工人所需完成的作業(yè)要素及順序，使裝配線在所有工作站均被有效利用的條件下，達到以下三個目標(biāo)：裝配線總?cè)藬?shù)最小、裝配線工人負荷量波動最小和各工作站裝配各產(chǎn)品的裝配時間波動最小。針對該問題做出如下假設(shè)：

(1)不同工人完成相同作業(yè)要素的時間相等。

(2)同樣的裝配作業(yè)需要分配至相同的工作站和工人。

(3)不考慮產(chǎn)品在工作站之間的搬運時間。

(4)不考慮產(chǎn)品切換時間。

(5)各工作站最大人數(shù)限制已知。

(6)工作站數(shù)量已知且需充分利用。

(7)每個作業(yè)要素只能由一個工人獨立完成。

1.2 數(shù)學(xué)模型

本文模型中用到的符號定義如表1所示。

表1 符號定義

在多人工作站混合裝配線平衡問題中，由于各品種在各個工序的工作時間不同，且工人在工作過程中可能存在等待現(xiàn)象，工人的完工時間并不能很好地描述其負荷量，因此將每個工人完成每種產(chǎn)品的有效工作時間的加權(quán)平均時間作為工人負荷量，因此，工作站j的工人k的負荷量為:

WLjk=∑i∈I∑l∈LqlXijktil

(1)

裝配線總?cè)藬?shù)最小、工人負荷均衡、產(chǎn)品在各工作站的加工時間與節(jié)拍差值最小的具有工作站約束的多人工作站混合裝配線平衡問題的數(shù)學(xué)模型為:

Objective min(∑j∈J∑k∈KWjk)

(2)

(3)

(4)

s.t.∑j∈J∑k∈KXijk=1,?i∈I

(5)

(6)

∑k∈KWjk≥1,?j∈J

(7)

(8)

?i∈I,h∈P(i),?j∈J

(9)

Shl-Sil+B(1-Xhjk)+B(1-Xijk)+B(1-Yih)≥til

?i∈I,h∈{r|r∈I-(Pall(i)∪Qall(i))andi

?j∈J,?k∈K,?l∈L

(10)

Sil-Shl+B(1-Xhjk)+B(1-Xijk)+BYih≥thl

?i∈I,h∈{r|r∈I-(Pall(i)∪Qall(i))andi

?j∈J,?k∈K,?l∈L

(11)

(12)

(13)

Wj(k+1)≤Wjk,?j∈J,?k∈K,k

(14)

Sil+til≤Cil,?i∈I,?l∈L

(15)

(16)

(17)

0≤Sil,?i∈I

(18)

Xijk∈{0,1},?i∈I,?j∈J,?k∈K

(19)

Wjk∈{0,1},?j∈J,?k∈K

(20)

Yih∈{0,1},?i∈I,h∈{r|r∈I-(Pall(i)∪Qall(i))andi

(21)

模型中，(2)～(4)分別表示三個目標(biāo)函數(shù)：裝配線總?cè)藬?shù)最小、工人負荷量標(biāo)準(zhǔn)差最小和各工作站各產(chǎn)品裝配時間對于節(jié)拍的標(biāo)準(zhǔn)差之和最?。?5)表示每個作業(yè)要素只能被分配一次；(6)表示所有作業(yè)要素必須被分配；(7)表示每個工作站至少分配一個工人；(8)表示作業(yè)要素分配必須滿足優(yōu)先關(guān)系；(9)表示產(chǎn)品l的作業(yè)要素h為i的先行作業(yè)要素，當(dāng)h與i分配在同一工作站時，i必須在h完成之后才能開始；(10)表示產(chǎn)品l的作業(yè)要素h與i不具備先行或者后行關(guān)系，作業(yè)要素i與h分配給同一工作站同一操作者，且作業(yè)要素i的操作順序先于h，h必須在i完成之后才可開始；(11)表示產(chǎn)品l的作業(yè)要素h與i不具備先行或者后行關(guān)系，作業(yè)要素h與i分配在同一工作站同一操作者，且作業(yè)要素i完成順序在h之后，i必須在h完成之后才可開始；(12)表示每個工人必須分配至少一個作業(yè)要素；(13)表示作業(yè)要素i分配給工作站j的工人k，則Wjk必須等于1；(14)表示各工作站工人按增序進行索引；(15)表示作業(yè)要素必須完成；(16)表示各作業(yè)要素的完成時間必須小于工作站總操作時間；(17)表示工作站平均裝配時間滿足節(jié)拍約束；(18)表示作業(yè)要素開始時間大于0；(19)～(21)分別表示變量X、W、Y的取值范圍。

2 混合遺傳算法設(shè)計

裝配線平衡問題是一類典型的NP-hard問題，普通的精確算法難以進行求解。本文設(shè)計了一種多目標(biāo)混合遺傳算法用于求解本文多人工作站混合裝配線平衡問題。

2.1 編碼與解碼

將染色體編碼分為兩部分，前者對應(yīng)作業(yè)要素的分配順序，后者對應(yīng)每個工作站分配的工人數(shù)量，染色體采用隨機鍵編碼的方式，編碼長度分別為作業(yè)要素數(shù)量和工作站數(shù)量，為每個作業(yè)要素分配一個0到1之間的隨機數(shù)作，為每個工作站分配一個0到最大工人數(shù)Mmax之間的隨機數(shù)。

在編碼得到染色體后，進行解碼得到裝配線配置方案。設(shè)工作站j的工人集合為Kj；工作站j中工人k完成作業(yè)要素i后，工作站的平均裝配時間為tijk；裝配線節(jié)拍為CT。解碼步驟如下：

Step1令j=1。

Step2對工作站j人員分配部分編碼向上取整，得到工作站j的人員分配。若取整后工作站人數(shù)大于Mmax，則將工作站人數(shù)設(shè)置為Mmax；若取整后工作站人數(shù)小于1，則將工作站人數(shù)設(shè)置為1。

Step3找出無緊前作業(yè)要素或緊前作業(yè)要素已分配的作業(yè)要素作為可選作業(yè)要素集A，從可選作業(yè)要素集中選出權(quán)重最大的作業(yè)要素作為待分配作業(yè)要素，若權(quán)重最大的作業(yè)要素有多個，則隨機選擇一個，設(shè)該作業(yè)要素為i。

Step4計算工作站j內(nèi)工人k完成作業(yè)要素i后工作站j的平均完工時間tijk，?k∈K。

Step5若min(tijk)≤CT(?k∈K)則將作業(yè)要素i分配給min(tijk)所對應(yīng)的工人，若min(tijk)所對應(yīng)的工人有多個，則將作業(yè)要素i隨機分配給其中一個工人, 并轉(zhuǎn)Step 7。

Step6若min(tijk)>CT(?k∈K)，則工作站j分配完畢。若所有工作站分配完畢，則退出，否則，令j=j+1，轉(zhuǎn)Step2對工作站j=j+1進行分配。

Step7判斷作業(yè)要素是否分配完畢，若分配完畢，則結(jié)束，否則，轉(zhuǎn)Step3繼續(xù)分配。

2.2 排序以及擁擠度計算

經(jīng)解碼后的種群(染色體個數(shù)為N)，其染色體可能會兩種不符合約束的情況：(1)作業(yè)要素?zé)o法全部分配，(2)工人或工作站未利用。對情況1所對的應(yīng)染色體，采用罰函數(shù)法進行處理；情況2所對應(yīng)染色體將產(chǎn)生較大的目標(biāo)函數(shù)值。這兩部分個體將會在之后的更新中被淘汰。

設(shè)種群中的染色體x的第i個目標(biāo)函數(shù)值為fi(x)(i=1,2,…,p)，fi(x)∈f(x)。若兩個染色體x1和x2的目標(biāo)函數(shù)值均有fi(x1)≤fi(x2)，其中只要任意一個fi(x1)

按照f(x)對種群排序，最優(yōu)的染色體排到第1層，次優(yōu)的排到第2層，依次進行。若同層有多條染色體，則需計算各染色體的擁擠度。根據(jù)每個目標(biāo)函數(shù)對種群中的所有個體按升序進行排序。將同層兩個邊界染色體的擁擠度設(shè)為無窮大，第i個個體的擁擠度則設(shè)為第i+1和第i-1個體的所有目標(biāo)函數(shù)值之差的和。在之前分層排序的基礎(chǔ)上，對同層內(nèi)染色體按照擁擠度由高到低排序，完成種群內(nèi)染色體的排序。

2.3 選擇

采用聯(lián)賽選擇算法，從種群中隨機選擇m條染色體形成交配池，要求m≤N/2。本文采用的基本方式是隨機從種群中選擇兩條染色體，將排序?qū)哟蔚偷娜旧w放入交配池，當(dāng)兩條染色體處于同一層時，選擇擁擠度較大的染色體放入交配池。重復(fù)進行，直到形成m條染色體的交配池。

2.4 交叉和變異

在進行交叉操作時，按交叉概率分別對作業(yè)要素排序和工作站人員進行兩點交叉。在完成交叉操作后，按照變異概率，任選一個作業(yè)要素重新為其分配一個0到1之間的權(quán)重，隨機選擇一個工作站重新為其分配一個0到Mmax之間的隨機數(shù)。經(jīng)交叉變異形成m條子代染色體后，與原種群中排序最后的m個染色體共同組成染色體集Y，對該集合按照2.2節(jié)的規(guī)則排序，取最優(yōu)的m條染色體遺傳至下一代。

2.5 差分進化

由于遺傳算法局部搜索能力較弱，為解決這一問題，本文將差分進化操作嵌入遺傳算法，以增強遺傳算法的局部搜索能力。算法對種群中最優(yōu)的k條染色體進行差分進化操作，其中k≤N/2，其步驟為：

Step1從排序的種群中，選擇前k條染色體進行差分進化。

Step2設(shè)k條染色體組成染色體集為X，當(dāng)前進行差分進化操作的染色體為Xl，隨機從染色體集X中選擇3條染色體：Xa、Xb、Xc，其中l(wèi)≠a≠b≠c，借助縮放因子F得到變異染色體Hl，其公式為:

Hl=Xa+F×(Xb-Xc)

(22)

Step3對染色體Xl進行交叉操作生成新染色體Ul。設(shè)染色體長度為D，則Xl={Xl,1,Xl,2,…,Xl,D}，Hl={Hl,1,Hl,2,…,Hl,D}，則新染色體Ul={Ul,1,Ul,2,…,Ul,D}按如下規(guī)則確定:

(23)

式中，CR為交叉概率，drand為染色體中隨機選擇的一個基因。所有Ul共同構(gòu)成染色體集合U。

Step4染色體集U與染色體集X合并形成染色體集Z，對Z排序后選擇最優(yōu)的k條染色體替換染色體集X遺傳至下一代。

本文設(shè)計的結(jié)合差分進化的多目標(biāo)混合遺傳算法流程圖如圖1所示。本算法既借助遺傳算法保持樣本多樣性，又借助差分進化操作加快優(yōu)化速度，進而快速獲得全局最優(yōu)。

圖1 算法流程圖

3 數(shù)值計算

3.1 參數(shù)效驗

將本文算法與DEMO[11]、NSGAII[12]和Roshani和Nezami在文獻[9]中提出的算法進行對比。用MATLAB編寫算法程序，在配置為Intel Core i5-7300HQ CPU、8.00GB RAM的PC上運算。

選用10個裝配線平衡案例進行實驗，其中作業(yè)要素數(shù)7～10的小規(guī)模問題案例4個，作業(yè)要素數(shù)21～58的中等規(guī)模問題案例4個，作業(yè)要素數(shù)70以上的大規(guī)模問題案例2個。作業(yè)要素優(yōu)先關(guān)系可以從www.assembly-line-balancing.de下載。由于這些案例的原問題均為單一品種裝配線平衡問題，因此，對案例稍加更改。根據(jù)文獻[9]，保持這些案例的作業(yè)要素優(yōu)先順序不變，將作業(yè)要素時間設(shè)置為0到原案例中最大作業(yè)要素時間之間的隨機值，工作站最大工人數(shù)設(shè)置為2，產(chǎn)品類型數(shù)量設(shè)置為2，各產(chǎn)品比例均設(shè)置為0.5。各算例相關(guān)信息如表2所示。

表2 案例相關(guān)信息

表3中LBw表示裝配線理論最小人數(shù)，其計算公式為:

(24)

式中，「 ?表示向上取整。

在進行比較之前，以案例9為例，以IGD[13]反世代距離為指標(biāo)對各算法進行參數(shù)效驗，各算法參數(shù)組合與最優(yōu)參數(shù)如表3所示，本文遺傳算法信噪比主效應(yīng)圖如圖2所示。

表3 算法參數(shù)組合與最優(yōu)參數(shù)

圖2 信噪比主效應(yīng)圖

3.2 方法對比分析

在本文算法與DEMO、NSGAII進行對比時，采用世代距離GD[14]、空間評價指標(biāo)SM[15]、反世代距離IGD分別作為算法收斂性、均勻性、綜合性評價指標(biāo)，其計算公式如式(25)(26)(27)所示。

(25)

式中，n為算法所得到解集中解的數(shù)量，di為算法所得到解中個體與參考集中最近解之間的歐幾里得距離。

(26)

(27)

式中，P為參考解集，Q為算法求得的解集，d(v,Q)為解v與Q中最近的解的歐氏距離。

將三種算法所求得全部解中的非劣解集作為GD與IGD中的參考集，每種算法運行3次取最終得到的非劣解進行計算。由于案例1～4三種算法所得到結(jié)果一致，因此僅展示案例5～10的計算結(jié)果，如表4所示。由表4中信息可知，本文遺傳算法的GD以及IGD明顯優(yōu)于DEMO以及NSGAII，這說明本文算法的收斂性以及綜合性能明顯優(yōu)于另外兩種算法。在解集均勻性方面，本文算法分別有9個案例中的SM小于DEMO和NSGAII，因此，本文算法在均勻性方面也優(yōu)于DEMO和NSGAII。

表4 計算結(jié)果

將本文算法與文獻[9]算法進行比較，兩種算法每個案例運行3次，取最優(yōu)結(jié)果和平均CPU時間。本文算法中各工作站數(shù)量均設(shè)置為文獻[9]算法計算后所得工作站數(shù)量，在本文算法得到的非劣解中，按照工人數(shù)最少、工人負荷標(biāo)準(zhǔn)差最低和各工作站產(chǎn)品裝配時間標(biāo)準(zhǔn)差之和最小的順序選擇一個方案對比，得到的結(jié)果如表5所示。其中，Ns表示工作站數(shù)量，Nw表示工人人數(shù)，DL表示工人負荷量標(biāo)準(zhǔn)差，DT表示各產(chǎn)品各工作站裝配時間與節(jié)拍標(biāo)準(zhǔn)差之和，CPU表示CPU時間。

由表5可知，除Jaeschke和Jackson兩個案例外，其他案例中本文算法得到的工人數(shù)量均小于文獻[9]算法，在工人數(shù)量相同的情況下，得到工人負荷標(biāo)準(zhǔn)差也優(yōu)于文獻[9]算法。在運行速度上，兩種算法在小規(guī)模問題上相差不大，隨著問題規(guī)模的擴大，本文算法明顯優(yōu)于文獻[9]算法。

表5 測試結(jié)果對比

3.3 實例計算

某挖掘機上車架混流裝配線共226個作業(yè)元素，A、B和C三種產(chǎn)品，產(chǎn)品比例為3:5:2，裝配線共12個工作站，每個工作站最大人數(shù)為5，原裝配線節(jié)拍為88min，裝配線總?cè)藬?shù)為18，工人負荷量標(biāo)準(zhǔn)差約為14.43。為滿足不斷增加的客戶需求，新的裝配線節(jié)拍設(shè)置為52min。經(jīng)本文算法優(yōu)化，在滿足節(jié)拍約束，保持現(xiàn)有工作站數(shù)量的情況下，裝配線總?cè)藬?shù)由18人減少至16人，工人負荷量標(biāo)準(zhǔn)差由14.43減少至5.67左右。限于篇幅，此處僅給出挖掘機部分線路裝配線平衡過程和結(jié)果。

挖掘機線路裝配過程共包含36個作業(yè)要素，作業(yè)要素綜合優(yōu)先順序如圖3所示，作業(yè)要素標(biāo)準(zhǔn)時間如表6所示。設(shè)定2個工作站，在節(jié)拍52min和各工作站最大工人數(shù)5的限制下，經(jīng)本文算法優(yōu)化得多個優(yōu)化方案，其中一個優(yōu)化方案如表7所示。兩個工作站共需3個工人，其中工作站1工人數(shù)為2，工作站2工人數(shù)為1，裝配線工人負荷量標(biāo)準(zhǔn)差為4.49。

圖3 作業(yè)要素優(yōu)先順序

表6 作業(yè)要素標(biāo)準(zhǔn)時間

表7 計算結(jié)果

4 結(jié)論

針對裝配線設(shè)計或改造過程中，節(jié)拍已知條件下，工作站數(shù)量存在約束的多目標(biāo)多人工作站混合裝配線平衡問題進行研究，建立了數(shù)學(xué)模型，并設(shè)計了一種結(jié)合差分進化算法的多目標(biāo)遺傳算法進行求解。實驗結(jié)果表明，本文算法的計算結(jié)果在收斂性、綜合性能方面明顯優(yōu)于DEMO、NSGAII，在均勻性上略優(yōu)于DEMO、NSGAII，另外，本文算法所得到的解在裝配線人數(shù)最小以及工人負荷標(biāo)準(zhǔn)差最低方面明顯低于Roshani和Nezami在文獻[9]中提出的算法，這也為企業(yè)更好解決類似裝配線問題提供了理論基礎(chǔ)以及相關(guān)方法。但是，本文未考慮裝配線調(diào)整過程中將會出現(xiàn)的各項成本，這也是未來的研究中需要解決的問題之一。