鄧 超，胡瑞飛，蔣捷峰，殷國(guó)富

(四川大學(xué)機(jī)械工程學(xué)院，成都 610065)

0 引言

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

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

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

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

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

1.1 工人分配

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

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

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

算法步驟如下：

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

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

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

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

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

(1)模型將會(huì)涉及的符號(hào)說明如表1所示。

表1 符號(hào)說明表

(2)確定目標(biāo)函數(shù)：

(1)

(2)

(3)

(4)

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

(5)

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

(3)約束條件：

(6)

(7)

(8)

(9)

(10)

(11)

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

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

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

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

(1)包圍捕食

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

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

(12)

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

(13)

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

a=2-(2t/M)

(14)

A=2a·r1-a

(15)

C=2·r2

(16)

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

(2)泡網(wǎng)攻擊

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

1)搖擺包圍捕食

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

2)螺旋式氣泡捕食

此階段，鯨魚計(jì)算出自身到頭鯨的距離，接著螺旋式移動(dòng)靠近頭鯨，數(shù)學(xué)模型如下：

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

(17)

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

(18)

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

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

(19)

式中，p為[0,1]之間的隨機(jī)數(shù)。

(3)隨機(jī)搜尋獵物

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

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

(20)

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

(21)

式(20)和式(21)中，Xrand為當(dāng)前鯨魚種群中一個(gè)隨機(jī)個(gè)體所在的位置。

2.2 鯨魚位置的編碼與解碼

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

鯨魚個(gè)體位置由N(工序總數(shù))個(gè)隨機(jī)數(shù)排列組成，編碼時(shí)，隨機(jī)數(shù)的索引值代表工序，數(shù)值大小代表對(duì)應(yīng)工序的權(quán)重，權(quán)重大的工序會(huì)優(yōu)先得到分配。

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

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

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

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

2.3 多目標(biāo)鯨魚優(yōu)化算法設(shè)計(jì)

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

paretoSet中解的個(gè)數(shù)確定為n。合并上一代paretoSet和當(dāng)前鯨魚種群為待選解集allSet。對(duì)allSet進(jìn)行層級(jí)劃分、擁擠度排序和刪除部分重復(fù)解等操作，從中選取n個(gè)備選解，更新paretoSet。

層級(jí)劃分方法：從allSet中選出非支配鯨魚個(gè)體，加入nonbadSet集合，剩余鯨魚個(gè)體加入badSet集合。其中非支配鯨魚個(gè)體代表其目標(biāo)函數(shù)值不全劣于其他個(gè)體。

(22)

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

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

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

(2)頭鯨選擇方式

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

圖2 頭鯨選擇算法流程圖

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

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

圖3 MOWOA算法流程圖

3 應(yīng)用實(shí)例

3.1 連接器實(shí)例介紹

本文實(shí)例來源為某公司連接器，如圖4所示，其內(nèi)部結(jié)構(gòu)復(fù)雜。經(jīng)過現(xiàn)場(chǎng)實(shí)地調(diào)研，收集和整理相關(guān)數(shù)據(jù)，得到連接器裝配線工序信息、工人技能情況和工序?qū)W習(xí)時(shí)間等數(shù)據(jù)。工序作業(yè)時(shí)間如表2所示，裝配工序順序如圖5所示，工人已會(huì)工序情況如表3所示，工序?qū)W習(xí)時(shí)間如表4所示。

圖4 連接器產(chǎn)品圖

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

續(xù)表

圖5 裝配順序圖

表3 工人技能情況表

表4 工序?qū)W習(xí)時(shí)間表

3.2 結(jié)果分析

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

表5 算法參數(shù)表

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

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

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

圖8 工人學(xué)習(xí)時(shí)間優(yōu)化過程圖

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

圖9 優(yōu)化目標(biāo)關(guān)系圖

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

表6 符號(hào)說明表

表7 工序分配方案1

表8 工序分配方案2

表9 工序分配方案3

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

4 結(jié)束語

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