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

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

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

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

1 檢測資源能力模型建立

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

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

圖1 檢測設(shè)備資源能力模型

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

2 檢測工藝過程節(jié)點圖構(gòu)建

2.1 非線性檢測工藝規(guī)劃

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

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

其中符號表示選擇關(guān)系，符號表示并行關(guān)系。圖中的非線性檢測工藝結(jié)構(gòu)化描述如下：

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

2.2 檢測工藝過程節(jié)點圖構(gòu)建

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

可以利用檢測過程節(jié)點圖將檢測工藝資源分配問題變換為網(wǎng)絡(luò)圖問題。通過其關(guān)鍵路徑得出檢測時間，再通過仿真，實現(xiàn)工藝規(guī)劃。其工藝路線圖可轉(zhuǎn)化為如圖5所示的節(jié)點圖[6]。

圖中各節(jié)點表示各道檢測工序，箭頭指向表示各道檢測工序之間的順序。當(dāng)涉及到多個零件的檢測工藝路線時，不同的零部件可以并行地進(jìn)行檢測，這樣就可以構(gòu)建整個產(chǎn)品檢測工藝路線節(jié)點圖。

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

圖3 檢測工藝資源優(yōu)化分配模型

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

圖5 非線性檢測工藝路線節(jié)點圖

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

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

3.1 模型優(yōu)化規(guī)則

在滿足檢測能力的基礎(chǔ)上，檢測工藝資源分配主要考慮兩個因素：檢測成本和檢測時間?，F(xiàn)確定檢測工藝資源分配的基本規(guī)則如下：

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

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

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

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

根據(jù)檢測工藝資源分配的基本規(guī)則，制定如下步驟：

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

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

（3）若檢測資源分配方案最后得出的時間遠(yuǎn)小于約束時間，則應(yīng)適當(dāng)?shù)膶z測資源進(jìn)行調(diào)整，以保證成本最低。

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

由檢測資源分配規(guī)則可知，所建立的數(shù)學(xué)模型是以檢測時間和檢測資源唯一性為約束條件，總檢測成本為優(yōu)化目標(biāo)的函數(shù)。

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

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

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

4 算法求解

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

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

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

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

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

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

其分配過程如圖7所示。

4.2 沖突調(diào)節(jié)函數(shù)

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

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

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

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

圖8 沖突調(diào)節(jié)函數(shù)流程圖

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

此調(diào)整算法需首先選擇當(dāng)前的關(guān)鍵路徑，其中各任務(wù)節(jié)點可用檢測工藝資源的補(bǔ)償率進(jìn)行計算，選擇最大補(bǔ)償率資源，并進(jìn)行沖突消解，計算整個檢測工藝過程節(jié)點圖的補(bǔ)償率。對所有任務(wù)節(jié)點進(jìn)行遍歷后，選擇整個檢測工藝過程中補(bǔ)償率最大的資源分配方法進(jìn)行檢測工藝資源重新分配。然后判斷檢測時間是否滿足要求，若檢測時間不滿足要求，則需重新尋找關(guān)鍵路徑并繼續(xù)對檢測工藝資源進(jìn)行優(yōu)化分配，以縮短時間。當(dāng)檢測最大路徑在要求范圍內(nèi)時，循環(huán)結(jié)束，完成資源分配。若所有檢測工藝資源能力不足以滿足時間要求時，直接退出循環(huán)。

4.4 實例驗證

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

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

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

圖10 檢測工藝路線圖

設(shè)檢測資源檢測能力如表2所示。

工藝路線的節(jié)點圖如圖11所示。

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

表1 檢測資源分類表

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

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

表2 檢測資源能力表

圖11 檢測工藝節(jié)點圖

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

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

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

表5 沖突調(diào)節(jié)后的檢測工藝資源分配結(jié)果

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

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

5 結(jié)論

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

參考文獻(xiàn)：

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

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

[3] 屈力剛，田健琪，韓 義，等.基于MBD的三坐標(biāo)檢測工藝系統(tǒng)構(gòu)建技術(shù)研究[J].制造業(yè)自動化，2017，39（2）：1-4.

[4]劉達(dá)新.基于三維CAD的智能三坐標(biāo)測量機(jī)檢測規(guī)劃系統(tǒng)的研究與開發(fā)[D].合肥：合肥工業(yè)大學(xué)，2009.

[5] 蔡 菲.工藝資源管理及應(yīng)用研究[D].武漢：武漢理工大學(xué)，2010.

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