基于啟發(fā)式算法的檢測(cè)資源分配研究

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

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

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

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

1 檢測(cè)資源能力模型建立

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

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

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

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

2 檢測(cè)工藝過程節(jié)點(diǎn)圖構(gòu)建

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

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

圖2 某非線性檢測(cè)工藝描述

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

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

2.2 檢測(cè)工藝過程節(jié)點(diǎn)圖構(gòu)建

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

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

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

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

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

圖4 某零件的非線性檢測(cè)工藝路線圖

圖5 非線性檢測(cè)工藝路線節(jié)點(diǎn)圖

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

3 檢測(cè)工藝資源分配模型的建立

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

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

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

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

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

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

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

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

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

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

3.2 檢測(cè)工藝資源分配模型的建立

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

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

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

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

4 算法求解

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

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

算法的輸出是：①檢測(cè)資源分配信息；②最長(zhǎng)檢測(cè)時(shí)間；③總檢測(cè)成本。

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

4.1 基于成本的檢測(cè)工藝資源分配

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

其分配過程如圖7所示。

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

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

4.3 考慮時(shí)間約束的檢測(cè)工藝資源分配

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

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

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

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

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

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

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

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

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

圖10 檢測(cè)工藝路線圖

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

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

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

表1 檢測(cè)資源分類表

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

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

表2 檢測(cè)資源能力表

圖11 檢測(cè)工藝節(jié)點(diǎn)圖

表3 各道檢測(cè)工序總成本和所用時(shí)間表

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

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

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

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

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

5 結(jié)論

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

參考文獻(xiàn)：

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

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

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

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

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

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