考慮拆卸序列的機器人拆卸線平衡優(yōu)化*

賴冬梅,唐秋華

(武漢科技大學a.冶金裝備及其控制教育部重點實驗室;b.機械傳動與制造工程湖北省重點實驗室,武漢 430081)

0 引言

科技的突飛猛進給人類帶來了便捷的生活,同時也對自然環(huán)境造成了破壞,人類面臨著資源短缺和環(huán)境污染的巨大挑戰(zhàn)。我國經(jīng)濟發(fā)展已從高速發(fā)展轉向高質量發(fā)展,傳統(tǒng)制造方式已不能滿足高質量發(fā)展的要求,再制造和綠色制造是實現(xiàn)人與自然協(xié)同發(fā)展的重要方式。再制造拆卸服務作為再制造服務的重要組成部分,是廢舊品再制造資源最大化利用的重要前提,是實現(xiàn)產(chǎn)品多生命周期的必要環(huán)節(jié)[1]。

目前針對廢舊品拆卸規(guī)劃的研究集中在拆卸序列規(guī)劃和拆卸線平衡兩個方面。拆卸線平衡問題的核心是為拆卸工作站分配拆卸任務,從而使拆卸線系統(tǒng)高效運行。自拆卸線平衡模型[2]建立后,很多學者就拆卸線平衡問題的建模和解決方法展開了豐富的研究,但常規(guī)研究專注于不違反廢舊品優(yōu)先關系,缺乏對拆卸序列的考慮。但在實際拆卸過程中,拆卸任務之間可能存在交互,一個零件可能會影響另一零件的基本拆卸時間,即一個零件會阻礙另一零件的拆卸從而需要附加操作,導致產(chǎn)生相應的拆卸作業(yè)時間增量,這就是考慮拆卸序列的拆卸線平衡問題。拆卸作業(yè)時間增量是拆卸總時間的一部分,它會因為拆卸任務順序的不同而變化,導致拆卸總時間變化。在拆卸任務分配后,各工作站的拆卸總時間也會因任務的組合不同而變化,從而影響工作站的負載均衡。

隨著機器人應用的普及,廢舊品拆卸不再局限于手工作業(yè),機器人拆卸在縮短拆卸周期、降低拆卸成本等方面更有優(yōu)勢,機器人拆卸線平衡問題引起了大量學者關注。由于機器人的特殊性,在拆卸過程中的刀具切換時間、方向調整時間和移動時間都不該被忽略。

為此,研究考慮拆卸序列的機器人拆卸線平衡問題是必要的。劉佳等[3]研究了具有多目標且與拆卸順序相關的拆卸線平衡問題。EMRAH等[4]就拆卸線平衡問題提出混合整數(shù)線性規(guī)劃模型及其擴展模型并進行了排序決策。CHEN等[5]不僅考慮廢舊品的優(yōu)先關系,還考慮拆卸任務交互導致的作業(yè)時間增量和機器人拆卸,提出序列相關的機器人拆卸線平衡問題并求解。LIU等[6]同時考慮機器人拆卸序列規(guī)劃和機器人拆卸線平衡問題的優(yōu)化目標,提出改進離散蜜蜂算法用于求解所提問題,該算法盡管能得到較優(yōu)解,但算法穩(wěn)定性還有待提高,數(shù)學模型還有待補充完整。同時,考慮拆卸方向的研究還較少。

針對目前研究的不足之處,在機器人拆卸線平衡問題中考慮拆卸任務之間的序列相關關系,為減少方向調整時間進行方向選擇,構建考慮拆卸序列并帶有多目標的機器人拆卸線平衡問題數(shù)學模型,建立耦合賦權方法并提出一種改進離散粒子群算法,以提高尋找較優(yōu)解的效率和質量。

1 問題陳述

機器人拆卸線平衡問題的目的在于給機器人拆卸生產(chǎn)線尋找最優(yōu)拆卸方案,使得整條線上的多個機器人拆卸工作站負載均衡,減少空閑時間,實現(xiàn)基于并行或串行拆卸線的廢舊品大量拆卸,從而提高拆卸效率,降低拆卸成本。學者評價拆卸方案質量時采用的指標一般包括節(jié)拍時間、平滑指數(shù)、各工作站空閑時間、轉變方向次數(shù)、需求指數(shù)[7]等。

在上述基礎上,同時考慮拆卸順序和多個工作站的拆卸任務分配,得到滿足拆卸先后約束和序列相關關系的可行拆卸序列,進而將任務均衡地分配在各并行工作站上,使拆卸生產(chǎn)線能按一定順序連續(xù)高效地大量拆卸廢舊品,其中拆卸線中每個工作站內(nèi)的拆卸任務執(zhí)行順序都符合可行拆卸序列的順序。值得注意的是,這里的拆卸總時間不再是簡單的基本拆卸時間之和,工作站中拆卸任務之間還存在額外的拆卸時間?；诖私⒁怨ぷ髡緮?shù)量最小、平滑指數(shù)最小和所有工作站中最大作業(yè)時間最小為目標的優(yōu)化模型,同時在排序決策中加入方向選擇,從而減少方向調整時間。

簡而言之,本文研究的拆卸線平衡問題是考慮拆卸序列和機器人拆卸場景的并行工作站直線型單產(chǎn)品拆卸線平衡問題。

2 數(shù)學模型構建

在拆卸過程中,拆卸任務是不可再分的最小自然單位,一個拆卸任務僅能在一個工作站上進行,且每個拆卸任務之間相互獨立[8]。為便于研究,提出以下假設:①每個拆卸工作站僅有一個拆卸機器人;②構成廢舊品的所有零件均須完全拆卸;③每個零件只能由一個機器人工作站進行拆卸;④每個工作站總拆卸時間小等于拆卸線節(jié)拍;⑤每個零件基本拆卸時間固定不變,不考慮準備時間及切換時間等的影響;⑥拆卸過程中機器人末端執(zhí)行器沿著預定的路徑進行拆卸;⑦廢舊品零件除了受拆卸順序優(yōu)先關系約束以外,沒有其他的約束限制[8]。

2.1 符號定義

表1 符號定義

2.2 優(yōu)化模型構建

根據(jù)上述問題描述可建立數(shù)學模型如下:

Minφ=w1F1+w2F2+w3F3

(1)

f1=|S|

(2)

(3)

(4)

Fi=(fi-min(fi))/(max(fi)-min(fi))

(5)

s.t. ∑tXp,t=1,?p

(6)

∑pXp,t=1,?t

(7)

∑tt·Xp,t≤∑tt·Xj,t,?p,j,p∈Hj

(8)

∑pXp,t+1≤∑pXp,t,?t<|P|

(9)

∑s∑cYp,s,c=1,?p

(10)

∑pYp,s,c+1≤∑pYp,s,c,?s,c<|C|

(11)

∑pYp,s,c≤1,?s,c

(12)

∑s∑c(|S|·s+c)·Yp,s,c-∑s∑c(|S|·s+c)·
Yj,s,c≤M·(2-Xp,t-Xj,t+1),?p,j,t,t<|P|

(13)

Lp,s≥btp-M·(1-Yp,s,1),?p,s

(14)

Lp,s≤btp+M·(1-Yp,s,1),?p,s

(15)

Lj,s≥btj+ttp,j+dtp,j+mtp,j-
M·(2-Yp,s,c-Yj,s,c+1),?p,j,s,c<|C|

(16)

Lj,s≤btj+ttp,j+dtp,j+mtp,j-
M·(2-Yp,s,c-Yj,s,c+1),?p,j,s,c<|C|

(17)

(18)

(19)

(20)

(21)

∑d∈DpZp,d=1,?p

(22)

dtp,j≥∑d∈Dp∑d′∈Djatdd′·Zp,d·Zj,d′-
M·(2-Yp,s,c-Yj,s,c+1),?p,j,s,c<|C|

(23)

dtp,j≤∑d∈Dp∑d′∈Djatdd′·Zp,d·Zj,d′+
M·(2-Yp,s,c-Yj,s,c+1),?p,j,s,c<|C|

(24)

式(2)～式(4)表示優(yōu)化目標,工作站數(shù)量最少即拆卸線成本最低,最小化平滑指數(shù)有利于工作站負載均衡。在滿足節(jié)拍的前提下最小化所有工作站中的最大作業(yè)時間,有利于減少閑置時間。為更好地構建目標函數(shù),用式(5)對目標進行歸一化處理,消除它們的量綱從而變成無量綱表達式,再為各目標賦予權重得到目標函數(shù)式(1)。

拆卸序列約束:式(6)～式(7)表示每個零件都必須被拆卸且每次只拆一個零件;式(8)表示零件p先于零件j拆卸;式(9)表示緊前零件拆卸后才能進行緊后零件的拆卸。

任務分配約束:式(10)表示每個零件只能分配到一個工作站上;式(11)表示在每個工作站的拆卸序列中,必須先分前面的位置再分后面的位置;式(12)表示每個工作站中的每個零件最多進行一次拆卸;式(13)表示零件p先于零件j被分配在工作站s上。

拆卸時長約束:式(14)～式(15)表示若p是工作站s上第一個被拆卸的零件,實際拆卸時長等于基本拆卸時長;式(16)～式(17)表示若j是工作站s上位于中間被拆卸的零件,實際拆卸時長等于基本拆卸時長加上其他操作時間。

拆卸節(jié)拍約束:式(18)表示任給定工作站的總作業(yè)時間不得超過節(jié)拍時間。

拆卸時序約束:式(19)表示每個零件的拆卸開始時間和結束時間的關系;式(20)表示當零件p和j存在優(yōu)先干涉關系時,零件p的拆卸結束時間在零件j的拆卸開始時間之前;式(21)表示在拆卸完前一零件后,完成其他操作后才能繼續(xù)進行下一零件的拆卸。

拆卸方向約束:式(22)表示零件p可從d方向拆卸;式(23)～式(24)表示先后拆卸零件p和j所需的方向調整時間。

3 改進離散粒子群算法

粒子群算法(particle swarm optimization,PSO)是一種模擬鳥類覓食飛行中基本規(guī)律的進化算法[9]。標準的粒子群算法一般用來求解連續(xù)優(yōu)化問題,很少用于求解離散優(yōu)化問題。為更好地解決拆卸線平衡這種復雜的、離散的組合優(yōu)化問題。采用能夠解決上述問題的離散粒子群算法[10],并融合遺傳算法中交叉與變異算子,不僅結合了粒子群算法和遺傳算法解決離散NP問題時的優(yōu)勢,還增強了全局搜索能力,避免陷入局部最優(yōu)。同時針對拆卸順序有約束的特性還設計了兩個有效的改進算子,即位移算子和變向算子,增加算法的尋優(yōu)能力。

3.1 編碼及解碼

采用兩段式編碼,包括拆卸序列段和拆卸方向段,其中拆卸序列用來表達拆卸任務的順序,且兩段編碼長度均為|P|(|P|指待拆卸廢舊品的零件總數(shù))。第一行為拆卸序列段,表示廢舊品零件的可行拆卸序列,第二行為拆卸方向段,表示所有零件的拆卸方向,包括X+,X-,Y+,Y-,Z+,Z-。若廢舊品零件數(shù)為6個,編碼格式為2×6,如圖1的編碼部分:{1,6,4,5,3,2;1,4,3,2,5,6}表示依次拆卸零件1/6/4/5/3/2,它們的拆卸方向分別為X+/Y-/Y+/X-/Z+/Z-。

圖1 拆卸編碼及解碼

基于上述編碼,解碼思路為:

(1)為表達廢舊品各零件間拆卸的優(yōu)先關系和阻礙關系,需要建立改進空間干涉矩陣[11],并進行干涉矩陣分析[12],產(chǎn)生初始可行拆卸序列和可行拆卸方向。拆卸一個廢舊品可有多個可行的拆卸序列,一個可行的拆卸序列也可能有多個可行的拆卸方向。

(2)采用機器人工作站分配法[12]將零件分配到相應工作站上,從第一個被拆卸的零件開始,比較其拆卸總時間與節(jié)拍時間的大小,若此零件與其所在工作站的所有零件的拆卸總時間大于節(jié)拍時間,則將該零件分配到下一個工作站。拆卸總時間為基本拆卸時間、刀具切換時間、方向調整時間與移動時間的總和,其中方向調整為0°、90°和180°時的方向調整時間分別為1、2和3。

(3)直至所有零件都分配到工作站上即完成拆卸任務的分配,最后輸出工作站的數(shù)量和拆卸任務的分配情況,如圖1的解碼部分。

3.2 粒子速度和位置更新

標準粒子群算法中的速度和位置更新公式不再適用于組合優(yōu)化問題,文獻[13]在粒子群算法中引入交換子和交換序的概念,基于此重新定義原有速度和位置更新公式為:

(25)

(26)

式中:“⊕”表示速度之間的加法,兩個交換序列合并后形成一個新的交換序列;“-”為位置之間的減法,即由多個交換序列組成的集合;“+”為位置和速度之間的加法,即粒子根據(jù)速度大小進行位置的更新從而得到一個新的拆卸序列;α,β為[0,1]的隨機數(shù),α(pij-xij)和β(pgj-xij)分別表示基本交換序列(pij-xij)和(pgj-xij)中的所有交換子分別以概率α和β保留,概率值越大則保留的交換子就越多。

3.3 改進算子設計

為避免算法陷入局部最優(yōu)困境,融入交叉、變異算子,增設位移算子,增加種群的多樣性并盡可能保留有益序列組合。同時,為有效減少拆卸總時間,就最大作業(yè)時間的機器人工作站中的任務設計變向算子,達到增強算法尋優(yōu)能力目的。

交叉算子采取遺傳算法中的兩點交叉方式,即在個體編碼串中隨機設置兩個交叉點,然后根據(jù)交叉概率Pc=0.7進行交叉點之間基因片段的交換,從而形成新的個體。

變異算子選用遺傳算法中傳統(tǒng)的基本位變異方法,對粒子的編碼以一定的變異概率Pm=0.5隨機指定拆卸序列中某一位置的值并做變異運算。

位移算子與常見的插入算子類似,不同點在于任意截取的是基因片段。任意截取隨機長度的基因片段,在滿足干涉約束的前提下隨機選擇新的插入點將基因片段插入,從而形成新的拆卸序列。

總作業(yè)時間最長的機器人工作站往往是影響拆卸總時間長短的關鍵,考慮設計變向算子,減少拆卸總時間。以圖1所示的包含6個零件的廢舊品拆卸為例,工作站2的總作業(yè)時間最長,對分配至工作站2的拆卸任務“4、5”隨機選擇一個進行拆卸方向調整。

3.4 算法流程

改進離散粒子群算法(improved discrete PSO,IDPSO)的偽代碼如表2所示。

表2 IDPSO偽代碼

4 實驗及案例分析

為便于分析與評價所提IDPSO算法性能,與文獻[6]中的改進離散蜂群算法(IDBA)、遺傳算法(GA)以及離散粒子群算法(DPSO)設計了對比實驗。上述算法均用MATLAB語言編寫,并在搭載AMD Ryzen 5 4600 U with Radeon Graphics 2.10 GHz處理器和16.0 GB機帶RAM的計算機上MATLAB R2019b平臺上運行。表3為案例的部分信息。

表3 12個案例的部分信息

4.1 目標權重確定及算法評價方法

為量化3個目標的權重系數(shù),同時采用網(wǎng)絡分析法(ANP)及熵權法。網(wǎng)絡分析法需要決策者對目標的重要性進行兩兩比較,實質上是一種主觀賦權法,因此考慮在其基礎上引入熵權概念,綜合考慮主觀性和客觀性。

ANP法和層次分析法 (AHP)在大致步驟上是相同的,它們的基本思想都是逐層歸納、先分后總地解決復雜問題[14-15],不同的是ANP法還需在判斷矩陣被接受后,建立加權超矩陣并取冪計算直到矩陣收斂,得到極限超矩陣,最終得到權重Vj(j=1,2,3)。

熵權法是一種客觀賦權方法,它利用信息熵理論,根據(jù)各目標的變異程度計算其熵權,熵權大小本質上由目標間的差異大小所決定,通過熵權修正各目標的權重,從而對專家打分進行客觀賦權[16],根據(jù)信息熵,各項目標的權重Hj可以表示為式(27):

(27)

式中:n表示目標數(shù)量,即n=1,2,3。

Vj和Hj具有差異性,其各自對建立的評價體系又具有不同的影響,考慮將兩者耦合起來[16-18],形成修正賦權組合式(28):

(28)

Wj兼顧了主觀和客觀因素,結合了ANP和熵權法兩種方法的優(yōu)點,使得目標函數(shù)里各目標的權重更加準確合理。

利用相對百分比偏差(relative percentage deviation,RPD)來評價算法對比實驗的結果,RPD值越小表示算法的性能越好,相對百分偏差由式(29)表示:

(29)

式中:φsome表示某個案例在給定算法下在一次運行中解的適應度值,φbest表示某個案例在所有算法下多次求解的最好解的適應度值。

最小相對百分偏差值(MinRPD)和平均相對百分偏差值(AvgRPD)的計算公式由式(30)和式(31)表示:

(30)

(31)

式中:φmin表示某個案例在給定情形下運行20次中求解的最小適應度值,φavg表示某個案例在給定情形下運行20次中求解的平均適應度值,其中,若算法得到的MinRPD和AvgRPD越小,則表示算法的性能越好。

4.2 改進算子性能分析

為證明所提算子改進策略有效,設計對比實驗依次進行交叉、變異、位移、變向算子性能分析,包括離散粒子群算法(DPSO)、僅帶交叉算子的離散粒子群算法(DPSO-C)、僅帶變異算子的離散粒子群算法(DPSO-M)、僅帶位移算子的離散粒子群算法(DPSO-D)、僅帶變向算子的離散粒子群算法(DPSO-T)與所提的帶有4種算子的改進離散粒子群算法(IDPSO)。實驗運行時間相同并設置為N×N×10 s,N表示各案例的拆卸任務總數(shù),12個案例在上述6種情形下各運行20次得到的結果如圖2所示。

(a) MinRPD (b) AvgRPD

從圖2a和圖2b可知,未改進的DPSO算法在實驗運行中求得的MinRPD值和AvgRPD值普遍偏大,求解結果明顯不夠穩(wěn)定,優(yōu)越性不好。分別引入交叉、變異、位移、變向算子后所求得的MinRPD值和AvgRPD明顯減小,但算法穩(wěn)定性欠佳。但當同時引入各算子后,所求解的MinRPD值和AvgRPD值明顯減小,算法穩(wěn)定性和求解性能得到明顯改善,證明所提算子改進策略有效。

4.3 算法性能分析

為更好地分析所提算法的綜合性能,將所提算法IDPSO與DPSO、GA以及IDBA進行對比實驗,在不同算法下將12個案例在相同時間內(nèi)分別運行20次,得到的結果如圖3所示。

(a) MinRPD (b) AvgRPD

從圖3a和圖3b可知,所提算法IDPSO求得的MinRPD值和AvgRPD值明顯優(yōu)于其他3種算法,說明相較于對比算法,IDPSO算法求解結果更好,算法求解穩(wěn)定性更好。綜合圖2和圖3分析可知,在相同的運行時間下,IDPSO算法的綜合性能更優(yōu)。

4.4 工程實例結果分析

為驗證文章所提方法的有效性,在相同時間用不同算法在AHP、ANP、熵權法、AHP-熵權法和ANP-熵權法5種賦權法下運行20次輸出最優(yōu)拆卸方案,以案例2為例,結果如表4所示,“(9-14)”表示拆卸任務“9、14”在同一個工作站;“目標值/適應度值”一欄數(shù)值依次為3個目標值和適應度值。

表4 對比實驗中案例2的拆卸結果展示

就算法而言,從表4可知,在相同的時間限制和實驗條件下,無論采用哪種賦權法,IDPSO相比其他算法的求解質量更高,依次為IDBA和DPSO,而GA求解質量最差,盡管IDBA也能找到比較好的解,但穩(wěn)定性較IDPSO較差。同時,IDPSO均能找到最優(yōu)的工作站數(shù)量為8,求解到最短的工作站最大作業(yè)時間為15.333 3 s,說明給定案例2的節(jié)拍時間22 s可以優(yōu)化至15.333 3 s,從而減小平滑指數(shù)和適應度值。

就賦權法而言,不同方法下優(yōu)化目標的權重不同,就會影響解的質量。相同算法中,AHP法下的適應度值最小,這可能是目標一的值小而權重相對較大造成的,但該方法并未考慮目標之間的相關關系。相較于此,ANP法考慮到目標之間是相互影響的,更適用于所研究的組合優(yōu)化問題,但由于該方法更主觀,因此考慮將熵權法與之耦合,可以看到ANP-熵權法下的求解質量也是比較好的?？偟膩碚f,采用不同評估方法得到的評價結果是不一樣的,在實際拆卸過程中,優(yōu)化目標的選擇應適合現(xiàn)場情況,才能達到解決實際拆卸難點的目的。經(jīng)過完備的對比實驗,驗證了所提方法可以有效地求解所提優(yōu)化問題。

5 結束語

為解決人工拆卸效率低下和拆卸成本高等問題,考慮用機器人進行廢舊品拆卸,在當前研究的基礎上,進一步考慮拆卸任務間的交互對拆卸順序及拆卸作業(yè)時間的影響。根據(jù)問題特征構建多目標優(yōu)化模型,提出ANP-熵權法建立耦合的定量評價模型,合理地量化目標權重,為下一步求解提供依據(jù)。同時設計一種改進離散粒子群算法來求解,該算法重構了粒子速度和位置更新公式,引入遺傳算法中的交叉和變異算子彌補了粒子群算法全局尋優(yōu)能力較差的缺點,并為契合問題本質還設計了位移和變向改進算子。為驗證ANP-熵權法的合理性,設計對比實驗與其他方法對比,實驗表明該方法在綜合考慮了主觀性和客觀性后得到了更為準確的權重,基于此求解的優(yōu)化方案貼合實際拆卸生產(chǎn),也能得到較好的應用。為驗證所提算法的性能,將其與遺傳算法、離散粒子群算法及改進離散蜂群算法對比,實驗表明,所提算法相比其他3種算法可有效求解所提問題,具有明顯的性能優(yōu)勢。綜上所述,本文研究方法可行且具有應用價值,為優(yōu)化拆卸線的生產(chǎn)提供了新的解決思路。