王書(shū)偉, 徐國(guó)勛, 劉 佳

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

0 引言

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

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

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

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

1 問(wèn)題描述與數(shù)學(xué)模型

1.1 問(wèn)題描述

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

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

1.2 符號(hào)設(shè)置

問(wèn)題模型涉及的符號(hào)設(shè)置如下：

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

W：為工作站集合。

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

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

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

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

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

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

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

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é)拍時(shí)間。

swl：為0-1變量，1表示開(kāi)啟，0則表示為開(kāi)啟。

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

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

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

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

(1)

(2)

(10)

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

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

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

2.1 編碼與解碼

TDLBP-II中存在先后關(guān)系和操作方位約束，構(gòu)建基于一維正負(fù)整數(shù)排列的編碼，排列的順序表示任務(wù)拆卸順序，排列中各位置上帶符號(hào)整數(shù)表示所分配的任務(wù)編號(hào)與操作方位(“+”代表右側(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)品的一個(gè)明確拆卸過(guò)程，可表示一個(gè)可行解。

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

2.2 種群初始化階段

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

2.3 族群劃分

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

2.4 局部搜索

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

2.5 個(gè)體學(xué)習(xí)

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

2.6 族群混合與再分

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

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

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

3 算法有效性分析

3.1 算例驗(yàn)證

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

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

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

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

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

3.2 實(shí)例分析

本節(jié)以大型打印機(jī)(含55個(gè)零件)為例，進(jìn)一步驗(yàn)證算法的有效性及說(shuō)明優(yōu)化任務(wù)在工作站上的分配在企業(yè)生產(chǎn)時(shí)的重要性。拆卸線設(shè)有4個(gè)工作站，其中任務(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)系請(qǐng)參見(jiàn)文獻(xiàn)[18]。將算法迭代時(shí)間設(shè)為200s，所得最好拆卸方案如圖8所示。

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

4 結(jié)論

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

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