摘要：因拆卸時間受操作者技能熟練程度、產品自身結構以及組成材料變化等多方面影響而存在不確定性的問題，基于灰數提出不確定拆卸時間的異步并行拆卸序列規劃方法。在考慮拆卸最大規定時間約束、工作站先后順序以及并行拆卸序列執行長度等約束條件的基礎上建立最大拆卸收益與最小拆卸時間為目標的數學模型，提出一種改進人工蜂群算法。用矩陣編碼構造可行解并使用錦標賽選擇替代輪盤賭，在偵查蜂階段設計一種基于潛能值的更新策略，提出一種新型的協同對比方法獲得非劣解。通過算法對比驗證改進算法的可行性，最后由筆記本電腦的拆卸實例來驗證優化模型的有效性，實驗結果表明：異步并行拆卸的經濟效益提升了23.1%，拆卸時間縮短了12.7%。

　　關鍵詞：異步并行拆卸序列規劃;灰數;不確定性;改進人工蜂群算法

　　論文《考慮不確定拆卸時間的異步并行拆卸序列規劃》發表在《福建理工大學學報》，版權歸《福建理工大學學報》所有。本文來自網絡平臺，僅供參考。

　　拆卸是回收再制造的關鍵環節，拆卸序列規劃(disassembly sequence planning, DSP)是指按照產品零部件的結構約束，探索可行的拆卸序列并找到最優拆卸順序的過程，對拆卸效率和收益的提升具有重要意義。

　　自GUNGOR首次提出有關拆卸問題以來，國內外學者已對同步并行拆卸規劃問題進行了研究。而目前拆卸研究的對象基本為大型復雜機電產品，對拆卸時間的要求逐漸提高，異步并行拆卸序列規劃問題逐漸成為研究的熱點。邢世雄等提出了一種改進蝙蝠算法的方法來研究拆卸序列規劃問題。郭鈞等提出了一種考慮不確定拆卸程度的選擇性異步并行拆卸序列規劃方法。孫嫻靜等在異步并行拆卸的基礎上考慮了優先關系約束和機器工作區域沖突約束的異步并行拆卸序列規劃問題。張雷等通過多個優化目標進行分析，提出一種基于環形拓撲結構的花授粉算法。賈寶惠等考慮協作度的雙人異步并行拆卸序列規劃模型，使操作者在優先約束下產生的閑置時間加入另一操作者進行協作。鄧明星等提出了一種考慮多目標件的異步并行選擇性拆卸序列規劃方法，利用改進遺傳算法獲取最優拆卸序列規劃方案。郭秀萍等考慮拆卸任務先后順序約束并提出基于Pareto占優概念的多目標動態規劃求解方法。尹鳳福等建立手機拆卸混合圖模型，同時考慮緊固件的連接關系，利用多種群遺傳算法進行優化分析。

　　上述研究多數在確定的拆卸時間下進行序列規劃的分析，現實中，拆卸時間會受到多種因素的影響，如產品的腐蝕與磨損、拆卸操作的難度、工廠設備的好壞等因素會導致拆卸作業產生諸多不確定性。為了方便處理不確定的數據，鄭紅斌等引入了三角模糊數的方法對不確定的目標進行求解，提出一種改進磷蝦算法，驗證了模型的實用性和算法的優越性。Peng Hu等研究一種新的集成RSC設計以處理相關DSP問題。在實際的拆卸作業過程中，不確定的拆卸時間往往是一個區間內的某個值，但不知其確切值，可以引入灰數來定性表示。灰數是一種能夠處理不確定性的數學方法，將不確定的拆卸時間表示為灰數區間，提供更全面和準確的信息來進行后續的優化。

　　人工蜂群算法(artificial bee colony, ABC)是通過模擬蜜蜂覓食行為以及蜜蜂之間的信息共享和協作方式所提出的一種智能優化算法。因其簡單性、魯棒性和有效性，在組合優化問題中得到成功應用。

　　綜上，本研究將灰數引入異步并行拆卸序列規劃問題中，研究拆卸時間的不確定性，結合蜂群算法求解組合問題的優勢，用改進的人工蜂群算法(improving artificial bee colony, IABC)對所提模型進行求解。

　　1 不確定拆卸時間的異步并行DSP

　　1.1 問題描述

　　圖1為異步并行拆卸示意圖，展示了兩條拆卸線和若干操作員的工作情況，灰色的長條表示兩條拆卸線，黑色圓點表示不同的拆卸任務，黑色方塊表示不同的工人，虛線表示工人和任務之間的關系。

　　1.2 模型建立

　　最小拆卸時間(F_{1})表示為：

　　[

　　otimes Min F_{1}=sum_{j=1}^{J} max left(t_{11} x_{11}, t_{12} x_{12}, cdots, t_{j m} x_{j m} ight)

　　]

　　式中，(j)表示任務編號，(J)表示拆卸任務總數，(m)表示算子指數，(t_{j m})為第(m)個操作者執行拆卸操作(j)時所需時間，(x_{j m})表示決策變量，若操作(j)由第(m)個操作員執行，則(x_{j m}=1)，否則(x_{j m}=0)。

　　最大拆卸收益(F_{2})表示為：

　　[

　　Max F_{2}=sum_{j=1}^{J} sum_{i=1}^{N} C_{i j} f_{j} x_{j}-left[sum_{j=1}^{J} z_{j} x_{j}+otimes F_{1} q ight]

　　]

　　式中，(sum_{j=1}^{J} sum_{i=1}^{N} C_{i j} f_{j} x_{j})代表拆卸產品的總收入;(sum_{j=1}^{J} z_{j} x_{j}+otimes F_{1} q)為拆卸能耗，(C_{i j})表示關聯矩陣，(i)為零件編號，(f)是零件的回收利潤，(x_{j})表示第(j)個機械手;(z_{j})表示第(j)個任務的基本成本，(q)表示單位時間的研究成本。

　　除上述約束，所構建模型還需滿足6個條件：

　　1. 一條可行拆卸路徑最大操作時間不能超過規定時間約束，即：

　　[

　　sum_{l=1}^{L} max left(t_{11} x_{11}, t_{12} x_{12}, cdots, t_{j m} x_{j m} ight) leq T_{B}

　　]

　　式中，(T_{B})表示并行拆卸中規定的最大拆卸時間。

　　2. 確保整個拆卸過程中每個零件最多拆卸一次，即：

　　[

　　0 leq sum_{j=1}^{J} C_{i j} x_{j} leq 1, i=1,2, cdots, N

　　]

　　式中，(N)為零件總數。

　　3. 每次操作只能是優先互斥、協同以及關聯的其中一種，即：

　　[

　　C_{i j}+P_{j k}+E_{j k} leq 1

　　]

　　式中，(P_{j k})為優先互斥矩陣，(E_{j k})為協同矩陣。

　　4. 工作站順序約束，確保工作站按照順序開啟，即：

　　[

　　x_{w-1} geq x_{w}, forall w=1, cdots, W

　　]

　　式中，(x_{w})表示第(w)個工作站，(x_{w-1})為前一個工作站。

　　5. 一個機械手在任意一次的并行拆卸中最多執行長度為(L)的操作，即：

　　[

　　sum_{j=1}^{j}left(x_{j 1}+x_{j 2} ight) leq L

　　]

　　式中，(x_{j1})、(x_{j2})分別表示兩個機械手，(L)為一個異步并行拆卸序列的長度。

　　6. 決策變量為0~1變量，即：

　　[

　　x_{j}, y_{j m} in{0,1}(j, m=1,2, cdots, J)

　　]

　　式中，如果執行拆卸任務(j)，則為(x_{j}=1);否則為0;如果操作(j)是由第(m)個操作員執行的則(y_{j m}=1)，否則為0。

　　1.3 灰數白化

　　目標函數中含有灰色不確定參數(otimes F_{1})，無法直接求解，需要進行白化處理：

　　1. 設置白化權函數：

　　[

　　varphi(x)=frac{1}{a_{1}left(x-a_{0} ight)^{2}+1}

　　]

　　式中，(varphi(x))表示白化權函數，(a_{1})表示系數，(x)表示隨機變量，(a_{0})為白化權函數值最高時的白化值。

　　2. 生成白化值，將式(9)的白化權函數變換為式(10)，得到灰數(otimes)的白化值(overline{otimes})：

　　[

　　left{egin{array}{l}

　　f(x)=varphi(x) / int_{a}^{b} varphi(z) d z \

　　F(x)=int_{a}^{x} varphi(z) d z / int_{a}^{b} varphi(z) d z \

　　overline{otimes}=F^{-1}(u)

　　end{array} ight.

　　]

　　式中，(x)滿足概率密度函數(f(x))以及相應的分布函數(F(x))。根據概率密度的定義，(x)的概率分布函數為(F(cdot))。若隨機變量(u)服從區間([0,1])上的均勻分布，通過(F^{-1}(u))可獲得符合分布(F(cdot))特征的隨機數，根據式得到灰數對應 的白化值(overline{otimes}=F^{-1}(u))。

　　2 改進的人工蜂群算法

　　2.1 任務關系優先表示方法

　　在操作層次拆卸樹(operation-dependent hierarchical disassembly tree, OHDT)圖中，通過樹狀圖結構呈現拆卸路徑，其中每個節點代表一個組件或一個拆卸操作，如圖2即展示了一臺筆記本電腦的OHDT圖。

　　根據圖2可以得到拆卸過程中存在3種類型的關系。本研究采用矩陣(P_{j k})以表示操作(j)和(k)之間的優先互斥關系：

　　[

　　P_{j k}=left{egin{array}{l}

　　1, 若 j 在操作 k 之前且 k 無法完成 \

　　-1, 若 k 與 j 不可以一起進行 \

　　0, 其他

　　end{array} ight.

　　]

　　采用協同矩陣(E_{j k})記錄任務(j)和(k)之間是否存在協同關系：

　　[

　　E_{j k}=left{egin{array}{l}

　　1, 若 j 可與 k 一起進行 \

　　0 , 其他

　　end{array} ight.

　　]

　　引入了關聯矩陣(C_{i j})強調操作與拆卸零件之間的關聯性：

　　[

　　C_{i j}=left{egin{array}{l}

　　1, 若 i 零件通過操作 j 得到 \

　　0, 其他

　　end{array} ight.

　　]

　　2.2 編碼階段

　　本研究提出“多解協同對比”的優化方法。用序列(S=[S_{1}, S_{2}, cdots, S_{l}])來表示操作序列，其中(l)表示總操作數，操作按1到(l)的順序編號。隨后將兩個執行向量部分進行交叉以完成編碼工作。編碼過程如下：

　　1. 隨機生成的每個可行解的元素值被標記并涂上陰影，代表了每次實際的拆卸序列，例如，(S=[5,3,8,9,14,17,15,20])被提取作為下一步的起始序列。

　　2. 執行拆卸操作，若操作(a)在操作(b)之前則操作(a)在(S)序列中位于操作(b)右側，交換操作(a)和(b)后再次從左循環操作序列，(S_{1})至(S_{l})均重復該步驟。

　　3. 序列向量需滿足協同關系;將經過上述兩個步驟所得到的兩個可行序列向量，一個向量首端與另一個向量末端依次進行上下的協同比對以滿足矩陣(E)的協同要求。如果符合要求將保留操作;反之，標記為非陰影狀態。最后可以得到兩個機械手協同拆卸的序列向量。

　　2.3 解碼階段

　　可行的拆卸序列采用了矩陣解碼(Z={Z_{1}, Z_{2}})來表示，圖中(t_{15,1})表示機械手(Z_{1})執行操作所需的大致拆卸時間區間，(t_{16,2})表示(Z_{2})執行操作時所需的大致時間區間，(Z_{2})在(L=5)時并沒有出現矩陣，表示此時為空閑狀態。

　　2.4 雇傭蜂階段

　　傳統蜂群算法在該階段通過輪盤賭來篩選蜜源從而進行下一步的操作，每次迭代都需要重新計算個體的適應度值。相比之下，錦標賽選擇更為簡便，且能有效地保護最優解。因此，本研究選擇使用錦標賽選擇來替代輪盤賭方法。

　　2.5 守望蜂階段

　　本研究引入了遺傳算法的變異操作，該策略有助于探索更廣泛的解空間，提高算法的全局搜索能力。變異操作采用自適應變異概率，如式(14)所示：

　　[

　　A_{g}=A_{g}^{max }-frac{A_{g}^{max }-A_{g}^{min }}{max \_D} cdot D

　　]

　　式中，(A_{g})為變異概率;(A_{g}^{max })為最大變異概率，取(0.65);(A_{g}^{min })為最小變異概率，取(0.35);(max\_D)為最大迭代次數;(D)為當前迭代次數。

　　為了選擇適應度更高的食物來源，本研究采用了貪婪的選擇程序。經過變異的食物來源與原始食物來源進行比較，通過貪婪選擇，將優秀的食物來源保留。

　　2.6 偵察蜂階段

　　當雇傭蜂未能及時更新新的蜜源時，偵察蜂會在整個解集內進行搜索，在一定程度內避免了早熟機制，但也降低了尋優效率;針對該問題，本研究在IABC內提出“潛能值”定義：若新迭代的蜜源無法取代舊蜜源，則潛能值減少，反之增加;個體的潛能值將設置為一個區間內的預設值。潛能值更新公式如(15)所示：

　　[

　　Q_{i}=Q_{i}-frac{m_{i}}{S}

　　]

　　式中，(Q_{i})表示第(i)個蜜源的潛能值，(m_{i})表示第(i)個蜜源的目標函數值，(S)表示當前的最佳目標函數值。

　　2.7 IABC算法步驟

　　IABC算法具體步驟如圖6所示。

　　3 算法驗證

　　3.1 算法對比

　　為檢驗IABC的優越性，選取切諾貝利災難算法(CDO)、機器學習算法(ILA)以及人工蜂群算法(ABC)進行比較，使用MATLAB進行1000次的迭代，收斂曲線圖如圖7所示。由圖7可知，IABC算法在接近120次迭代時到達最優值，收斂速度要優于其他算法。

　　3.2 實例基本信息

　　現實中，相比其他的家用電器，筆記本電腦的零件成本較高且回收簡單，故采用Fujitsu AH556型號筆記本作為拆卸對象，拆卸信息包括顯示屏、系統板、固態驅動器、散熱器等22個零件，每個零件拆卸收益從0.5元到72.3元不等。

　　3.3 算例對比

　　在改進算法下進行同步并行拆卸與異步并行拆卸的測試，取部分結果如表3和表4所示。操作過程中出現0表示此時機械手為空閑狀態。

　　表3 同步并行拆卸算例帕累托解(部分)

　　|序號|機械手|過程|F1/s|F2/元|

　　|1|M1|3?17?6?9?11?14?13?16|291.97|270.88|

　　||M2|4?15?18?20?0?0?13?3| | |

　　|2|M1|13?7?9?11?17?16?0|260.47|263.91|

　　||M2|6?4?7?10?12| | |

　　|3|M1|14?3?6?11?16?7|100.6|154.95|

　　||M2|13?4?8?12?13?0| | |

　　表4 異步并行拆卸算例帕累托解(部分)

　　|序號|機械手|過程|F1/s|F2/元|

　　|1|M1|1?3?8?10?11?14?17?18|113.3|240.4|

　　||M2|2?4?5?9?12?13?19| | |

　　|2|M1|2?4?9?5?12|100.4|230.9|

　　||M2|1?8?3?9?12| | |

　　|3|M1|1?3?8?9?11?15?7?0|178.5|304.4|

　　||M2|2?4?6?10?14?12?18?13?0| | |

　　比較可得：異步并行拆卸平均拆卸收益為256.4元，相比同步并行拆卸的208.3元，經濟效益提高了23.1%;而異步并行拆卸所用的平均拆卸時間為142.6s，相比同步并行拆卸的163.3s，時間縮短了12.7%。

　　4 結束語

　　本研究考慮實際拆卸作業中拆卸時間的不確定性，引入灰數將確定的拆卸時間拓展至不確定拆卸時間，構建了兩個目標函數的異步并行拆卸數學模型。引入了優先互斥、協同和關聯3個約束來描述各組件之間的操作關系，并通過OHDT來描述拆卸信息模型。結合本研究特征，設計了IABC，用錦標賽代替原本的輪盤賭策略，提出一種新型的多解協同對比的方法;在偵查蜂階段為避免陷入局部最優，設計了潛能值的更新策略。將所提算法與現有算法進行對比，驗證其優越性。最后將本研究所改進算法與所提模型應用于筆記本電腦拆卸實例，結果表明異步并行拆卸在拆卸收益與拆卸時間上均優于同步并行拆卸。本研究僅考慮了拆卸時間的不確定性，實際拆卸過程中還存在許多不確定因素，如工人的體能消耗、疲勞程度等情況，未來將深入研究。

　　參考文獻

　　[1]吳秀麗,張興宇.工位數固定的U型拆卸線部分拆卸平衡問題[J].控制理論與應用,2024,41(6):1079-1088.

　　[2]GUNGOR A,GUPTA S M.An evaluation methodology for disassembly processes[J].Computers&Industrial Engineering,1997,33(1/2):329-332.

　　[3]徐鵬程.機電產品異步并行拆卸序列規劃與評價技術研究[D].杭州:浙江大學,2020.

　　[4]邢世雄,陳國華,孫川,等.基于改進蝙蝠算法的再制造裝配體拆卸序列規劃研究[J/OL].機械設計與制造,1-6[2024-11-08].https:∥doi.org/10.19356/j.cnki.1001-3997.20240516.008.

　　[5]郭鈞,王振東,杜百崗,等.考慮不定拆卸程度的選擇性異步并行拆卸序列規劃[J].中國機械工程,2021,32(9):1080-1090,1101.

　　[6]孫嫻靜,唐秋華,鄧明星.基于改進遺傳算法的異步并行拆卸序列規劃[J].工業工程,2022,25(4):151-157.

　　[7]張雷,耿笑榮,陶凱博.考慮碳排放與收益的隨機并行拆卸線平衡優化[J].機械工程學報,2023,59(7):330-338.

　　[8]賈寶惠,任帥,盧翔.考慮協作度的雙人異步并行拆卸序列規劃[J].機械設計與制造,2024(1):359-363,369.

　　[9]鄧明星,陳方穎,唐秋華,等.考慮多目標件的異步并行選擇性拆卸序列[J].計算機集成制造系統,2020,26(7):1749-1755.

　　[10]郭秀萍,周玉莎.用多目標動態規劃求解拆卸序列的Pareto最優前沿[J].系統管理學報,2023,32(6):1205-1212.

　　[11]尹鳳福,劉廣闊,王曉東,等.基于多種群遺傳算法的廢舊手機拆卸序列規劃[J].合肥工業大學學報(自然科學版),2023,46(4):438-446.

　　[12]ZHANG X S,FU A P,ZHANG S,etal.Selective disassembly sequence planning under uncertainty using trapezoidal fuzzy numbers:a novel hybrid metaheuristic algorithm[J].Engineering Applications of Artificial Intelligence,2024,128:107459.

　　[13]鄭紅斌,張則強,曾艷清.不確定工人體能消耗的多目標U型拆卸線平衡問題[J].計算機集成制造系統,2023,29(2):392-403.

　　[14]HU P,CHU F,DOLGUI A,etal.Integrated multi-product reverse supply chain design and disassembly line balancing under uncertainty[J].Omega,2024,126:103062.

　　[15]REN Y X,GAO K Z,FU Y P,etal.Ensemble artificial bee colony algorithm with Q-learning for scheduling bi-objective disassembly line[J].Applied Soft Computing,2024,155:111415.