基于啟發式算法的檢測資源分配研究

屈力剛，宋昕一，田健琪，萬景洋，肖 龍

（1.沈陽航空航天大學 航空制造工藝數字化國防重點學科實驗室，遼寧 沈陽 110136；2.華晨汽車集團控股有限公司，遼寧 沈陽 110000）

隨著國內制造業的快速發展，生產線自動化、柔性程度越來越高，企業多型號產品并線生產，產量成倍增加，因此，需要對產品幾何量的檢測效率提出更高的要求。

目前，產品幾何量檢測技術的研究已經從降低測點數量[1]、優化檢測路徑[2]、降低人為因素影響[3，4]、使用三維數模代替二維圖紙進行編程等很多方面進行了研究。但企業同時存在嚴重的檢測資源利用率低下，檢測資源分配不合理等現象。以某研究院為例，其大量檢具長時間閑置，個別檢具滿載運轉。若能進行合理的檢測資源分配，提高閑置檢測資源的利用率，則能大大提高企業的檢測效率。針對此問題，本文提出了基于啟發式算法，針對檢測資源分配問題進行了系統研究。

1 檢測資源能力模型建立

啟發式算法（Heuristic Algorithm），是用一個問題的最優算法求得該問題每一個實例的最優解。基于啟發式算法的檢測資源分配在分配過程中需考慮三點：①檢具是否有所需的檢測能力；②總檢測時間；③檢測總成本。

檢具的檢測能力主要分為：尺寸檢測能力、精度能力、形狀檢測能力、檢測效率能力。若使用三坐標測量機，則還包括測頭庫和檢測工藝能力，如圖1所示。

圖1 檢測設備資源能力模型

在測量一個零件時，首先考慮零件的基本尺寸是否在其測量范圍內，測量設備的測量精度是否滿足要求。其次通過零件的外形，判斷檢具是否具有其形狀檢測能力（若使用三坐標測量機，則還需考慮其測針是否夠長，測座可旋轉角度，球頭能否順利進行觸測）。在此基礎上，考慮其測量效率和批量檢測能力[5]。

2 檢測工藝過程節點圖構建

2.1 非線性檢測工藝規劃

在產品的整個生產周期中，檢測工藝伴隨加工工藝貫穿始終。一套完整的工藝由多個加工工序和檢測工序組合而成。其檢測工藝描述如圖2所示。

圖2 某非線性檢測工藝描述

其中符號表示選擇關系，符號表示并行關系。圖中的非線性檢測工藝結構化描述如下：

如圖3所示，每道檢測工序有多種檢測資源類型可供選擇，而每種檢測資源類型又對應著多型號的檢測設備。檢測工藝與檢測資源之間存在著復雜的相互影響的關系，不同檢測設備的檢測效率、測量精度和使用成本不同，因此不同的分配方式決定了不同的測量效率和測量成本。因此，檢測資源的分配是復雜的非線性規劃的問題。

2.2 檢測工藝過程節點圖構建

產品的檢測工藝路線將直接影響檢測時間。某零件的非線性檢測工藝路線如圖4所示。

可以利用檢測過程節點圖將檢測工藝資源分配問題變換為網絡圖問題。通過其關鍵路徑得出檢測時間，再通過仿真，實現工藝規劃。其工藝路線圖可轉化為如圖5所示的節點圖[6]。

圖中各節點表示各道檢測工序，箭頭指向表示各道檢測工序之間的順序。當涉及到多個零件的檢測工藝路線時，不同的零部件可以并行地進行檢測，這樣就可以構建整個產品檢測工藝路線節點圖。

對每道檢測工序進行檢測資源分配后，網絡圖就會有具體的檢測時長和檢測成本信息。不同的檢測設備檢測相同的工序所需時間和成本不同，因此，檢測設備的分配直接影響整個檢測的成本和時間。

圖3 檢測工藝資源優化分配模型

圖4 某零件的非線性檢測工藝路線圖

圖5 非線性檢測工藝路線節點圖

對檢測工藝結構圖來說，在檢測能力滿足的情況下，對總檢測時間影響最大的是圖中的最長路徑，即關鍵路徑（Critical Path）。當檢測資源分配情況不同時，檢測時間會因檢測設備的不同而發生變化。因此，此問題可以使用CPM（Critical Path Method）計算。

3 檢測工藝資源分配模型的建立

3.1 模型優化規則

在滿足檢測能力的基礎上，檢測工藝資源分配主要考慮兩個因素：檢測成本和檢測時間。現確定檢測工藝資源分配的基本規則如下：

規則1：某一類檢測工藝資源的檢測設備在同一時間只能檢測一道工序。這是因為企業的檢測資源具有唯一性。在企業中，每臺設備都有唯一的標識。制定這一規則是為了保證檢測資源分配不沖突。

規則2：產品的檢測時間都是有限制的，因此檢測工藝資源的分配必須滿足時間約束。超出規定的時間約束就擾亂產品生產的效率。當所分配的檢測資源不能滿足時間約束的時候，就必須進行重新分配，以減少檢測時間。

規則3：在滿足1、2條的基礎上，盡可能保證檢測工藝資源成本最低。

規則3是檢測工藝資源分配的總目標，時間約束和資源不沖突約束都是對檢測過程的約束。

根據檢測工藝資源分配的基本規則，制定如下步驟：

（1）檢測資源在分配過程中必須達到的是規則1和3，檢測資源分配成本最低，且進行檢測的資源都是獨一無二的，以保證無沖突。

（2）如果檢測資源在分配過程中違反了規則2，那么必須對檢測資源進行重新分配，縮短檢測完成時間。

（3）若檢測資源分配方案最后得出的時間遠小于約束時間，則應適當的對檢測資源進行調整，以保證成本最低。

3.2 檢測工藝資源分配模型的建立

由檢測資源分配規則可知，所建立的數學模型是以檢測時間和檢測資源唯一性為約束條件，總檢測成本為優化目標的函數。

假設一個檢測工藝網絡圖中有N個任務節點，每道工序有M種檢測資源可用，若第j種檢測資源分配到每i個檢測任務工序的每小時檢測成本為Cij（j=1，2…m），第j種檢測資源完成該道檢測工序的時間是Tij。選中第j種檢測資源是Aij=1。則可以得出檢測工藝資源的分配的求解函數：

需要保證總的檢測成本最低，有如下約束：

（3）Tcpm（T1，T2，…Tn）≤T0（4），表示檢測的最長時間不得超過規定的檢測時間。

4 算法求解

基于啟發式算法的檢測工藝資源分配共用到三種函數，分別是：①基于檢測成本的檢測工藝資源分配函數；②沖突調節函數；③考慮到時間約束的檢測工藝資源分配函數。如圖6所示。

算法的輸入是：①各檢測任務之間的先后順序，即檢測工藝路線節點圖；②檢測資源的分類和檢測成本；③檢測資源的檢測能力信息。

算法的輸出是：①檢測資源分配信息；②最長檢測時間；③總檢測成本。

圖6 基于啟發式算法的檢測工藝資源分配流程

4.1 基于成本的檢測工藝資源分配

基于成本的檢測工藝資源分配算法是在不計檢測時間和工藝資源唯一性的約束的前提下，直接以成本最低為目的對檢測資源進行優化分配，并未考慮檢測資源的唯一性，只是將檢測成本最低納入考量。啟發式算法的輸入是檢測資源分配情況，檢測任務先后順序和每一類檢測資源的檢測能力、成本信息等。啟發式算法的輸出是資源分配表、總檢測時間和成本。

其分配過程如圖7所示。

4.2 沖突調節函數

檢測工藝資源初始值分配完畢后，需對有檢測資源沖突的任務節點進行篩選，采用雙重嵌套循環檢查。當檢查到任務節點V和V0之間有檢測工藝資源沖突時，在不改變其他節點資源分配的情況下進行重新分配。在重新進行檢測工藝資源分配的過程中，主要考慮總檢測時間和總檢測成本。在檢測時間最短的情況下，控制使其檢測成本最低。如圖8所示。

4.3 考慮時間約束的檢測工藝資源分配

基于成本的檢測工藝資源分配算法沒有考慮時間限制，但為了滿足生產節拍需求，實際應用過程中的檢測資源分配必須滿足時間約束，在基于成本的分配方法前提下進行調整。如圖9所示。

圖7 基于檢測成本的檢測工藝資源分配算法流程圖

圖8 沖突調節函數流程圖

該算法的最終目的是在保證檢測時間滿足要求的情況下，追求檢測成本最低。在某一任務節點中，若重新分配檢測工藝資源，則檢測時間和檢測成本都會發生改變。設節點T0中，按前兩個算法對檢測工藝資源S0（檢測成本Expense0、檢測時間T0）進行了選擇。將其他可選的檢測工藝資源（檢測成本Expense′、檢測時間T′）與已選定的檢測工藝資源進行對比。計算補償率△Time/△Expense的值。高補償率檢測資源在保證增加成本較小的情況下更有利于縮短檢測時間。補償率計算公式為：（T0-T′）/（Expense′-Expense0）。

此調整算法需首先選擇當前的關鍵路徑，其中各任務節點可用檢測工藝資源的補償率進行計算，選擇最大補償率資源，并進行沖突消解，計算整個檢測工藝過程節點圖的補償率。對所有任務節點進行遍歷后，選擇整個檢測工藝過程中補償率最大的資源分配方法進行檢測工藝資源重新分配。然后判斷檢測時間是否滿足要求，若檢測時間不滿足要求，則需重新尋找關鍵路徑并繼續對檢測工藝資源進行優化分配，以縮短時間。當檢測最大路徑在要求范圍內時，循環結束，完成資源分配。若所有檢測工藝資源能力不足以滿足時間要求時，直接退出循環。

4.4 實例驗證

圖9 考慮時間約束的檢測工藝資源分配調整算法流程圖

以下圖所示的檢測工藝路線為例，共有7個任務和3條路徑。本道檢測工藝限制時間為8小時。

針對如圖10所示檢測工藝路線，設如表1所示的檢測資源分類情況。假設同種類檢測資源的使用成本和檢測能力相同。

圖10 檢測工藝路線圖

設檢測資源檢測能力如表2所示。

工藝路線的節點圖如圖11所示。

由圖11可見，該檢測工藝路線比較簡單。首先，計算出各道工序所需成本和時間，如表3所示，括號內為工序所需的檢測時間。

表1 檢測資源分類表

首先，運用基于成本的檢測工序資源分配算法，對檢測資源進行初始分配。為每一道檢測工序選取檢測成本最低的檢測資源，得到如表4所示資源分配結果。

表中的檢測設備分配結果較為理想化，其關鍵路徑是P1-P2（P3）-P4-P7可見檢測任務P1和檢測任務P6之間存在檢測資源沖突。在此情況下，使用沖突調解算法，將設備S5分配給任務P1和任務P6再重新進行成本計算。將設備S5分配給任務P1時，任務P6可使用檢測設備S22，分配情況如表5所示。

表2 檢測資源能力表

圖11 檢測工藝節點圖

表3 各道檢測工序總成本和所用時間表

表4 基于成本的檢測工藝資源分配結果

因檢測工藝的限制時間是8小時，而最長檢測時間是9小時，顯然不能滿足需求。這時利用考慮時間約束的算法調整，計算關鍵路徑P1-P2（P3）-P4-P7中各個檢測資源的補償率Rv=△Time/△Expense值，經過計算，只有P4工序的比值為正，Rv=0.25。對工序P4的檢測資源進行調整，將P4的檢測資源調整為S42，這時滿足了時間限制，退出算法。其最終分配結果如表6所示。

表5 沖突調節后的檢測工藝資源分配結果

表6 考慮時間約束的檢測工藝資源分配結果

若需要進一步縮短檢測時間，則需針對分配情況重新確定關鍵路徑，計算每一道工序的時間成本比Rv，并選擇Rv最大的工序進行調整分配。

5 結論

本文分析了檢測資源分配多樣性的成因，并且建立了檢測資源能力模型和檢測資源分配求解函數，以檢測時間為約束，檢測總成本為目標函數，通過啟發式算法進行檢測資源分配的優化求解，實現了企業檢測資源分配的合理化、規范化和利用率最大化。本算法支持從檢測資源能力方面進行檢測資源合理分配，并且能夠從檢測時間和檢測成本兩方面進行檢測資源的合理分配，為企業節省檢測成本及時間成本。經某汽車企業實例驗證，基于啟發式算法的檢測工藝資源分配可提高檢測效率30%，對于企業生產來說，具有很大的實用價值及深遠意義。

參考文獻：

[1] 盧耀暉，周繼偉，張 蔚，等.基于三坐標測量機的平面測量方法研究[J].裝備制造技術，2011，（4）：110-113.

[2] 王世剛，付宜利.數字化環境下在線檢測路徑優化技術的研究[J].組合機床與自動化加工技術，2009，（5）：52-55+60.

[3] 屈力剛，田健琪，韓 義，等.基于MBD的三坐標檢測工藝系統構建技術研究[J].制造業自動化，2017，39（2）：1-4.

[4]劉達新.基于三維CAD的智能三坐標測量機檢測規劃系統的研究與開發[D].合肥：合肥工業大學，2009.

[5] 蔡 菲.工藝資源管理及應用研究[D].武漢：武漢理工大學，2010.

[6] 駱 珣，等.項目管理教程 [M].北京：機械工業出版社，2004：160-170.