考慮不確定性條件的退役產(chǎn)品拆解柔性調(diào)度

馬新一，匡增彧，卓曉軍，任瑩暉

(1.湖南大學(xué) 機(jī)械與運(yùn)載工程學(xué)院，湖南 長沙 410082；2.長沙礦冶研究院有限責(zé)任公司，湖南 長沙 410012；3.同濟(jì)大學(xué) 機(jī)械與能源工程學(xué)院，上海 201804)

隨著我國經(jīng)濟(jì)和科技的發(fā)展，3C電子產(chǎn)品和新能源汽車等新興消費(fèi)品快速更新迭代，此類產(chǎn)品退役給環(huán)境保護(hù)、戰(zhàn)略礦產(chǎn)資源需求和產(chǎn)業(yè)可持續(xù)發(fā)展帶來巨大壓力[1]。為實(shí)現(xiàn)我國“3060”雙碳戰(zhàn)略目標(biāo)，促進(jìn)環(huán)境和產(chǎn)業(yè)的可持續(xù)發(fā)展，梯次利用和資源化成為此類退役產(chǎn)品最佳的循環(huán)再利用方式[2-4]。但回收的退役產(chǎn)品來源復(fù)雜、品類和結(jié)構(gòu)多樣、性能殘值不一，造成其循環(huán)再利用前的回收拆解深度、拆解序列和拆解方法不確定，導(dǎo)致回收拆解逆向生產(chǎn)調(diào)度受到諸多不確定性擾動(dòng)因素影響[5]。

現(xiàn)階段，我國退役產(chǎn)品回收拆解企業(yè)普遍存在生產(chǎn)自動(dòng)化程度低、手工作業(yè)占比大、依賴人工經(jīng)驗(yàn)排程等現(xiàn)狀[5]。造成退役產(chǎn)品的拆解破損良率低、生產(chǎn)資源調(diào)度和拆解物料管控困難、存在環(huán)境污染和生產(chǎn)安全等瓶頸問題，影響了退役產(chǎn)品循環(huán)再利用的經(jīng)濟(jì)性[6]。為解決上述問題，考慮新興消費(fèi)產(chǎn)品內(nèi)部結(jié)構(gòu)同質(zhì)化發(fā)展趨勢，柔性工裝拆解工作站逐漸成為退役產(chǎn)品大規(guī)模自動(dòng)化拆解線的發(fā)展趨勢。在考慮退役產(chǎn)品多源異構(gòu)不確定性擾動(dòng)因素條件下，如何構(gòu)建退役產(chǎn)品拆解線生產(chǎn)的調(diào)度策略與模型，提升退役產(chǎn)品大規(guī)模自動(dòng)化拆解線動(dòng)態(tài)調(diào)度的平穩(wěn)性，成為了回收拆解逆向生產(chǎn)亟待解決的關(guān)鍵問題。

對于傳統(tǒng)的離散制造正向生產(chǎn)而言，常采用網(wǎng)絡(luò)模型和參數(shù)假設(shè)等描述不確定生產(chǎn)工藝流程和工時(shí)節(jié)拍，構(gòu)建不確定條件生產(chǎn)調(diào)度模型。例如，Tao等[7]利用AND/OR網(wǎng)絡(luò)描述柔性車間中設(shè)備選擇和工藝流程不確定問題。Zhang等[8]利用基于圖的約束規(guī)劃求解集成式工藝規(guī)劃與車間調(diào)度問題。蔣勝龍等[9]針對加工時(shí)間不確定的煉鋼—連鑄調(diào)度，構(gòu)建基于有向網(wǎng)絡(luò)圖的柔性調(diào)度模型。Amiri等[10]將具有不確定性的加工時(shí)長假設(shè)為隨機(jī)且服從正態(tài)分布。正向生產(chǎn)多關(guān)注于加工時(shí)長或工藝流程等單一不確定性因素。而對于具有多源異構(gòu)不確定性特性的退役產(chǎn)品回收拆解逆向生產(chǎn)而言，品類、結(jié)構(gòu)、性能殘值和拆解方式等不確定性擾動(dòng)因素，通過對拆解深度、拆解序列和拆解方式的綜合影響，轉(zhuǎn)化為對拆解線生產(chǎn)資源組合和完成時(shí)間的動(dòng)態(tài)擾動(dòng)。因此，不確定性擾動(dòng)因素對退役產(chǎn)品拆解線生產(chǎn)調(diào)度的動(dòng)態(tài)平穩(wěn)性影響更為復(fù)雜。

此外，柔性工裝拆解工作站類自動(dòng)化拆解線生產(chǎn)調(diào)度側(cè)重生產(chǎn)資源的組合優(yōu)化，具有典型NPhard問題屬性。遺傳算法、粒子群算法等是典型NP-hard問題求解常用智能算法。例如，姜天華[11]以生產(chǎn)市場最短和能耗最小為目標(biāo)建立柔性作業(yè)車間進(jìn)行生產(chǎn)調(diào)度模型，并采用灰狼優(yōu)化算法求解。Liu等[12]為克服遺傳算法準(zhǔn)確性低的問題，提出可變鄰域下降混合遺傳算法 (VND-hGA)，設(shè)計(jì)基于粒子群算法的遺傳算子用于解決柔性車間調(diào)度問題。張曉星等[13]利用融合單親遺傳算法基因變異操作的改進(jìn)混合蛙跳算法求解柔性車間調(diào)度問題。在現(xiàn)有求解NP-hard問題的諸多智能算法中，遺傳算法與模擬退火等算法結(jié)合可以提高算法全局搜索能力，在生產(chǎn)調(diào)度等組合優(yōu)化問題中證明了其有效性[14-16]，更適合于不確定性條件下退役產(chǎn)品拆解線生產(chǎn)調(diào)度問題。

本文以退役動(dòng)力電池回收拆解逆向生產(chǎn)為例，展開考慮不確定性因素的退役產(chǎn)品柔性拆解生產(chǎn)動(dòng)態(tài)調(diào)度問題研究。構(gòu)建基于AND/OR網(wǎng)絡(luò)結(jié)構(gòu)的退役產(chǎn)品柔性拆解線混合整數(shù)規(guī)劃調(diào)度模型，改進(jìn)融合單親遺傳和模擬退火機(jī)制的智能算法，最后實(shí)例驗(yàn)證模型和算法的可行性。

1 問題描述與建模

1.1 問題描述

本文研究采用柔性工裝拆解工作站的退役產(chǎn)品拆解線生產(chǎn)調(diào)度問題，該問題描述如下。某批次中有k件退役工件J={J1,J2,···,Jk} 需要在mk臺設(shè)備M={M1,M2,···,Mmk}上 進(jìn)行拆解。每臺設(shè)備Mm配有mf件配套夾具，夾具切換時(shí)間為Tm。每個(gè)工件Ji的拆解序列中有ni道工序Oi={Oi1,Oi2,···,Oini}。拆解序列中可能有多條可選的工藝路線，拆解時(shí)只能從中選擇一條進(jìn)行拆解，且拆解過程必須遵守工序緊前緊后關(guān)系。每道工序Oij都有一個(gè)拆解資源集Mij={Mij1,Mij2,···,}，資源集中元素表示一種設(shè)備和夾具的組合方式。拆解時(shí)可以從拆解資源集中選擇任意一種組合方式。退役產(chǎn)品拆解線生產(chǎn)調(diào)度以拆解時(shí)長最短為目標(biāo)，模型建立前作出如下假設(shè)。

1) 所有設(shè)備在開始時(shí)刻都沒有安裝夾具，必須在安裝相應(yīng)夾具后才可以進(jìn)行加工；

2) 每臺設(shè)備某一時(shí)刻只能拆解一道工序，拆解過程不可中斷；

3) 對任意設(shè)備，若前后兩道工序的夾具不同，則需要計(jì)算夾具切換時(shí)間，否則無需切換夾具，可以連續(xù)加工；

4) 忽略工件在各工作站運(yùn)輸?shù)臅r(shí)間，工件可以在各個(gè)工作站之間運(yùn)輸；

5) 不考慮能源消耗、成本約束等其他條件。

1.2 模型構(gòu)建

1.2.1 AND/OR調(diào)度策略模型

為表示退役產(chǎn)品不確定的拆解深度和不確定的拆解線工藝路線等生產(chǎn)調(diào)度擾動(dòng)因素，構(gòu)建如圖1所示的AND/OR節(jié)點(diǎn)網(wǎng)絡(luò)調(diào)度策略模型。

圖1 AND/OR節(jié)點(diǎn)網(wǎng)絡(luò)示意圖Figure 1 Diagram of an AND/OR node network

定義1節(jié)點(diǎn)。圖1中用N={0,1,2,···,n+1}表示節(jié)點(diǎn)，節(jié)點(diǎn)代表工序。其中，0和n+1節(jié)點(diǎn)為虛擬節(jié)點(diǎn)，分別表示起始節(jié)點(diǎn)和終結(jié)節(jié)點(diǎn)。批次中每款退役工件拆解序列都從0節(jié)點(diǎn)出發(fā)，到n+1節(jié)點(diǎn)結(jié)束。0節(jié)點(diǎn)后多條退役工件拆解序列體現(xiàn)來料品類的不確定性。

定義2AND節(jié)點(diǎn)。圖1中無陰影的節(jié)點(diǎn)表示AND節(jié)點(diǎn)。若選擇AND節(jié)點(diǎn)代表工序，則該節(jié)點(diǎn)所有緊后節(jié)點(diǎn)工序都必須被選擇。特別規(guī)定 0節(jié)點(diǎn)和n+1節(jié)點(diǎn)為AND節(jié)點(diǎn)。

定義3OR節(jié)點(diǎn)。圖1中灰色陰影節(jié)點(diǎn)表示OR節(jié)點(diǎn)。若選擇OR節(jié)點(diǎn)代表工序，則該節(jié)點(diǎn)所有緊后節(jié)點(diǎn)工序中僅能選擇一個(gè)進(jìn)行加工。

定義4可選活動(dòng)鏈。用 CH 表示退役產(chǎn)品拆解序列中可選的工藝路線，如圖1的AND/OR模型，CH1={{3,4,5,6,7},{8,9,10}}，CH2={{4,5},{6}}，CH3={{14},{15}}可分別表示為3組可選活動(dòng)鏈。

AND/OR網(wǎng)絡(luò)的可選活動(dòng)鏈構(gòu)成具有樹狀結(jié)構(gòu)層級關(guān)系，如圖2所示。AND/OR節(jié)點(diǎn)網(wǎng)絡(luò)圖的可選活動(dòng)鏈均可繪制成至少3層的樹狀結(jié)構(gòu)圖。第1層表示所有位于可選活動(dòng)鏈中的節(jié)點(diǎn)集合；第2層表示互相獨(dú)立的可選活動(dòng)鏈集合；從第3層開始則是各個(gè)可選活動(dòng)鏈集合的活動(dòng)鏈子集，用于表示各活動(dòng)鏈的包含關(guān)系。

圖2 可選活動(dòng)鏈樹狀結(jié)構(gòu)示例Figure 2 The tree structure of an optional activity chain

1.2.2 基于AND/OR節(jié)點(diǎn)網(wǎng)絡(luò)的拆解調(diào)度模型

1) 索引與參數(shù)。

i、j為工序索引，i,j∈{0,1,2,···,n,n+1}，n為退役產(chǎn)品拆解工序總數(shù)；m為拆解設(shè)備索引，m∈{1,2,···,mk}，mk為設(shè)備總數(shù)；f為夾具索引，f∈{1,2,···,mf}，mf為設(shè)備Mm的配套夾具數(shù)，需與設(shè)備索引聯(lián)合使用；t為時(shí)刻索引，t∈Γ={0,1,2,···}，Γ 為時(shí)刻集 合；Aij為工序緊前關(guān)系 參數(shù)，0-1變量，若i是j緊前工序則為1，否則為0；γi為節(jié)點(diǎn)性質(zhì)參數(shù)，0-1變量，若i節(jié)點(diǎn)是AND節(jié)點(diǎn)則為1，否則為0；Tm為設(shè)備Mm切換夾具所需的時(shí)間；Di,m,f為工序i使用機(jī)器Mm上夾具f的拆解時(shí)間；?為充分大的實(shí)數(shù)。

2) 決策變量。

xi為工序選擇變量，0-1變量，若工序i被選中則為1，否則為0；yi,t為工序完成時(shí)刻變量，0-1變量，若工序i在t時(shí)刻完成則為1，否則為0；zi,m,f為設(shè)備夾具選擇變量，0-1變量，若工序i使用機(jī)器Mm上夾具f則為1，否則為0；Bm,i,j為機(jī)器工序順序判定變量，0-1變量，對機(jī)器Mm，若工序i是j緊前工序則為1，否則為0；Cm,i,j為機(jī)器工序夾具判定規(guī)則，0-1變量，對機(jī)器Mm，若工序i和j夾具不同則為1，否則為0。

3) 目標(biāo)函數(shù)。

以退役產(chǎn)品回收拆解最短完工時(shí)長為調(diào)度優(yōu)化目標(biāo)。

4) 約束條件。

其中，式(2) 為工序拆解方式選擇約束；式 (3)為工序拆解次數(shù)約束；式 (4) 為AND和OR節(jié)點(diǎn)性質(zhì)約束；式 (5) 為各工件拆解順序約束；式 (6) 為機(jī)器操作時(shí)間約束，考慮夾具切換的時(shí)間；式 (7) 表示設(shè)備初始時(shí)刻必須先裝載夾具再進(jìn)行第1道工序加工；式 (8) 和式 (9) 為Bm,i,j和Cm,i,j變量描述，當(dāng)工序選擇變量xi、完成時(shí)刻變量yi,t、設(shè)備夾具選擇變量zi,m,f和拆解時(shí)長參數(shù)Di,m,f確定時(shí)，Bm,i,j和Cm,i,j變量的值也唯一確定。

2 算法設(shè)計(jì)

考慮到AND/OR節(jié)點(diǎn)網(wǎng)絡(luò)的編碼方式，若通過標(biāo)準(zhǔn)遺傳算法中2個(gè)父代交叉獲得子代，容易違反工序緊前緊后關(guān)系而生成非可行調(diào)度方案。單親遺傳算法 (partheno-genetic algorithm，PGA) 具有與標(biāo)準(zhǔn)遺傳算法類似的進(jìn)化機(jī)制，去除了標(biāo)準(zhǔn)遺傳算法中的交叉算子，具有全局收斂性[17]，可用于解決組合調(diào)度優(yōu)化問題[18]。與標(biāo)準(zhǔn)遺傳算法類似，單親遺傳算法同樣具有易陷入局部最優(yōu)的缺陷。因此本文融合模擬退火算 法 (simulated annealing，SA) 機(jī)制，提出模擬退火單親遺傳算法 (SA-PGA) 求解基于AND/OR節(jié)點(diǎn)網(wǎng)絡(luò)的拆解調(diào)度模型。其算法流程如圖3所示。其中，α為溫變系數(shù)，CT為當(dāng)前溫度，TEMPf為外循環(huán)最高溫度，Gen為當(dāng)前迭代次數(shù)，L為內(nèi)循環(huán)最大迭代次數(shù)。在選擇個(gè)體變異時(shí)引入SA機(jī)制，以一定概率接受較差解進(jìn)行變異，提高算法全局搜索能力。

圖3 算法流程Figure 3 Flow chart of the algorithm

2.1 編碼設(shè)計(jì)

由于退役產(chǎn)品的多源異構(gòu)特性，拆解時(shí)需要先針對不確定的拆解深度和拆解序列進(jìn)行工序選擇和排序，再對每道工序不確定的拆解方法進(jìn)行設(shè)備和夾具選擇。因此，需構(gòu)建如圖4所示的四子串實(shí)數(shù)編碼。第1層為工序?qū)?，首尾分別為初始節(jié)點(diǎn)和終節(jié)點(diǎn)，中間節(jié)點(diǎn)表示工序的加工順序，需符合緊前關(guān)系約束。第2層為選擇層，編碼表示對應(yīng)第1層工序的選擇與否，規(guī)定初始節(jié)點(diǎn)和終節(jié)點(diǎn)都被選擇。第3層和第4層分別為設(shè)備層和夾具層，表示被選擇節(jié)點(diǎn)所代表的工序的加工設(shè)備和夾具，未被選擇的節(jié)點(diǎn)、初始節(jié)點(diǎn)和終節(jié)點(diǎn)則無需選擇設(shè)備夾具組合，該處基因編碼為0。

圖4 四子串實(shí)數(shù)編碼示例Figure 4 An example of four substring real number coding

2.2 遺傳算子

單親遺傳算法的遺傳算子可以分為基因重組算子和基因突變算子兩大類，其中基因重組算子是指基因的位移或換位。本問題的四子串編碼中工序和選擇層的遺傳變異，也將采用基因重組算子與基因突變算子進(jìn)行變異。本文設(shè)計(jì)的基因重組算子包括循環(huán)位移算子，基因突變算子包括選擇變異算子和設(shè)備夾具變異算子。變異流程如圖5所示。當(dāng)隨機(jī)選擇節(jié)點(diǎn)代表的工序被選擇的時(shí)候，則采用循環(huán)位移算子進(jìn)行變異操作。循環(huán)位移算子的作用是在符合工序緊前關(guān)系的前提下，將被選中的節(jié)點(diǎn)放到其緊前工序和緊后工序之間的新位置，改變工序的操作順序。圖6為循環(huán)位移算子示例，隨機(jī)選擇節(jié)點(diǎn)6進(jìn)行移動(dòng)，記錄下其坐標(biāo)值最大的緊前工序和坐標(biāo)值最小的緊后工序坐標(biāo)，即節(jié)點(diǎn)7和節(jié)點(diǎn)10的坐標(biāo)，并從兩者之間隨機(jī)挑選一個(gè)坐標(biāo)成為6節(jié)點(diǎn)新的位置，其他節(jié)點(diǎn)順位移動(dòng)。

圖5 個(gè)體變異流程Figure 5 Individual mutation process

圖6 循環(huán)位移算子Figure 6 Cyclic shift operator

當(dāng)隨機(jī)選擇節(jié)點(diǎn)代表的工序未被加工時(shí)采用選擇變異算子。如圖7所示，已知被選中的節(jié)點(diǎn)3和節(jié)點(diǎn)8位于同一條未被選擇的活動(dòng)鏈中，且與節(jié)點(diǎn)6在同一可選活動(dòng)鏈集合中，則選擇位移算子就會(huì)選中節(jié)點(diǎn)3和節(jié)點(diǎn)8所在的活動(dòng)鏈，實(shí)現(xiàn)加工工序的改變。在可選活動(dòng)鏈樹狀結(jié)構(gòu)中，選擇變異算子將按照等級從高到低逐級對活動(dòng)鏈進(jìn)行選擇，直到最底層活動(dòng)鏈被選擇為止。實(shí)現(xiàn)選擇鏈變換后，對新選中的節(jié)點(diǎn)隨機(jī)分配設(shè)備和夾具。當(dāng)工序?qū)雍瓦x擇層的循環(huán)位移算子和選擇變異算子執(zhí)行后，采用多點(diǎn)變異方式對設(shè)備和夾具進(jìn)行變異。

圖7 選擇變異算子Figure 7 Mutation operator of selection

2.3 模擬退火機(jī)制

傳統(tǒng)的遺傳算法多采用輪盤賭方式選擇個(gè)體，容易導(dǎo)致優(yōu)秀個(gè)體流失。在單親遺傳算法中引入模擬退火機(jī)制，可以一定概率接受較差的解，有效防止算法出現(xiàn)“早熟”現(xiàn)象而陷入局部最優(yōu)。本文采用二元錦標(biāo)賽融合模擬退火的方式選擇個(gè)體進(jìn)行變異操作。

1) 采用輪盤賭方式在種群中選擇兩個(gè)個(gè)體ind1和ind2，計(jì)算其完工時(shí)長分別為 Fit(ind1)和Fit(ind2)。

2) 依據(jù)模擬退火中Metropolis準(zhǔn)則接受個(gè)體，若Fit(ind1)

3) 重復(fù)1)、2)，直到新種群中個(gè)體數(shù)量與原種群相同。

3 實(shí)例驗(yàn)證

以某企業(yè)退役動(dòng)力電池的回收拆解為例，驗(yàn)證柔性拆解線動(dòng)態(tài)調(diào)度策略和模型的可行性。新能源車常用的動(dòng)力電池類型包括磷酸鐵鋰電池、錳酸鋰電池、鎳氫和三元材料電池等。傳統(tǒng)動(dòng)力電池具有電芯-模組-電池包三級結(jié)構(gòu)，新型動(dòng)力電池朝無模組、集成化結(jié)構(gòu)化創(chuàng)新。在電芯層面又有刀片電池和大圓柱電池的區(qū)別。由于動(dòng)力電池退役后仍有70%容量可用于梯次利用，且動(dòng)力電池包含鎳、鈷、錳等重金屬元素可資源化再利用，有助于節(jié)省動(dòng)力電池上游貴金屬資源消耗。因此，回收的退役動(dòng)力電池從來源、類型、結(jié)構(gòu)和性能殘值等方面都存在不確定性。

退役動(dòng)力電池類型和結(jié)構(gòu)的不確定將影響拆解序列的不確定，導(dǎo)致拆解方法和拆解動(dòng)作順序不確定。其性能殘值的不確定，將影響循環(huán)再利用流向的不確定，導(dǎo)致拆解深度和拆解序列的不確定。外觀結(jié)構(gòu)的完好和破損情況，也會(huì)影響選擇手工或機(jī)器拆解方式的不確定，導(dǎo)致拆解時(shí)間變動(dòng)帶來總完工時(shí)間的不確定。本文選取某公司的退役動(dòng)力電池回收拆解柔性線為例，考慮拆解深度、拆解序列和拆解方法為不確定性擾動(dòng)因素，與單親遺傳算法相比較驗(yàn)證本文改進(jìn)的模擬退火單親遺傳算法的有效性，與現(xiàn)階段廣泛采用的調(diào)度員手工調(diào)度比較，驗(yàn)證本文構(gòu)建的拆解調(diào)度模型實(shí)用性。

3.1 實(shí)例數(shù)據(jù)與參數(shù)設(shè)置

選擇包含兩款三元?jiǎng)恿﹄姵?(三元01、三元02)和一款鎳氫動(dòng)力電池 (鎳氫01) 的拆解批次。拆解線中設(shè)備和工位信息匯總?cè)绫?所示。設(shè)置龍門吊負(fù)責(zé)電池包和模組的上下線。漏電檢測、掃碼、手動(dòng)維護(hù)開關(guān)、拆安全包開關(guān)、放電等難以使用機(jī)器操作的工序采用人工處理。設(shè)置了2臺帶視覺識別功能的拆解機(jī)器人工位，負(fù)責(zé)拆解螺母、螺栓類緊固件?？紤]拆解安全性，由人工工位負(fù)責(zé)拆解可能存在內(nèi)部結(jié)構(gòu)破損或變形的退役動(dòng)力電池。表2～ 4分別列出了實(shí)例中3款動(dòng)力電池各工序所需的拆解設(shè)備、夾具以及相應(yīng)工序時(shí)間信息。部分工序的前序工序和后續(xù)工序相同，如三元01的工序6、7、8和工序15、16，表示該些工序順序可互換，無緊前緊后約束。在調(diào)度過程中，需要合理配置各個(gè)工序的設(shè)備和夾具，合理安排各工序的操作順序。與定工序調(diào)度相比，相互之間沒有緊前緊后關(guān)系的工序，拆解調(diào)度復(fù)雜度會(huì)更高。

表1 拆解線設(shè)備工位信息表Table 1 The station information of disassembly line equipments

表2 三元01拆解工序信息表Table 2 Disassembly sequences of ternary power battery 01

表3 三元02拆解工序信息表Table 3 Disassembly sequences of ternary power battery 02

表4 鎳氫01拆解工序信息表Table 4 Disassembly sequences of Ni-MH power battery 01

當(dāng)前，采用調(diào)度員手工排程隨機(jī)調(diào)度，沒有固定的調(diào)度規(guī)則和調(diào)度算法。本文采用在遵守設(shè)備拆解緊前緊后約束的條件下隨機(jī)生成調(diào)度方案的形式描述當(dāng)前的手工排程調(diào)度方法。為減少偶然性，測試50次得到調(diào)度方案平均拆解時(shí)長。再根據(jù)拆解線基礎(chǔ)數(shù)據(jù) (見表2～ 4) 繪制調(diào)度策略AND/OR節(jié)點(diǎn)網(wǎng)絡(luò)模型圖，并采用PGA算法和SA-PGA算法求解。設(shè)置PGA算法和SA-PGA算法參數(shù)，設(shè)備變異率Pm=0.1，工序變異 率Pc=0.1，種群 數(shù)N=40，SA-PGA內(nèi)循環(huán)迭代次數(shù)L=40，初始溫度 TEMP=120?C，終溫T EMPf=1?C，溫變系數(shù)α=0.95。

3.2 優(yōu)化結(jié)果分析

結(jié)果表明，模擬調(diào)度員手工調(diào)度的50次試驗(yàn)中，最大完工時(shí)長為18 020 s，最短完工時(shí)長為10 710 s，平均完工時(shí)長13 829.8 s，極差為7 310 s，方差為2 875 973 s2。本文調(diào)度模型PGA算法和SAPGA算法求解運(yùn)行的迭代曲線如圖8所示。由圖8可知，PGA算法尋得最優(yōu)方案的完工時(shí)長為9 860 s，劣于SA-PGA算法尋得的9 765 s的調(diào)度方案。說明SA-PGA算法繼承了PGA算法收斂速度快的優(yōu)點(diǎn)，同時(shí)也能夠跳出局部最優(yōu)。

圖8 PGA與SA-PGA迭代曲線Figure 8 Iterative curves of PGA and SA-PGA

基于SA-PGA算法的50次測試中，迭代完成后種群中最長完工時(shí)間為10 365 s，最短完工時(shí)長為9 765 s，平均完工時(shí)長為9 829.3 s，極差為600 s，方差為19 750 s2。與手動(dòng)調(diào)度相比，采用AND/OR節(jié)點(diǎn)模型和優(yōu)化算法后，調(diào)度結(jié)果的方差和極差明顯減小，調(diào)度波動(dòng)更小，且完工時(shí)長明顯縮短，平均完工時(shí)長縮短27.4%，說明了調(diào)度模型的有效性和魯棒性。

對比優(yōu)化前后調(diào)度方案甘特圖，手工排程完工時(shí)長為16 775 s時(shí)的調(diào)度方案如圖9 (a)，采用本文提出調(diào)度模型及改進(jìn)算法獲得的完工時(shí)長為9 765 s的調(diào)度方案如圖9 (b)，兩種調(diào)度方法相關(guān)結(jié)果如表5所示。結(jié)合圖9與表5可知，采用優(yōu)化算法后，設(shè)備利用率更加均衡。例如，優(yōu)化后用于相同拆螺母工序的視覺識別機(jī)器人2的設(shè)備5和設(shè)備6分別工作了2 150 s和1 540 s，而優(yōu)化前采用手工調(diào)度方式時(shí)設(shè)備5僅工作250 s，遠(yuǎn)小于設(shè)備6的 2 320 s，存在利用率低的問題。優(yōu)化前后夾具切換次數(shù)由25次減少到20次，夾具切換時(shí)長由4 350 s縮短至3 350 s，減少了時(shí)間浪費(fèi)。

表5 優(yōu)化前后調(diào)度方案數(shù)據(jù)匯總表Table 5 Data of dispatching schemes before and after optimization

圖9 優(yōu)化前后調(diào)度方案甘特圖和圖例Figure 9 Gantt chart of scheduling schemes before and after optimization

在該拆解線中，表示人工拆解螺栓和螺母的設(shè)備4、7和8，主要負(fù)責(zé)破損嚴(yán)重?zé)o法使用機(jī)器拆解的工序，以及機(jī)器被占用時(shí)的手工拆解。當(dāng)電池部件破損較輕可以使用機(jī)器拆解時(shí)，人工拆解工位與代表視覺識別機(jī)器人的設(shè)備3、5和6存在可相互替代的關(guān)系。由于電池結(jié)構(gòu)復(fù)雜和工人操作熟練度等因素，使人工拆解相比視覺識別機(jī)器人拆解時(shí)長較長。傳統(tǒng)手工調(diào)度難以平衡機(jī)器和人工的工作負(fù)荷，容易產(chǎn)生機(jī)器閑置率高的問題。采用優(yōu)化算法后，表示人工工位的設(shè)備4、7和8拆解時(shí)長由7 345 s減少至4 870 s，代表視覺識別機(jī)器人的設(shè)備3、5和6拆解時(shí)長由3 930 s增加至6 050 s。機(jī)器工作時(shí)長在所有工位工作時(shí)長占比由44.4%提高到69.9%。由機(jī)器代替手工拆解，提高了拆解線的拆解效率和自動(dòng)化利用程度。

4 結(jié)論

針對不確定條件下的退役產(chǎn)品柔性拆解動(dòng)態(tài)調(diào)度問題，構(gòu)建基于AND/OR節(jié)點(diǎn)網(wǎng)絡(luò)退役產(chǎn)品拆解調(diào)度模型。設(shè)計(jì)了四子串編碼規(guī)則和循環(huán)位移、變異選擇和設(shè)備夾具變異3種遺傳算子，提出將模擬退火機(jī)制與單親遺傳算法融合的SA-PGA算法求解調(diào)度問題。

在實(shí)例驗(yàn)證中，與模擬手工排程的隨機(jī)調(diào)度相比，本文提出的調(diào)度方案完工時(shí)長縮短27.4%，自動(dòng)化率提高25.2%。設(shè)備的工作負(fù)荷得到平衡，夾具切換造成的時(shí)間浪費(fèi)縮短，實(shí)例驗(yàn)證調(diào)度方法具有可行性。在來料品類、拆解序列和拆解方式等不確定擾動(dòng)因素影響下，多次調(diào)度的完工時(shí)長方差減小。本文提出的調(diào)度模型有助于減小不確定性擾動(dòng)因素對拆解調(diào)度的影響，具有魯棒性，實(shí)現(xiàn)對柔性拆解設(shè)備和夾具的動(dòng)態(tài)優(yōu)化配置。

在建立調(diào)度模型時(shí)未考慮資源約束、工件運(yùn)輸時(shí)長等因素，因此綜合考慮車間中其他因素對調(diào)度產(chǎn)生影響將是下一步研究的重點(diǎn)。未來可考慮將AND/OR節(jié)點(diǎn)調(diào)度方法集成到 MES 系統(tǒng)中，在拆解前輸入相關(guān)基礎(chǔ)數(shù)據(jù)，對拆解提供調(diào)度方案指導(dǎo)。