第II類雙邊拆卸線平衡問題建模與優(yōu)化

王書偉, 徐國勛, 劉 佳

(1.山東科技大學 經(jīng)濟管理學院,山東 青島 266590; 2.海南大學 旅游學院,海南 ?？?570228; 3.青島理工大學 商學院,山東 青島 266520)

0 引言

截至2019年底我國汽車保有量達2.6億輛，同比增長8.83%，產(chǎn)銷量已連續(xù)11年蟬聯(lián)全球第一。我國汽車保有量持續(xù)增長的同時，報廢量也在大幅增加，對其進行再利用，不僅能實現(xiàn)資源的循環(huán)，還能降低對環(huán)境危害。拆卸是回收再利用的重要環(huán)節(jié)，拆卸線平衡問題DLBP在國內(nèi)外重要期刊均有報道，這些工作大部分是基于精確方法和智能算法，研究拆卸線上作業(yè)的均衡分配。

Bentaha等[1]針對拆卸過程作業(yè)時間的不確定，以最大化拆卸利潤為目標，采用隨機動態(tài)規(guī)劃求解部分拆卸DLBP；Altekin[2]針對隨機DLBP，提出分段線性規(guī)劃法。Ilgin等[3]通過線性物理規(guī)劃解決多產(chǎn)品混流DLBP。DLBP已被證明為NP-complete[4]，其解空間隨著問題規(guī)模增加呈爆炸式增長，精確方法對大規(guī)模問題無力適從，因此更多學者采用智能算法求解DLBP，以在合理時間內(nèi)得到問題的滿意解。Pistolesi等[5]從工作站開啟數(shù)量、拆卸利潤和拆卸危害角度出發(fā)，構(gòu)建DLBP多目標優(yōu)化模型，提出一種極值多目標遺傳算法，以實現(xiàn)對Pareto前沿解的搜索；Zhu等[6]考慮到實際拆卸過程中的潛在安全隱患，評估危害，并設(shè)計一種螢火蟲算法進行求解；此外，變鄰域搜索算法[7]、人工蜂群算法[8]等智能算法也被應(yīng)用于DLBP的優(yōu)化。

上述研究均是關(guān)于單邊DLBP，針對的是小型廢舊產(chǎn)品拆卸作業(yè)。然而，對于報廢汽車等大型產(chǎn)品，單邊拆卸會造成工人作業(yè)時走動頻繁，而采用雙邊拆卸將工作站分布于傳送裝置的兩側(cè)，兩側(cè)工人并行作業(yè)，可有效減少移動距離提升拆卸效率。為此，鄒賓森等[9]建立以最小化工作站數(shù)量、最小化空閑時間和盡早拆除高價值零部件為目標的雙邊拆卸線平衡問題模型(two-sided DLBP, TDLBP)，并提出一種Pareto蝙蝠算法求解；王書偉等[10]則進一步考慮最小化工位啟動數(shù)量，以減少工人、設(shè)備等作業(yè)成本投入；考慮拆卸時作業(yè)數(shù)量和作業(yè)時間的不確定性，Wang等[11]構(gòu)建了隨機TDLBP模型，并設(shè)計了離散花朵授粉算法，以優(yōu)化作業(yè)負荷、能耗及利潤指標。

以上DLBP的研究都是在給定節(jié)拍時間前提下，最小化工作站開啟數(shù)量以降低固定成本投入，該類問題可定義為第I類問題，而第II類問題則是在工作站數(shù)量固定的情況下，最小化節(jié)拍時間以最大化拆卸線產(chǎn)能。目前，僅有Bentaha等[12]、王書偉等[13]和Kalaycllar等[14]以工作站作業(yè)負荷、利潤為目標對第II類單邊DLBP(DLBP-II)展開研究。然而，對于報廢汽車拆解企業(yè)已規(guī)劃成型的拆卸線，兩側(cè)工位數(shù)量已確定，為了提高拆卸效率，需最小化節(jié)拍時間以在最短周期內(nèi)完成產(chǎn)品拆卸，因此對第II類TDLBP(TDLBP-II)進行研究符合實際拆卸情況。鑒于此，本文以最短節(jié)拍時間、負荷均衡和優(yōu)先拆除有危害零部件為目標建立TDLBP-II優(yōu)化模型，并設(shè)計了一種變鄰域蛙跳算法(shuffled frog leaping algorithm with variable neighborhood search, VNS-SFLA)進行求解。蛙跳算法概念簡單、參數(shù)少且計算速度快、尋優(yōu)能力強，在選址問題[16]、車間調(diào)度[15]等組合優(yōu)化問題得到廣泛應(yīng)用。TDLBP-II也屬于組合優(yōu)化問題，因此本文將蛙跳算法應(yīng)用于該問題求解，并與變鄰域算法進行融合，針對問題特點，對算法進行改進，以提升尋優(yōu)能力。

1 問題描述與數(shù)學模型

1.1 問題描述

雙邊拆卸線如圖1所示，左右兩側(cè)相對應(yīng)的兩個工位稱為一個工作站或成對工位，彼此稱對方為伴隨工位。在拆卸過程中，由于零部件所處位置不同，作業(yè)任務(wù)僅能分配到左側(cè)(L)工位、右側(cè)(R)工位或兩側(cè)(E)工位均可，這種分配限制稱為任務(wù)的操作方位約束。

圖2為任務(wù)優(yōu)先關(guān)系圖，用于表示拆卸先后關(guān)系，其中圓表示拆卸任務(wù)，箭頭表示拆卸先后，圓外字母和數(shù)字表示任務(wù)分配方位和拆卸時間。以圖中任務(wù)7為例，其與任務(wù)6和8存在直接關(guān)聯(lián)，在任務(wù)6拆卸完后，任務(wù)7才能被分配到右側(cè)工位進行拆卸，作業(yè)時間為10秒，而后任務(wù)8才能被分配。

1.2 符號設(shè)置

問題模型涉及的符號設(shè)置如下：

I：為任務(wù)集合，一個零件對應(yīng)一項拆卸任務(wù)。

W：為工作站集合。

L：為工位邊{0，1}集合，0代表右側(cè)，1代表左側(cè)。

Lt：為分配到左側(cè)工位的任務(wù)集合。

Rt：為分配到右側(cè)工位的任務(wù)集合。

Et：為分配到左側(cè)或右側(cè)工位均可的任務(wù)集合。

ti：為任務(wù)i作業(yè)時間。

tid：為任務(wù)i的等待時間。

STwl:為分配到w工作站中l(wèi)側(cè)工位的任務(wù)拆卸結(jié)束時間。

Pi：為任務(wù)i直接前驅(qū)任務(wù)集。

hi：表示零部i的危害性。

PSlk：表示在拆卸線的l側(cè)工位，任務(wù)k所分配的拆卸位置；如左側(cè)工位的任務(wù)分配序列為{1,3,2,5,9,11}，那么任務(wù)5的分配位置PS15為4。

CT：為整數(shù)變量，表示節(jié)拍時間。

swl：為0-1變量，1表示開啟，0則表示為開啟。

xiwl：為0-1變量，1表示分配，0則表示未分配。

1.3 數(shù)學模型

企業(yè)在對報廢汽車實施拆卸時，需在滿足環(huán)保要求下最大化拆解線效益，因此所構(gòu)建問題優(yōu)化模型如下：

minf1=CT=max{STwl|w∈W,l∈L}

(1)

(2)

(10)

目標函數(shù)：式(1)為最小化節(jié)拍時間式(2)最小化平衡指數(shù)，以將任務(wù)在各工位上均衡分配；式(3)為優(yōu)先拆卸有危害零部件。約束條件：式(4)表示一個任務(wù)僅能分配一次；式(5)為拆卸先后關(guān)系約束限制；式(6)滿足每個工位的任務(wù)作業(yè)結(jié)束時間不能超過節(jié)拍時間；式(7)表示每一個工作站至少有一側(cè)工位啟動，即沒有工作站閑置；式(8)、(9)、(10)表示零部件分配滿足操作方位約束。

2 算法設(shè)計與實現(xiàn)

蛙跳算法是受青蛙覓食過程啟發(fā)而演變的一種群智能算法[17]，其結(jié)合了文化基因算法和粒子群算法的優(yōu)點，具備較強的全局搜索能力，已應(yīng)用于多種組合優(yōu)化問題，然而也存在過早收斂等不足。本文針對所解決問題特點對算法進行改進，以進一步提高搜索效率，具體描述如下。

2.1 編碼與解碼

TDLBP-II中存在先后關(guān)系和操作方位約束，構(gòu)建基于一維正負整數(shù)排列的編碼，排列的順序表示任務(wù)拆卸順序，排列中各位置上帶符號整數(shù)表示所分配的任務(wù)編號與操作方位(“+”代表右側(cè)工位，“-”代表左側(cè)工位)。例如整數(shù)排列S1{-1，+4，-3，-2，+6，-5，-9，+7，+8，-11，+10}表示先將任務(wù)1分配至左側(cè)工位，再將任務(wù)4分配至右側(cè)，按照排列依次分配，最后將任務(wù)10分配至右側(cè)工位拆卸結(jié)束，該排列為圖2所示產(chǎn)品的一個明確拆卸過程，可表示一個可行解。

由于TDLBP-II的節(jié)拍時間未知，且受拆卸優(yōu)先關(guān)系的影響，待分配任務(wù)若未分配至其前驅(qū)任務(wù)所在同側(cè)，則需“等待”其前驅(qū)拆卸完畢后分配。因此，在解碼時，需首先確定理論節(jié)拍時間(最長任務(wù)作業(yè)時間)，然后對任務(wù)進行依次分配，工位最長結(jié)束時間為實際節(jié)拍時間。以整數(shù)排列S1在工作站數(shù)量m=3(6個工位)的雙邊拆卸線上進行解碼為例，解碼結(jié)果如圖3所示，右側(cè)第三個工位作業(yè)結(jié)束時間最長，因此實際節(jié)拍時間為25。

2.2 種群初始化階段

在覓食過程中，若種群中的個體能較廣分散在解空間，將大幅提升搜索效率。為了保證初始種群個體的多樣性，分別采用優(yōu)先分配作業(yè)時間最長/最短任務(wù)的方法生成差異顯著的兩個個體，剩余個體基于這兩個個體隨機構(gòu)造，以擴大個體差異。

2.3 族群劃分

種群初始化完畢后，需將個體劃分到m個族群中，然后再以族群為單位進行覓食。TDLBP-II中最小節(jié)拍時間與平衡指數(shù)兩個目標之前存在相關(guān)性，與危害指數(shù)存在沖突，在此將種群中的個體按照字典排序進行評價，并選擇一個較好個體依次放入每個族群中，余下個體隨機分配。

2.4 局部搜索

蛙跳算法以族群為單位進行覓食，最差個體通過最優(yōu)個體的引導得以改進。然而，在實際搜索過程中較差個體所代表解也較差，往往不具備搜索潛力。為了提高族群進化速度，采用變鄰域搜索(variable neighborhood search, VNS)對族群個體進行局部搜索。VNS是將不同的鄰域結(jié)構(gòu)組建成一個鄰域結(jié)構(gòu)集，與單一鄰域搜索相比，VNS搜索范圍更廣、能更好地跳出局部最優(yōu)，搜索過程如圖4所示。鄰域結(jié)構(gòu)是VNS的核心，在此針對TDLBP-II特點，設(shè)計了如圖5所示的三種鄰域結(jié)構(gòu)。

2.5 個體學習

自然界中的各類種群都會通過對自身的不斷調(diào)整來提升適應(yīng)周邊環(huán)境的能力，以向有利于種群發(fā)展的方向進化。蛙跳算法強調(diào)族群內(nèi)部個體間的學習，忽視了個體自主調(diào)整的能動性，和族群精英個體間的交流。為此，在族群內(nèi)部進化完后，組織各族群最優(yōu)個體進行自學習和相互學習：基于0-1整數(shù)的互學習操作和基于優(yōu)先順序的0-1整數(shù)自學習操作(圖6)，從而加強精英個體的相互學習及自我學習，進一步提升精英個體進化速度，與此同時還可有效避免陷入局部最優(yōu)。

2.6 族群混合與再分

經(jīng)過一定周期進化后，所有族群將重新混合，然后按照2.3節(jié)中所采用方法對個體進行再劃分，以實現(xiàn)種群間信息的傳遞與交流。經(jīng)過如此往復，保證后代個體有更好的適應(yīng)度，進而尋得問題最優(yōu)解。

2.7 節(jié)拍時間調(diào)整

節(jié)拍時間CT是從理論最小節(jié)拍時間(最大任務(wù)作業(yè)時間與平均任務(wù)作業(yè)時間的大者)開始搜索。在此基于二分法的定界策略，通過不斷調(diào)整CT的上下界實現(xiàn)快速對最優(yōu)CT的搜索[12]。若搜索得到的CT大于當前設(shè)置的CT，則將CT下界變更為當前設(shè)置的CT，并重置CT為搜索得到CT和所設(shè)置CT的平均值；反之則下界不變，CT重置為下界CT與搜索得到CT的平均值。該策略可更快實現(xiàn)節(jié)拍時間向最優(yōu)節(jié)拍時間的快速靠攏。

3 算法有效性分析

3.1 算例驗證

目前尚無TDLBP-II研究算例，但已有單邊直線DLBP可以看成是雙邊拆卸線一側(cè)工位未開啟的特殊形式。本節(jié)采用P10算例[7](含10個零件)、P25算例[7]和P47算例[8]三個單邊拆卸算例對所提算法的有效性進行驗證，將三個算例中任務(wù)操作方位均設(shè)置為右側(cè)工位，任務(wù)優(yōu)先關(guān)系、作業(yè)時間(取整)和危害性等具體數(shù)據(jù)請參見對應(yīng)文獻。為了保證測試的有效性，在CPU i3-7100 3.9GHz，4G電腦上，采用C++編碼，將P10、P25、P47分別在0.5s、2.5s、5s內(nèi)求解，每個運行25次，計算平均值(D)和均方差(V)，并與變鄰域搜索算法[7]、離散人工蜂群算法[8](DABC)求解進行對比，結(jié)果請見表1。

通過表1可以看出，P10算例工作站為2的情況下，三種算法在節(jié)拍時間與平衡指數(shù)兩個目標上的求解結(jié)果相同，但所提VNS-SLFA在危害指數(shù)方面要好于VNS和DABC兩種算法。而在其他不同工作站數(shù)量下，三種算法在指定時間內(nèi)每次均能搜索到問題的最優(yōu)解。圖7為拆卸方案{5,10,6,7,9,4,8,1,2,3}在設(shè)有5個工作站(10個工位)的雙邊拆卸線上的分配情形，該方案節(jié)拍時間為36s，拆卸過程所產(chǎn)生的空閑時間最少，任務(wù)分配也最均衡。

表1 VNS-SLFA、VNS和DABC求解結(jié)果對比

在P25算例工作站設(shè)置為6和8的兩種情況下，三種算法在各個目標上的結(jié)果一致。在剩余三種情形中，三種算法在節(jié)拍時間方面求解結(jié)果相同，但在工作站為7時，所提算法在平衡指數(shù)方面要優(yōu)于VNS和DABC兩種算法，在工作站數(shù)量為9、10時，雖三種算法的平衡指數(shù)也一致，但在危害指數(shù)方面，所提算法要優(yōu)于其他兩種算法。通過對比發(fā)現(xiàn)，所提算法在P25算例中整體搜索質(zhì)量要好于VNS和DABC。另外需要注意的是，在工作站數(shù)量為9和10的兩種情況下，拆卸線的節(jié)拍時間均為18，但在平衡指數(shù)方面，工作站為9的情況要明顯小于工作站為10的情況，說明當節(jié)拍時間一定后，工作站數(shù)量越多平衡指數(shù)會越大，此時工作站的空閑時間也會增多，拆卸線平衡性變差。

隨著問題規(guī)模的繼續(xù)增大，在P47算例中，除了工作站數(shù)量為4的情況下，所提算法在危害指數(shù)上比VNS算法求解效果要差外，在其余情況所提算法求解結(jié)果都要好于其他兩種算法，且優(yōu)勢較為明顯，體現(xiàn)更好的尋優(yōu)效果。

3.2 實例分析

本節(jié)以大型打印機(含55個零件)為例，進一步驗證算法的有效性及說明優(yōu)化任務(wù)在工作站上的分配在企業(yè)生產(chǎn)時的重要性。拆卸線設(shè)有4個工作站，其中任務(wù)6/9/11-15/17/25/31/33-35/37-38/43/45-46/51/53-54操作方位為右側(cè)工位，任務(wù)3/19/28/49為左右兩側(cè)工位均可，剩余任務(wù)為左側(cè)工位，任務(wù)拆卸優(yōu)先關(guān)系請參見文獻[18]。將算法迭代時間設(shè)為200s，所得最好拆卸方案如圖8所示。

通過圖8可以看出，零部件在雙邊拆卸線上進行作業(yè)時，第一個工作站的左側(cè)工位作業(yè)結(jié)束時間91s為所有工位中最長作業(yè)結(jié)束時間，則設(shè)為拆卸線節(jié)拍時間?？偪臻e時間為每個工位上的空閑時間和：0+2+0+13+1+13+0+13=42s。在整個作業(yè)過程中僅在拆卸零件9時產(chǎn)生了1次等待，時間為9s。通過該方案實施產(chǎn)品拆卸，拆卸線空閑時間與等待時間較少，任務(wù)分配相對平衡，在很大程度上避免了工人和機器，在拆卸過程中處于“無事可做”的狀態(tài)，保證了拆卸效率，提高了拆卸線產(chǎn)能。

4 結(jié)論

本文對工作站數(shù)量固定的雙邊拆卸線平衡問題展開研究，建立問題數(shù)學模型，然后采用變鄰域蛙跳算法求解。通過對不同算例測試表明，相較于VNS和DABC兩種算法，所提VNS-SFLA具有更好的尋優(yōu)效果。對實例產(chǎn)品拆卸過程進行分析表明優(yōu)化任務(wù)在拆卸線上的分配，使任務(wù)盡可能均衡在各工位上分配，能夠減少拆卸等待時間和閑置時間，縮短節(jié)拍時間，最大化拆卸線產(chǎn)能。

此外，需特別指出的是當雙邊拆卸線只開啟一側(cè)工位時，可看成是單邊拆卸，因此單邊拆卸可以看成是雙邊拆卸的特殊形式，所以本文所構(gòu)建的第II類雙邊DLBP優(yōu)化模型也可適用于第II類單邊DLBP。也正因為此，本文所設(shè)計的變鄰域蛙跳算法不僅能用于TDLBP-II的尋優(yōu)，也可應(yīng)用于DLBP-II的求解，在對算法進行適當?shù)恼{(diào)整還可用于其他類型DLBP的優(yōu)化。另外，本文所提出編碼方式、種群初始化策略、鄰域結(jié)構(gòu)可為其他啟發(fā)式算法求解提供借鑒。但本文研究的TDLBP-II是對廢舊產(chǎn)品完全拆卸，未考慮因零部件損壞導致拆卸中斷現(xiàn)象的發(fā)生以及拆卸線的再平衡，因此，針對產(chǎn)品不完全拆卸與拆卸線再平衡的研究是后續(xù)工作的方向。