第II類雙邊拆卸線平衡問題建模與優化

王書偉, 徐國勛, 劉 佳

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

0 引言

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

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

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

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

1 問題描述與數學模型

1.1 問題描述

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

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

1.2 符號設置

問題模型涉及的符號設置如下：

I：為任務集合，一個零件對應一項拆卸任務。

W：為工作站集合。

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

Lt：為分配到左側工位的任務集合。

Rt：為分配到右側工位的任務集合。

Et：為分配到左側或右側工位均可的任務集合。

ti：為任務i作業時間。

tid：為任務i的等待時間。

STwl:為分配到w工作站中l側工位的任務拆卸結束時間。

Pi：為任務i直接前驅任務集。

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

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

CT：為整數變量，表示節拍時間。

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

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

1.3 數學模型

企業在對報廢汽車實施拆卸時，需在滿足環保要求下最大化拆解線效益，因此所構建問題優化模型如下：

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

(1)

(2)

(10)

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

2 算法設計與實現

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

2.1 編碼與解碼

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

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

2.2 種群初始化階段

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

2.3 族群劃分

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

2.4 局部搜索

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

2.5 個體學習

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

2.6 族群混合與再分

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

2.7 節拍時間調整

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

3 算法有效性分析

3.1 算例驗證

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

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

表1 VNS-SLFA、VNS和DABC求解結果對比

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

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

3.2 實例分析

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

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

4 結論

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

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