鄧 超，胡瑞飛，蔣捷峰，殷國富

(四川大學機械工程學院，成都 610065)

0 引言

裝配線平衡問題(Assembly Line Balancing Problem, ALBP)主要是研究在滿足各類約束的條件下，如何將各裝配工序合理分配入工位，達到減少人力和設備資源浪費、降低成本和提高裝配效率等目的。

近年來，學者們對于裝配線的研究主要集中于改進數學模型和算法，使數學模型能有效反應實際情況，算法求解效率和精度更高。如李愛平等[1]提出了裝配復雜性的測度方法，并建立了考慮裝配復雜性的ALBP數學模型，應用改進的遺傳算法求解變速箱實例，結果表明了方法的有效性。王共冬等[2]定義了能力因子，用于修正工人和設備對裝配線的影響，采用改進后的Memetic算法求解，通過對比說明了該方法求解結果更符合實際。徐立云等[3]建立了考慮作業(yè)人員疲勞的多目標優(yōu)化數學模型，利用改進的粒子群優(yōu)化算法求解軸承座分裝線，驗證了方法的有效性。Pereira J等[4]為了解決以成本為導向，考慮任務分配和設備決策的機器人ALBP，提出了一種結合遺傳算法和其他優(yōu)化方法的混合式算法，通過實驗證明了算法的優(yōu)越性。劉雪梅等[5]考慮工位復雜度對裝配線的影響，提出工位復雜性測度方法，建立ALBP模型，以某變速箱裝配線為例，采用改進的遺傳算法有效求解了該問題。

目前很多裝配線依然以人工為主，工人作為裝配線中最具能動性的因素，應充分考慮其帶來的影響[6]。大部分學者從人機工程學角度出發(fā)，如曹婧華[7]提出考慮工人心理承受和疲勞恢復的ALBP模型，應用遺傳算法求解，求解結果更具使用價值。Bortolini M等[8]提出了最小化節(jié)拍和人機工程學風險的多目標ALBP模型，以某廚房電器裝配線為例驗證了多目標模型。Battini D等[9]提出裝配線平衡和零件供給的綜合問題，考慮人機工程學，建立了整數混合模型。少部分學者研究了ALBP中的工人分配問題，如Sungur B等[10]將工人技能等級排序，根據任務技能需求不同進行工人合理分配，建立總成本最小為優(yōu)化目標的數學模型。Oksuz M K等[11]根據不同工人對不同任務的績效不同，從作業(yè)績效均衡性角度，建立了裝配線工人分配和平衡問題的非線性模型，使用人工蜂群算法和遺傳算法求解該類問題。上述從工人角度出發(fā)的ALBP研究，以工人會所有工序操作為前提，未考慮工人技能水平不一，工序難度等帶來的影響。實際中，工序重新分配后，工人上崗可能會需要學習部分工序操作，給企業(yè)帶來培訓成本，且學習的時候，裝配線不能正常運行，會給企業(yè)造成重大損失。因此需要對工人進行合理分配，使得全部工人需要學習的總時間盡可能最少。

目前文獻缺乏對這一角度的工人分配方法和數學模型研究，本文為此提出了一種基于匈牙利算法的工人分配方法，建立了考慮工人分配的多目標優(yōu)化模型。并針對此模型，設計了多目標鯨魚優(yōu)化算法，最后應用于某公司連接器實例。

1 裝配線優(yōu)化模型構建

1.1 工人分配

裝配線工人指派問題可描述為：已知n個工位中的工序內容、m個工人及其會操作的工序情況和工人學習各工序操作所需的平均時間sti(i=1,2,…,n)，按照一個工位只需要一個工人，一個工人不能被重復分配的原則，合理從m個工人中分配n個工人至n個工位，使工人學習總時間最少。

工人學習時間情況矩陣WSn×m，行代表工位，列代表工人，WS(i,j)=k，代表工人j去工位i需要學習k分鐘。根據工人分配原則，問題轉化為從矩陣WS中的不同行不同列選取n個數，使其總和最小。本文采用匈牙利指派算法求解此問題，該算法基于如下性質：

設指派模型的效益矩陣為Ci,j(本文為WS)，若Ci,j某行或列減去同一個常數，得到新矩陣Bi,j,以Bi,j或Ci,j為效益矩陣的指派模型具有相同的最優(yōu)解(相同的指派方式)[12]。

算法步驟如下：

步驟1：用0元素補全矩陣WSn×m為方陣WSm×m；行歸約：每行所有元素減去該行元素最小值；列歸約：每列元素減去該列元素最小值。

步驟2：用最少的直線覆蓋方陣中的0，若直線數小于方陣維度m，則轉至步驟3，若等于則轉至步驟4。

步驟3：找出未被直線覆蓋的數中的最小值min，未被畫線的行減去min，畫線的列加上min，移除直線，轉至步驟2。

步驟4：移除補全方陣時的0元素，找出n個不同行不同列的0元素，被選擇的0元素代表最終分配方案。

1.2 考慮工人分配的裝配線多目標優(yōu)化模型

(1)模型將會涉及的符號說明如表1所示。

表1 符號說明表

(2)確定目標函數：

(1)

(2)

(3)

(4)

minf=[CT(x),SI(x),WSI(y,z)],
(x∈X,y∈WS,z∈WA)

(5)

式(1)為生產節(jié)拍計算方法；式(2)為平滑指數計算方法；式(3)表示WS中元素的計算方法；式(4)為工人學習總時間計算方法；式(5)表示優(yōu)化目標為生產節(jié)拍CT、平滑指數SI和工人學習總時間WSI，綜合考慮了生產效率、裝配線平衡和工人技能情況，其中x，y，z為決策變量。

(3)約束條件：

(6)

(7)

(8)

(9)

(10)

(11)

式(6)～式(8)為工序分配約束，表示每一個工序都被分配入了工位中、未被重復分配和滿足優(yōu)先關系；式(9)為工位作業(yè)時間約束，表示各工位作業(yè)時間應不大于節(jié)拍；式(10)和式(11)為工人分配約束，表示各個工位需要一個工人，且工人未被重復分配。

2 多目標鯨魚優(yōu)化算法(MOWOA)

2.1 鯨魚優(yōu)化算法(WOA)

Mirjalili S等[13]在2016年提出了WOA。該算法具有參數少，原理簡單，求解精度高等優(yōu)點[14]。WOA實質是模擬鯨魚捕食行為，鯨魚更新位置方式有3種：包圍捕食、泡網攻擊和隨機搜尋獵物。

(1)包圍捕食

此方式是模擬鯨魚找到并包圍獵物的捕食行為，在WOA中，假定最優(yōu)候選解是獵物(頭鯨)所在位置，其他鯨魚將靠向頭鯨進而更新自己的位置。位置更新的數學表達式為：

D=|C·X*(t)-X(t)|

(12)

X(t+1)=X*(t)-A·D

(13)

式(12)和式(13)中，X*(t)代表第t代頭鯨的位置，X(t)代表第t代中鯨魚個體的位置，t為迭代次數，A和C為系數變量A和C定義如下：

a=2-(2t/M)

(14)

A=2a·r1-a

(15)

C=2·r2

(16)

式(14)為收斂因子a更新公式，其中M為最大迭代次數，表示a隨著迭代從2線性遞減到0。式(15)和式(16)為A，C更新公式，其中r1和r2為[0,1]之間的隨機數。

(2)泡網攻擊

此方式是模擬鯨魚氣泡捕食行為，分為兩種策略，描述如下：

1)搖擺包圍捕食

此階段鯨魚位置根據式(13)更新，此過程A取值范圍為[-a,a]，若A在[-1,1]之間，鯨魚將會更新到當前位置和頭鯨位置之間。

2)螺旋式氣泡捕食

此階段，鯨魚計算出自身到頭鯨的距離，接著螺旋式移動靠近頭鯨，數學模型如下：

D′=|X*(t)-X(t)|

(17)

X′(t+1)=D′·ebl·cos(2πl(wèi))+X*(t)

(18)

式(17)和式(18)中D′為第i頭鯨魚到頭鯨的距離，b為螺旋形狀常數，l為[-1,1]之間的隨機值。

假定鯨魚執(zhí)行兩種捕食策略的概率各為50%，則此階段鯨魚位置更新公式為：

(19)

式中，p為[0,1]之間的隨機數。

(3)隨機搜尋獵物

此方式是模擬鯨魚隨著伙伴隨機搜尋獵物的捕食行為。鯨魚更新位置是以A值為基礎，當|A|>1時，鯨魚不再跟著頭鯨更新位置，而是全局隨機搜尋獵物，跳出局部最優(yōu)。位置更新公式如下：

D=|C·Xrand-X(t)|

(20)

X(t+1)=XrandT-A·D

(21)

式(20)和式(21)中，Xrand為當前鯨魚種群中一個隨機個體所在的位置。

2.2 鯨魚位置的編碼與解碼

本文采用基于權重的鯨魚位置編碼解碼方式，得到工位信息矩陣X，為后續(xù)計算決策變量值提供數據支持。

鯨魚個體位置由N(工序總數)個隨機數排列組成，編碼時，隨機數的索引值代表工序，數值大小代表對應工序的權重，權重大的工序會優(yōu)先得到分配。

在上述編碼方式下，解碼分為3個步驟：

步驟1：生成工序順序集合R，該集合滿足工序優(yōu)先順序，并符合權重優(yōu)先規(guī)則。

步驟2：將集合中的工序分配入各個工位中，得到工位信息矩陣X。

步驟3：求出各工位作業(yè)時間、工人學習時間和工人分配方案。

2.3 多目標鯨魚優(yōu)化算法設計

(1)外部備選解集paretoSet更新機制

paretoSet中解的個數確定為n。合并上一代paretoSet和當前鯨魚種群為待選解集allSet。對allSet進行層級劃分、擁擠度排序和刪除部分重復解等操作，從中選取n個備選解，更新paretoSet。

層級劃分方法：從allSet中選出非支配鯨魚個體，加入nonbadSet集合，剩余鯨魚個體加入badSet集合。其中非支配鯨魚個體代表其目標函數值不全劣于其他個體。

(22)

具體更新算法偽代碼如下：

圖1 pareto解集更新算法流程圖

算法在paretoSet最后一次執(zhí)行解添加操作時，對當前層的非劣解集進行擁擠度排序和刪除重復解操作，適當增加解的多樣性的同時，保證解的優(yōu)越性。

(2)頭鯨選擇方式

合并當前種群和paretoSet為allSet，從中選出頭鯨備選個體，并加入集合selectSet，從selectSet中隨機選取一個鯨魚個體作為頭鯨，使算法較均衡地往各個目標函數值最優(yōu)方向搜索，提高解的優(yōu)越性。頭鯨選擇算法偽代碼如下：

圖2 頭鯨選擇算法流程圖

(3)多目標鯨魚優(yōu)化算法

綜上所述，MOWOA偽代碼如下:

圖3 MOWOA算法流程圖

3 應用實例

3.1 連接器實例介紹

本文實例來源為某公司連接器，如圖4所示，其內部結構復雜。經過現場實地調研，收集和整理相關數據，得到連接器裝配線工序信息、工人技能情況和工序學習時間等數據。工序作業(yè)時間如表2所示，裝配工序順序如圖5所示，工人已會工序情況如表3所示，工序學習時間如表4所示。

圖4 連接器產品圖

表2 工序作業(yè)時間

續(xù)表

圖5 裝配順序圖

表3 工人技能情況表

表4 工序學習時間表

3.2 結果分析

本文裝配線實例給定工標題系位數為12，根據前文建立的數學模型，在Windows10 64位操作系統(tǒng)、內存8G處理器Intel(R)Core(TM)i5-8400的計算機配置下，采用MATLAB編程，算法參數設置如表5所示。

表5 算法參數表

圖6～圖8為節(jié)拍、平滑指數和工人學習時間3個目標的優(yōu)化過程，表示每代鯨魚種群中各目標的最優(yōu)值。由圖可知，3個目標經過多次迭代后都到達一個較低的值收斂，證明了算法能有效優(yōu)化3個目標。

圖6 CT優(yōu)化過程圖

圖7 SI優(yōu)化過程圖

圖8 工人學習時間優(yōu)化過程圖

圖9 由最后的pareto解集得來，以工人學習時間優(yōu)化目標為x軸，節(jié)拍和平滑指數為y軸。由圖9可知，整體上節(jié)拍和平滑指數與工人學習時間呈負相關，說明CT/SI更優(yōu)的工序分配下，工人分配后，工人學習時間更多，三者難以同時保證最優(yōu)，決策者可根據傾向從pareto解集中選擇相應解。

圖9 優(yōu)化目標關系圖

從最后解中選擇了4種具有代表性的分配方案，如表7～表9所示，符號說明見表6。

表6 符號說明表

表7 工序分配方案1

表8 工序分配方案2

表9 工序分配方案3

由表7～表9可知，工序分配符合裝配順序，未出現重復分配和少分配的情況；工人安排也符合分配原則，說明算法求解結果符合模型所定約束。由表8可知，不同的工序和工人分配，優(yōu)化目標值可能相同。這使得企業(yè)決定方案時靈活性更大。

4 結束語

本文分析了目前ALBP中對工人研究的不足，為提高裝配效率和降低成本，提出了工人分配方法、多目標優(yōu)化模型和多目標鯨魚優(yōu)化算法。以匈牙利算法進行工人分配的方式，能使工人學習時間最少，從而降低工人學習帶來的影響。以某公司連接器為例，驗證所提模型與算法，發(fā)現算法求解結果符合模型所定約束，且優(yōu)化效果明顯，說明算法能有效解決該類模型問題；生產節(jié)拍和平滑指數降低時，工人學習時間呈上升趨勢，優(yōu)化目標間呈明顯博弈；同一優(yōu)化結果下，工序和工人分配方案可能不同。本文方法能提供多組優(yōu)秀解，企業(yè)決策者可根據實際情況選擇分配方案。接下來將繼續(xù)探索符合實際的優(yōu)化目標，設計更具效率的優(yōu)化算法。