設(shè)備備件重復(fù)庫存自動處理算法的應(yīng)用與研究

余興武，鄭大元，韓鵬，楊明川

(北京奔馳汽車有限公司，北京 100176)

備件倉儲管理是指對備件進行的計劃、實施、考核的管理，備件管理為了保證生產(chǎn)過程連續(xù)均衡地進行，做好備件的采購、供應(yīng)、存儲、合理使用等工作；備件倉儲管理是對倉儲物資的入庫、出庫、結(jié)存等活動的切實有效控制。為了滿足備件倉儲的科學(xué)管理，越來越多企業(yè)引入了信息化ERP管理系統(tǒng)，然而備件倉儲系統(tǒng)主數(shù)據(jù)普遍存在料賬不準(zhǔn)確、重復(fù)備件等問題，嚴(yán)重影響備件采購決策，甚至造成呆料與缺料停工損失。

在理想情況下，不同備件應(yīng)該有不同的型號和訂貨號；同一種備件必須使用統(tǒng)一的備件信息。但由于實際工作的多變性和備件信息管理的不規(guī)范性，導(dǎo)致很多重復(fù)備件產(chǎn)生。

如何查找匹配出備件數(shù)據(jù)的重復(fù)特征是實現(xiàn)ERP管理系統(tǒng)備件主數(shù)據(jù)準(zhǔn)確而無重復(fù)的關(guān)鍵技術(shù)。

1 重復(fù)備件研究背景

1.1 重復(fù)備件特征

根據(jù)MRP Controller（物料管理控制員）以及庫房管理人員對備件倉儲管理的工作總結(jié)，備件的屬性標(biāo)識主要由型號和訂貨號，大致總結(jié)了以下重復(fù)備件的可能性。

（1）型號和訂貨號一樣，但分配的物料號不一樣。

（2）型號和訂貨號填寫不規(guī)范，可能是包含關(guān)系，如兩個備件型號分別是6005-2RSH和SKF:6005-2RSH。

（3）型號和訂貨號使用符號不統(tǒng)一，如6005-2RSH和6005/2RSH，有可能存在“-”“/”“_”等混用的情況，但主體內(nèi)容一樣。

1.2 重復(fù)備件數(shù)據(jù)匹配算法研究現(xiàn)狀

相似度查詢是計算機學(xué)科中的一個重要問題，它的應(yīng)用遍及多個領(lǐng)域，例如，數(shù)據(jù)庫、數(shù)據(jù)集成、互聯(lián)網(wǎng)、數(shù)據(jù)挖掘等。林學(xué)民、王煒利用集合和字符串進行分析和歸類，研究數(shù)據(jù)的重復(fù)特征的關(guān)鍵算法；李星毅等研討的數(shù)據(jù)集合中相似重復(fù)記錄匹配算法，通過設(shè)置不同字段不同的權(quán)值，分組重復(fù)多次計算各個關(guān)鍵字段的相似度，可以有效解決相似重復(fù)記錄數(shù)據(jù)的問題；姜華、韓安琪等提出了一種改進的編輯距離相似度算法，解決了編輯距離標(biāo)準(zhǔn)算法在求解相似度過程中只考慮編輯操作次數(shù)，未考慮字符串包含關(guān)系對重復(fù)度匹配結(jié)果的影響，實現(xiàn)字符串重復(fù)相似度計算的高準(zhǔn)確性。

根據(jù)重復(fù)備件的特征，總結(jié)前人研究成果，本文提出一種基于編輯距離相似度和字符相似度算法相結(jié)合匹配算法，可以準(zhǔn)確而迅速得找出系統(tǒng)中重復(fù)備件數(shù)據(jù)，保證ERP系統(tǒng)中備件主數(shù)據(jù)的準(zhǔn)確性，優(yōu)化備件存儲結(jié)構(gòu)，降低備件采購成本。

2 編輯距離相似度和字符相似度算法

2.1 編輯距離相似度算法

編輯距離：兩個字符串r和s之間的編輯距離(記作ed(r,s)或ED(r,s))是通過使用三種編輯操作形式，刪除、插入或者替換單個字符，將字符串r轉(zhuǎn)化為字符串s的所需要的最少編輯操作個數(shù)。如果字符串r和s的編輯距離越大，說明字符串r和s越不相似，反之相反。

標(biāo)準(zhǔn)化編輯距離：字符串r和字符串s的標(biāo)準(zhǔn)化編輯距離sed公式如下，sed的取值范圍為[0,1]：

計算兩個字符串r和s的編輯距離相似度，采用標(biāo)準(zhǔn)編輯距離動態(tài)規(guī)劃計算方法，時間復(fù)雜度為O(|r|*|s|)，空間復(fù)雜度為O(min(|r|，|s|))。

建立|r|+1行|s|+1列的矩陣D，計算兩個字符串之間的編輯距離，其中初始化D[i][0]=i，0≤i≤|r|，D[0][j]=j，0≤j≤|s|，然后我們可以迭代計算D[i][j]，1≤i≤|r|，0≤j≤|s|，按照下邊公式：

其 中，如 果r[i]=s[j]，δ=0；否 則δ=1。最 終D[|r|][|s|]為字符串r和s之間的編輯距離。

2.2 字符相似度算法

由于備件主數(shù)據(jù)重復(fù)特征較復(fù)雜，標(biāo)準(zhǔn)編輯距離算法在兩個字符串長度差不多的情況下效果較理想，但重復(fù)備件特征字符串常常是包含關(guān)系，字符串長度可能差異巨大，使用編輯距離相似度算法達不到相關(guān)高效高精度匹配的結(jié)果，因此引用字符相似度算法。

字符相似度：兩個字符串r和s，長度分別為L1和L2，分別拆分成單個字符集合r[L1]和s[L2]，定義三種字符串相似度組合：

（1）字符集合r[L1]和s[L2]每個字符元素互相包含所占百分比，字符集合r[L1]有a個包含于字符集合s[L2]；字符集合s[L2]有b個包含于字符集合r[L1]；相似度charSimilarRate1計算公式如下：

生理學(xué)源自于人體解剖生理學(xué)，它是將人體解剖學(xué)、生理學(xué)、組織胚胎學(xué)等科學(xué)進行有機融合、重組而形成的一門綜合性學(xué)科.該學(xué)科的前沿發(fā)展很快,如何在新的條件下，在創(chuàng)建跨學(xué)科、多層次人體解剖生理學(xué)教學(xué)和實驗課的研究與實踐中進行教學(xué)改革, 就成為當(dāng)下亟待解決的問題了.另外，在生理學(xué)的教學(xué)中,既要結(jié)合結(jié)構(gòu)來學(xué)習(xí)功能(與組織胚胎學(xué)、解剖學(xué)的關(guān)系),還要進行正常生理功能和病理現(xiàn)象之間的多層次聯(lián)系(與病理生理學(xué)、藥理學(xué)、臨床醫(yī)學(xué)等之間的關(guān)聯(lián)),這也是生理學(xué)課程學(xué)習(xí)中的重要問題.基于上述原因，本課程存在教與學(xué)之間各自所具有不同程度的難點.

（2）字符集合r[L1]和s[L2]每兩個相鄰字符元素互相包含所占百分比；字符集合r[L1]有i個兩字符相鄰包含于字符集合s[L2]；字符集合s[L2]有j個兩字符相鄰包含于字符集合r[L1]；相似度charSimilarRate2計算公式如下：

（3）字符集合r[L1]和s[L2]每三個相鄰字符元素互相包含所占百分比；字符集合r[L1]有x個三字符相鄰包含于字符集合s[L2]；字符集合s[L2]有y個三字符相鄰包含于字符集合r[L1]；相似度charSimilarRate3計算公式如下：

通過字符相似度可以有效查詢匹配出字符長度差異較大且多重包含關(guān)系，提高重復(fù)備件查詢匹配的覆蓋率。

3 重復(fù)備件處理系統(tǒng)開發(fā)

3.1 系統(tǒng)開發(fā)技術(shù)

系統(tǒng)開發(fā)采用JAVA編程語言，運用了軟件工程思想、面向?qū)ο蟮募夹g(shù)來進行分析、設(shè)計和實現(xiàn)，系統(tǒng)包含軟件客戶端、局域網(wǎng)服務(wù)器和數(shù)據(jù)庫三部分。系統(tǒng)框架如圖1所示。

圖1 系統(tǒng)框架

3.2 系統(tǒng)實現(xiàn)效果

重復(fù)備件處理系統(tǒng)的基本功能包括備件主數(shù)據(jù)批量存儲、重復(fù)備件查詢匹配算法選擇、查詢匹配參數(shù)設(shè)置、導(dǎo)出結(jié)果等。

（1）批量查詢匹配重復(fù)備件，如圖2所示。

圖2 批量查詢匹配重復(fù)備件

①選擇相似度查詢算法——距離相似度或字符相似度，設(shè)置相應(yīng)算法的相似度百分比；

②輸入批量查詢型號或訂貨號；③批量查詢匹配重復(fù)備件結(jié)果。

（2）備件主數(shù)據(jù)全自動查詢匹配重復(fù)備件

備件的特征參數(shù)是型號和訂貨號，系統(tǒng)支持所有備件主數(shù)據(jù)交叉智能查詢匹配重復(fù)備件功能。查詢結(jié)果如圖3所示。

圖3 備件主數(shù)據(jù)全自動查詢匹配重復(fù)備件

4 重復(fù)備件處理

4.1 重復(fù)備件處理流程

重復(fù)備件處理主要負(fù)責(zé)人是備件控制工程師和庫房管理員，其流程角色和職責(zé)如圖4所示。

圖4 重復(fù)備件處理流程角色和職責(zé)

4.2 重復(fù)備件處理結(jié)果

通過使用編輯距離算法和字符相似度算法分析備件的重復(fù)特征，將ERP設(shè)備備件主數(shù)據(jù)重復(fù)庫存率從15%降低到1%以內(nèi)，處理重復(fù)備件產(chǎn)生的經(jīng)濟效益達2000萬元，實現(xiàn)了ERP系統(tǒng)中備件主數(shù)據(jù)的準(zhǔn)確性，優(yōu)化了備件庫存價值。

5 結(jié)語

本文對企業(yè)的ERP系統(tǒng)中備件主數(shù)據(jù)特征進行分析研究，使用編輯距離和字符相似度算法，開發(fā)重復(fù)備件處理系統(tǒng)，匹配出重復(fù)備件并批量自動處理，杜絕重復(fù)備件的產(chǎn)生，保證ERP系統(tǒng)中備件主數(shù)據(jù)的準(zhǔn)確性，優(yōu)化備件存儲結(jié)構(gòu)，降低備件采購成本。通過實踐證明，本文所研究的重復(fù)物料查詢匹配算法以及自主開發(fā)的重復(fù)物料處理系統(tǒng)，可以廣泛應(yīng)用于ERP系統(tǒng)重復(fù)物料處理的問題。