基于分布估計算法的并行拆卸序列規(guī)劃研究*

郭硯榮，張秀芬

(1.內蒙古化工職業(yè)學院 測控與機電工程系，內蒙古 呼和浩特 010070；2.內蒙古工業(yè)大學 機械學院，內蒙古 呼和浩特 010051)

0 引 言

拆卸序列規(guī)劃是根據(jù)產品的裝配關系、零部件的結構、尺寸以及拆卸資源，推理出將產品上的一個或多個零件拆下的最優(yōu)拆卸順序的求解過程[1-4]。產品的拆卸是回收再制造的關鍵步驟之一，良好的拆卸序列可以大大提高拆卸效率。對于大型復雜機械產品的拆卸工作往往是多人參與，這就要求在考慮拆卸約束的情況下，合理地分配每個拆卸操作者的拆卸任務，以便提高效率。因此，研究并行拆卸對實際拆卸工作有重要意義。

目前，并行拆卸序列規(guī)劃(PDSP)已受到了國內外學者的關注。早期的研究有CHEN等[5]“剝蒜”法、KANG等[6]的整數(shù)規(guī)劃法等?！皠兯狻狈▋H適用于二維裝配體的并行拆卸序列規(guī)劃，整數(shù)規(guī)劃法可以精確獲得最優(yōu)解，但在產品零件數(shù)目多的情況下會產生組合爆炸。近期的研究集中于基于智能算法的并行拆卸序列規(guī)劃方法。例如，張雷等[7]利用傳遞閉包算法進行聚類分析，并通過人工蜂群算法規(guī)劃復雜產品的并行拆卸序列，但該方法僅適用于有多個組件的產品；蔡凱駿等[8]提出分階段迭代的蟻群算法進行拆卸序列規(guī)劃，該算法在解的質量和效率之間很好地取得了平衡，但其前提是所有零件的基本拆卸時間相等，而實際拆卸中，多人協(xié)作的并行拆卸序列和各個被拆零件的基本拆卸時間有關；REN等[9]以多目標的人工蜂群算法規(guī)劃并行拆卸序列，獲得最優(yōu)解的效率較高，但該方法前提是假定每步拆卸多人同時開始拆卸。

上述方法雖然在并行拆卸序列方面取得了重大成果，但是存在的主要問題是：(1)產品的拆卸往往是多人協(xié)作的工作過程，存在著平行或交叉的拆卸作業(yè)，現(xiàn)有的并行拆卸序列大多是多條串行拆卸序列的簡單合并，沒有全面考慮人力的調度；(2)許多算法容易產生大量的無效解，搜索時間長，容易陷入局部最優(yōu)。

分布估計算法(EDA)是將統(tǒng)計學與遺傳進化算法相結合的一種算法[10-11]。傳統(tǒng)的遺傳算法采用交叉與變異生成新一代群體，從而求解問題；而分布估計算法是用精確的概率模型更新下一代種群，由于不需要交叉與變異操作，分布估計算法解決了傳統(tǒng)遺傳算法由于交叉、變異操作所導致的優(yōu)良模式破壞問題。該算法目前已經在多目標規(guī)劃、調度問題和路徑規(guī)劃等領域得到成功應用。

為此，本文全面考慮拆卸約束、人力的調度和拆卸任務的分配等約束，提出基于分布估計算法的并行拆卸序列規(guī)劃方法，以實現(xiàn)并行拆卸序列規(guī)劃的快速求解。

1 拆卸模型的建立

1.1 層次拆卸任務圖

零件在裝配體中的裝配深度不同，其對應的拆卸層次也不同。為了將產品零件之間的拆卸優(yōu)先關系更直觀的表達出來，筆者基于逐層拆卸的思想，構建產品的層次拆卸任務圖G，其定義為G=(V,E)。

其中：V=(v0,v1,v2,…,vn,vn+1)，

v1,v2,…,vn—實節(jié)點，表示零件n—零件的個數(shù)；v0,vn+1—添加的拆卸任務開始和結束的虛節(jié)點，表示虛任務，開始的虛節(jié)點指向所有實際開始的任務，所有最后結束的實任務指向結束的虛節(jié)點；E—節(jié)點之間的有向邊，對于實節(jié)點之間的有向邊表示不同裝配層次的兩個零件間的拆卸約束關系，用帶箭頭的實線表示，箭尾指向的零件的拆卸優(yōu)先級高于箭頭指向的零件，而虛節(jié)點和其他實節(jié)點之間用帶箭頭的虛箭線連接，表示虛任務。箭尾所指節(jié)點稱為箭頭所指節(jié)點的緊前拆卸任務，反過來，箭頭所指節(jié)點稱為箭尾所指節(jié)點的緊后任務。

本研究以滑動軸承為例說明層次拆卸任務圖的信息含義?；瑒虞S承裝配圖及其層次拆卸任務圖如圖1所示。

圖1 滑動軸承裝配圖及其層次拆卸任務圖

其中，節(jié)點0是添加的開始虛節(jié)點，虛節(jié)點0與實節(jié)點1之間的虛箭線表示一項虛任務；而節(jié)點11是軸承座，相當于基體，基體一般都是最后拆卸，當其他所有零件都拆卸完成后，只剩下基體了，相當于基體也拆卸了，所以節(jié)點11相當于結束的虛節(jié)點，無需再添加另外的結束虛節(jié)點，因此節(jié)點10與節(jié)點11之間用虛箭線表示，增加虛節(jié)點主要是為了使每個實任務都有緊前和緊后任務，以方便后續(xù)的處理；而其他實任務之間用實箭線連接。L0～L8表示8個不同拆卸層次，L0層是虛任務，L1層的零件是可以最先拆卸掉的零件，而L8層的零件需要解除掉L1層至L7層的對應的約束才可以拆卸。

1.2 層次拆卸任務圖的鄰接矩陣

層次拆卸任務圖和其對應的鄰接矩陣可以相互轉換，層次拆卸任務圖在計算機內是通過存儲其鄰接矩陣Mr實現(xiàn)的，mrij=1表示i是j的緊前任務，j是i的緊后任務，否則為0。圖1(b)的滑動軸承層次拆卸任務圖可以用如下鄰接矩陣表示：

緊后拆卸任務

1.3 拆卸約束矩陣

拆卸約束矩陣是反映產品零件之間拆卸優(yōu)先關系的矩陣，其數(shù)學表達式如下：

MC={mcij}n×n

(1)

其中：

1.4 層次拆卸任務圖構建方法

層次拆卸任務圖的構建主要有以下步驟：

(1)在產品的三維模型中通過二次開發(fā)提取零件間的裝配約束關系信息，并通過人工補充約束生成產品的拆卸約束矩陣；

(2)利用式(1)的零件拆卸條件判斷當前所有可拆卸零件，并將其存儲到第一層集合L1中，然后更新拆卸約束矩陣，繼續(xù)利用式(1)判斷更新后的矩陣中的可拆卸零件，直至拆卸約束矩陣為空矩陣，并依次將可拆卸零件放入對應的Lk層中；

(3)依據(jù)拆卸約束矩陣的約束信息添加不同層次零件之間的拆卸約束，生成產品的層次拆卸任務圖。

層次拆卸任務圖生成流程圖如圖2所示。

圖2 層次拆卸任務圖生成流程

2 問題描述

并行拆卸序列規(guī)劃問題的求解就是在滿足目標函數(shù)條件下，找到最優(yōu)的拆卸序列，并對拆卸任務制定分配方案。

為了降低并行序列求解的復雜程度，本文作以下假設：

(1)每個零件由一個拆卸人員拆卸；

(2)多人拆卸時，操作者拆卸區(qū)域互不干涉；

(3)不同拆卸人員拆卸相同零件所需的時間相同。

因為本文的拆卸序列規(guī)劃以拆卸總時間最少為優(yōu)化目標，產品的并行拆卸實際上是在綜合考慮拆卸約束和拆卸資源的情況下，合理安排拆卸活動中各個零件拆卸的開始時間和結束時間。

假設產品有n個待拆卸零件，將每個待拆卸零件看作一項拆卸任務，則產品的拆卸活動由n個任務構成集合DT={0,1,2，…n,n+1}，任務0和任務n+1分別為附加的開始和結束的虛任務，這樣可以使得每個實際非空任務都至少有一個直接前向任務和后向任務，以便于后續(xù)的處理。M={m1,m2,…,mn}—拆卸操作人員集合；T={t1,t2,…tn}—零件基本拆卸時間集合，即每個任務的持續(xù)時間；tj(1≤j≤n)—第j個任務的持續(xù)時間；S={s1,s2,…,sn,sn+1}—每個任務的開始時間集合；E={e1,e2,…,en,en+1}—每個任務的結束時間集合。基于以上假設，建立產品的并行拆卸數(shù)學模型。

優(yōu)化目標：

Min{max(e1,e2,…,en)}

(2)

拆卸約束條件：

ei≤ej-ti,?(i,j)∈C

(3)

拆卸操作人員數(shù)量約束：

(4)

式中：集合C—任務的時序約束，由兩個任務組成的任務對構成，C可以通過層次拆卸任務圖的鄰接矩陣Mr獲??；St—全部在時刻t正在進行的任務的集合。

3 并行拆卸序列規(guī)劃問題的求解

3.1 編碼與解碼

考慮并行拆卸序列和EDA算法的特點，本文采用基于任務的編碼方法，把每個待拆卸零件看作一個拆卸任務。其解的形式采用自然數(shù)排列編碼，自然數(shù)是零件的編號，數(shù)字出現(xiàn)的順序代表零件的拆卸順序，數(shù)字越靠前表示對應的拆卸任務越需優(yōu)先完成，比如有6個編號為1～6的待拆卸零件的編碼為{0，6，5，3，2，1，4，7}。其中，“0”和“7”為開始的虛任務，“6”在第一位表示編號為6的零件是首先要拆卸的實際任務，而編號為“4”的零件是最后拆卸的任務，而多人協(xié)作的并行拆卸規(guī)劃是每一個拆卸任務的開始時間與結束時間的調度方案，所以還需將這種編碼解碼為每一個任務的時間安排。

本文采用掃描法生成任務調度方案進行解碼[12]。即根據(jù)拆卸任務的約束，對拆卸人員進行調度，生成并行調度方案，即對給定的編碼解里的各項拆卸任務，在滿足拆卸約束的條件下，在給定的拆卸人數(shù)限制下進行并行調度。解碼流程圖如圖3所示。

圖3 解碼流程圖

主要有以下5個步驟：

(1)首先初始化當前時間D_t為零、結束事件列表D_e為空，并設定拆卸任務掃描列表D_s的初始值為鄰接矩陣Mr中最先開始的虛任務0；

(2)判斷在當前時刻D_t，事件列表D_e中是否有事件發(fā)生，如果有則處理事件，并釋放任務所占拆卸人員，更新拆卸人員集合和當前可用人員數(shù)量，根據(jù)該結束任務從鄰接矩陣中找出滿足時序約束的緊后任務加入到任務掃描列表D_s中，并將該任務結束事件從列表D_e和矩陣Mr中移除；

(3)如果當前時刻沒有事件發(fā)生且仍然有未被調度任務，轉(4),如果沒有未被調度任務,轉(7)；

(4)通過矩陣Mr依次判斷列表D_s中的任務的時序約束關系，標識滿足時序約束關系的候選任務；

(5)根據(jù)編碼的順序確定候選任務的優(yōu)先權，并依次掃描每個候選任務，判斷當前是否有空閑拆卸人員，如果有則開始執(zhí)行任務，包括更新拆卸人員數(shù)量，從零件的基本拆卸時間集合T中獲得任務的持續(xù)時間ti，通過公式ei=D_t+ti計算該任務結束事件的時刻，并將該任務添加到D_e列表中，同時將其從D_s列表中刪除；

(6)當掃描完D_s列表中滿足時序約束的任務后，將當前時間D_t推進到D_e中最早結束事件的時刻，跳到(2)；

(7)結束，輸出調度方案。

以圖1中的滑動軸承為例，軸承各零件的基本拆卸時間如表1所示。

表1 滑動軸承各零件的基本拆卸時間

其中，A={0,1,7,2,8,6,3,4,5,9,10,11}是一個符合拆卸約束的可行的編碼解。假定參與并行拆卸的人數(shù)為2，對該編碼解通過掃描法解碼，得到的滑動軸承并行拆卸調度圖如圖4所示。

圖4 滑動軸承并行拆卸調度圖

圖4中橫坐標表示時間，縱坐標表示拆卸人員。通過此種解碼方式，本文計算出了2個人并行拆卸產品所需的總時間為10 s。

3.2 概率模型及更新方法

EDA算法是通過從種群中選取部分優(yōu)勢個體，運用統(tǒng)計學習的手段建立一個概率模型，從而描述候選解在空間的分布情況，再根據(jù)建立的概率模型隨機采樣產生新的種群以實現(xiàn)進化。

用EDA求解問題，關鍵要選擇合適的概率模型。本文給出如下概率模型及更新機制。假設一個待拆卸產品有n個待拆卸零件，即n個拆卸任務，其EDA算法的概率模型可用矩陣來表示：

(5)

式中：prij—將任務i安排在任務序列位置j的概率；t—進化的代數(shù)。

初始化種群時，初始概率矩陣的值可用矩陣表示：

(6)

概率模型更新時，首先從種群中選擇E個較優(yōu)的精英解，再更新計算：

(7)

式中：β—學習進度；k—精英解中的個體，在個體k中如果任務i安排在第j個位置，則Iij,k=1，否則，Iij,k=0。

生成新個體時，編碼的位置j上安排任務i的概率為：

(8)

式中：M—序列的對應位置的滿足時序約束(拆卸約束)的全部可選擇的拆卸任務集合，該集合可以通過搜索層次拆卸任務圖獲得，然后用輪盤賭方法生成新的解。

3.3 適應度函數(shù)

本文用最短拆卸完工時間作為評價指標，可行編碼解的完工時間可表示為：

f(A)=max(e1，e2，…en)

(9)

式中：f(A)—對應編碼解A的拆卸完工時間，當解碼生成前向調度方案后便可獲得每個拆卸任務的完工時間。

3.4 拆卸序列規(guī)劃流程

流程主要分3大步驟：

(1)通過人機交互方式構建產品的拆卸約束矩陣，并根據(jù)1.4的方法構建產品的層次拆卸任務圖，然后設定各個零件的基本拆卸時間、并行拆卸的人數(shù)；

(2)設定種群數(shù)Np以及最大迭代次數(shù)，初始化概率矩陣、初始化種群；

(3)運用掃描法解碼并評價解的適應度，直至達到最大迭代次數(shù)，最后輸出最優(yōu)解。

基于EDA的并行拆卸序列規(guī)劃算法流程圖如圖5所示。

圖5 基于EDA的并行拆卸序列規(guī)劃算法流程

4 實例應用

本研究以閥蓋頭夾具驗證本文的拆卸序列規(guī)劃方法。閥蓋頭夾具爆炸圖及其層次拆卸任務圖如圖6所示。

圖6 閥蓋頭夾具爆炸圖及層次拆卸任務圖

閥蓋頭夾具零件信息及編號如表2所示。

本研究以Matlab為實驗平臺，設置種群規(guī)模為30、精英解個數(shù)為10、最大迭代次數(shù)為50，進行運算。閥蓋頭夾具并行拆卸調度圖如圖7所示。

表2 閥蓋頭夾具零件信息及編號

圖7 閥蓋頭夾具并行拆卸調度圖

筆者將本文方法與遺傳算法、分支定界算法規(guī)劃的2人并行拆卸結果進行對比研究[13-14]，結果如表3所示。

表3 研究結果對比表

從表中可看出：本文所規(guī)劃的并行拆卸完工時間遠比其他兩種方法規(guī)劃的時間短，本文方法的運行時間略高于遺傳算法的運行時間。

利用改進人工蜂群算法對本例進行2人并行拆卸規(guī)劃[15]，得到的最優(yōu)拆卸序列為(16,18)→(20,22)→(15,17)→(19,21)→(14)→(11,12)→(7,8)→(6，2)→(3,13)→(10,1)→(5,9)，總的拆卸時間為23 s,大于本文方法規(guī)劃的拆卸時間20.5 s。

通過對比可以看出，本文的算法在求解的效率與質量之間達到了較好的平衡。原因是本文選取的對比文獻中的編碼方法都是假設并行拆卸的每步任務同時執(zhí)行，比如并行度為2時，只有兩人都完成了上一步任務才同時開始執(zhí)行下一步任務，而實際當中由于有些零件的基本拆卸時間不同會導致兩人的任務完成時間不同步，完工早的拆卸人員可以馬上進入下一個可行拆卸任務，不必等待另一名拆卸人員；而本文的方法可充分地對多名拆卸人員及時調度，所以方案優(yōu)化效果更佳。

5 結束語

本文在總結現(xiàn)有并行拆卸序列規(guī)劃的基礎上，提出了基于分布估計算法的并行拆卸序列的規(guī)劃方法，具體如下：

(1)研究了產品層次拆卸任務圖的構建方法并存儲其鄰接矩陣，通過層次拆卸任務圖清楚的表達出各項拆卸作業(yè)的時序約束關系；

(2)將每一個被拆零件視為一項拆卸任務，以拆卸任務為基礎進行編碼，編碼時依據(jù)層次拆卸任務圖的鄰接矩陣按任務的時序約束進行，避免了無序編碼的產生。運用掃描法對多人參與的拆卸作業(yè)進行并行解碼，該解碼方法既考慮了零件間的拆卸約束，又根據(jù)拆卸人員的狀態(tài)與數(shù)量合理的安排拆卸任務，從而提高了解的優(yōu)化效果；

(3)以最短拆卸完工時間為優(yōu)化目標，運用分布估計算法獲得產品的并行拆卸序列最優(yōu)解，并通過實例驗證該方法可以獲得質量較優(yōu)解。