基于加工能力模糊聚類的設(shè)備分組方法

周媛媛 ，田錫天 ，黃利江 ，辛宇鵬 ，馬光輝

（1.西北工業(yè)大學(xué)CAPP與制造工程軟件研究所，西安 710072；2.中航工業(yè)西安航空發(fā)動(dòng)機(jī)（集團(tuán)）有限公司，西安 710021）

工藝設(shè)計(jì)是連接產(chǎn)品設(shè)計(jì)和制造的橋梁，是生產(chǎn)制造的前提。加工設(shè)備的確定是工藝設(shè)計(jì)的重要步驟之一。工藝人員往往是依據(jù)經(jīng)驗(yàn)確定加工設(shè)備，因此加工設(shè)備的選擇結(jié)果受工藝人員經(jīng)驗(yàn)水平的影響很大，不利于資源的合理利用。面向工藝設(shè)計(jì)，根據(jù)設(shè)備的能力對(duì)設(shè)備進(jìn)行合理分組，可以根據(jù)工藝要求在設(shè)備組中快速選擇符合要求的加工設(shè)備，提高設(shè)備選擇的準(zhǔn)確性、高效性，實(shí)現(xiàn)資源優(yōu)化配置，同時(shí)也減少人員參與，為工藝設(shè)計(jì)中的自動(dòng)化決策提供條件。

目前設(shè)備的分組方法主要概括為兩種：一種是按照設(shè)備的類別進(jìn)行分組的方法，如機(jī)械設(shè)備可分為金切機(jī)床、鍛壓設(shè)備和鑄造設(shè)備等，金切機(jī)床又可分為車床、銑床、刨床、鉆床等，以此類推繼續(xù)細(xì)化分類。這樣的設(shè)備分組方法，雖然有利于設(shè)備的管理，但是對(duì)于工藝設(shè)計(jì)來(lái)說(shuō)，同一加工特征可以用不同類別的設(shè)備進(jìn)行加工，同一設(shè)備也可以加工不同的加工特征，因此按類別對(duì)設(shè)備分組的方法不利于工藝設(shè)計(jì)過(guò)程中對(duì)設(shè)備的選擇。另一種方法是將設(shè)備構(gòu)建成制造單元，滿足某類零件的加工。近幾十年來(lái)，很多學(xué)者對(duì)制造單元的構(gòu)建技術(shù)做了大量研究：考慮加工時(shí)間、加工順序、生產(chǎn)批量等生產(chǎn)約束條件，建立了分別以加工成本最少、運(yùn)輸成本最少、物流總量最小、最佳設(shè)備及單元平衡等為目標(biāo)的數(shù)學(xué)模型[1]，通過(guò)聚類分析法、遺傳算法、神經(jīng)網(wǎng)絡(luò)、粒子群優(yōu)化算法等方法實(shí)現(xiàn)制造單元的構(gòu)建[2-5]。但大多數(shù)研究都是在已知零件可選設(shè)備的基礎(chǔ)上，對(duì)這些可選設(shè)備進(jìn)行組合，構(gòu)成完成某種加工任務(wù)的制造單元。而很少?gòu)牧慵庸ぴO(shè)備的選擇角度研究如何將設(shè)備進(jìn)行分組。石旭東等[6]根據(jù)設(shè)備具有的工藝元素，應(yīng)用擴(kuò)展模糊C-均值聚類算法（EFCM）對(duì)設(shè)備進(jìn)行分組，形成加工單元。這種分組方法使每個(gè)設(shè)備只能屬于一個(gè)加工單元，但有些設(shè)備的工藝元素卻無(wú)法全部包含在一個(gè)加工單元中。

本文采用加工能力元來(lái)描述設(shè)備的加工能力，形成設(shè)備與加工能力元的對(duì)應(yīng)關(guān)系，應(yīng)用區(qū)間數(shù)模糊C-均值（FCM，F(xiàn)uzzy C-means）聚類算法對(duì)加工能力元進(jìn)行聚類分組，進(jìn)而對(duì)設(shè)備進(jìn)行分組。每個(gè)設(shè)備根據(jù)所擁有的多種加工能力可以被分到不同的組中。

1 基于加工能力模糊聚類的設(shè)備分組方法

在機(jī)加工藝設(shè)計(jì)中，工藝人員根據(jù)加工能力選擇滿足工藝要求的加工設(shè)備。本文采用加工能力元對(duì)設(shè)備的加工能力進(jìn)行描述。加工能力元（MCE，Machining Capability Element）是以加工特征為核心的加工能力信息所形成的實(shí)體，可以表示為：mce=（A1，A2，…，AN），其中，A1是與零件加工特征有關(guān)的能力參數(shù)，如加工零件的種類、加工特征的類型、可加工零件的尺寸、可達(dá)到的精度（包括尺寸精度、形狀精度、位置精度、表面質(zhì)量）、生產(chǎn)批量等。圖1描述了加工能力元與設(shè)備的關(guān)系，可以看出每個(gè)設(shè)備的加工能力可以用多個(gè)加工能力元描述，同時(shí)每個(gè)加工能力元表達(dá)的加工能力也可以選擇不同的設(shè)備進(jìn)行實(shí)現(xiàn)。因此，根據(jù)加工能力對(duì)設(shè)備進(jìn)行分組，在工藝設(shè)計(jì)中可以依照零件的加工特征匹配相應(yīng)的加工能力元，進(jìn)而找到可選設(shè)備組，再根據(jù)具體情況從可選設(shè)備組中確定具體的設(shè)備對(duì)零件進(jìn)行加工。

設(shè)備分組過(guò)程如圖2所示，首先根據(jù)設(shè)備的加工能力提取相應(yīng)的加工能力元，并生成加工能力元與設(shè)備的對(duì)應(yīng)關(guān)系數(shù)據(jù)。然后將加工能力元根據(jù)可加工特征類型、可加工零件類別2個(gè)參數(shù)進(jìn)行粗略分類。可加工特征類型可分為平面、外圓柱面、孔、螺紋、鍵槽、齒面等；可加工零件類別可分為軸套類、輪盤(pán)類、叉架類、箱體類等。在對(duì)加工能力元分類的基礎(chǔ)上，根據(jù)加工能力元其余參數(shù)（如可加工零件的長(zhǎng)度、可達(dá)到的精度范圍、可達(dá)到的表面粗糙度、生產(chǎn)批量等）對(duì)加工能力元進(jìn)行模糊聚類分組。最后，在加工能力元模糊聚類的基礎(chǔ)上，根據(jù)加工能力元與設(shè)備的對(duì)應(yīng)關(guān)系對(duì)設(shè)備進(jìn)行分組。

圖1 加工能力元與設(shè)備的關(guān)系Fig.1 Relationship between machining capability elements and machines

圖2 設(shè)備分組過(guò)程Fig.2 Machine grouping process

2 加工能力元的模糊聚類模型

FCM聚類算法是一種應(yīng)用較為廣泛的基于劃分的聚類方法，該算法用模糊隸屬度來(lái)表示對(duì)象屬于某個(gè)類的程度，通過(guò)解的多次迭代得到目標(biāo)函數(shù)的優(yōu)化解。由于加工能力元參數(shù)的取值一般為區(qū)間數(shù)值型，傳統(tǒng)的FCM聚類算法無(wú)法滿足聚類要求，因此本文采用一種區(qū)間數(shù)FCM聚類算法對(duì)加工能力元進(jìn)行分組。

設(shè)有n個(gè)加工能力元MCE={mce1，…，mcen}，每個(gè)加工能力元表示為，j=1，2，…，n，N為加工能力元參數(shù)的個(gè)數(shù)。

已知：（1）n個(gè)加工能力元參數(shù)A1（加工零件的類別）的值相同，同時(shí)參數(shù)A2（加工特征的類型）的值也相同的，即；（2）參數(shù)A3，A4，…，AN的值為區(qū)間數(shù)值的形式，表示為k=3，4，…，N；j=1，2，…，n，其中。

將n個(gè)加工能力元分成c組，分組中心為V=（v1，v2，…，vc），其中，k=3，4，…，N，i=1，2，…，c。uij為每個(gè)加工能力元 mcej對(duì)各分組中心vi的隸屬度。建立目標(biāo)函數(shù)如下：

式中，d（vi，mcej）為加工能力元與分組中心之間的距離，即mcej和vi間的相似性度量，距離越小，相似度越高。本文引入?yún)^(qū)間數(shù)的距離公式[7]來(lái)度量加工能力元與分組中心之間的距離。

設(shè)區(qū)間數(shù)，其中，，則a與b間的距離定義為：

（1）當(dāng)a=b時(shí)，d（a，b）=0 ；

（2）當(dāng)a≠b時(shí)，

加工能力元與分組中心vi=間的距離可以表示為：

同理，任意兩個(gè)加工能力元和，j1,j2∈ {1,2,···,n} 間的距離可以表示為：

式（1）的迭代解為：

經(jīng)多次迭代求得每個(gè)加工能力元mcej對(duì)各分組中心vi的隸屬度uij后，根據(jù)最大隸屬度原則，mcej對(duì)哪個(gè)分組中心的隸屬度最大，就將其歸入那個(gè)分組中，即若μi0j=max{μij|i=1,2,···,c}，i0={1，2，…，c}，則將 mcej分到第i0組。

3 加工能力元模糊聚類分組過(guò)程

3.1 初始分組中心選擇

FCM聚類算法是一種局部搜索算法，為防止計(jì)算結(jié)果收斂于局部最優(yōu)解，需要合理選擇初始分組中心。本文采用文獻(xiàn)[8]中的一種改進(jìn)的最大最小距離算法，進(jìn)行初始分組中心的選擇。初始分組中心選擇步驟如下。

步驟1：確定分組數(shù)c，2≤c≤n，其中n為加工能力元的個(gè)數(shù)。

步驟2：計(jì)算任意兩個(gè)加工能力元間的距離d(mcej1,mcej2)，j1，j2=1，2，…，n。找出距離最大的兩個(gè)加工能力元和，即，作為第一和第二聚類中心；令r=2。

步驟3：如果c=2，則跳至步驟5；否則，計(jì)算除聚類中心外的任意加工能力元mcej與聚類中心的距離d(mcej,mceph)，j=1，…，n且mcej? {mcep1,···,mcepr}，h=1，…，r。 若且，則即為第r+1聚類中心；更新r=r+1。

步驟4：如果r=c，則跳至步驟5；否則跳至步驟3。

步驟5：將各加工能力元按最小距離原則分到各組中，即若n，則加工能力元mcej分到mcep所在的組中，此時(shí)得到一個(gè)粗分組。

步驟6：計(jì)算各粗分組的中心。

式 中，i=1，2，…，c;k=3，4，…，N ；j=1，2，…，n；Ni為第i組中加工能力元的個(gè)數(shù)；Gi表示第i組。V0=(v01,v02,···,v0c)即為初始分組中心。

3.2 加工能力元模糊聚類分組算法

加工能力元的模糊聚類分組算法如下。

步驟1：根據(jù)式（8）對(duì)數(shù)據(jù)進(jìn)行規(guī)范化處理，

式中，。例如，對(duì)參數(shù)A4（mm）的值[200，600]、[750，1000]、[1500，2000]進(jìn)行規(guī)范化處理，則（A4）max=2000， （A4）min=200，（A4）max-（A4）max=2000-200=1800。按公式（8）計(jì)算，規(guī)范化結(jié)果分別為 [0，0.2222]、[0.3056，0.4444]、[0.7222，1]。

步驟2：確定分組數(shù)c，給定一個(gè)小正數(shù)ε（如10-2，10-3，10-4，…），設(shè)置迭代計(jì)數(shù)b=0（分組數(shù)c可參照文獻(xiàn)[9]進(jìn)行確定）。

步驟3：用3.1節(jié)介紹的改進(jìn)的最大最小距離算法選擇初始分組中心vi(0)(i=1,2,···,c)。

步驟4：根據(jù)公式（5）計(jì)算每個(gè)加工能力元對(duì)各分組中心的隸屬度μij(b)(i=1,2,···,c;j=1,2,···,n)。

步驟5：根據(jù)公式（6）更新各分組中心vi(b+1)(i=1,2,···,c) 。

步驟6：若，則停止迭代，；否則令b=b+1，轉(zhuǎn)向步驟4。

步驟7：按照最大隸屬度原則，對(duì)加工能力元進(jìn)行分組。

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

本文從某企業(yè)葉片加工車間選擇15臺(tái)加工設(shè)備，以此為例說(shuō)明該分組方法的過(guò)程及實(shí)用效果。15臺(tái)設(shè)備對(duì)葉片類零件的葉身型面進(jìn)行加工的能力描述如表1所示。

首先根據(jù)這15臺(tái)設(shè)備的加工能力，總結(jié)出加工零件的類別為葉片，加工特征的類型為葉身型面的加工能力元共10個(gè)。加工能力元的參數(shù)為：加工零件的類別（A1）、加工特征的類型（A2）、特征的長(zhǎng)度范圍 （A3/mm）、輪廓度（A4/mm）、位置度（A5/mm）、表面粗糙度Ra（A6/μm）及適應(yīng)的生產(chǎn)批量（A7/件）。表2列出各加工能力元參數(shù)信息及對(duì)應(yīng)加工設(shè)備。

應(yīng)用模糊聚類算法對(duì)加工能力元分組。設(shè)分組數(shù)c=4，小正數(shù)ε=10-5。表3為經(jīng)計(jì)算所得初始分組中心，再經(jīng)6次迭代運(yùn)算得最終分組中心，如表4所示。表5列出加工能力元對(duì)最終分組中心的隸屬度。

根據(jù)最大隸屬度原則，由表5可得到加工能力元的分組結(jié)果。由表2可得加工能力元與設(shè)備的對(duì)應(yīng)關(guān)系。加工能力元及相應(yīng)設(shè)備的分組結(jié)果如表6所示。

（1）對(duì)單獨(dú)一個(gè)參數(shù)來(lái)說(shuō)，分組結(jié)果并沒(méi)有將參數(shù)值相近的加工能力元全部分到同一組中。例如，對(duì)于參數(shù)A5（位置度），mce4與mce6具有相同的值，但并沒(méi)有被劃分到同一組中。

表1 設(shè)備加工能力描述

表2 加工能力元參數(shù)及對(duì)應(yīng)設(shè)備信息

表3 初始分組中心各參數(shù)值

表4 最終分組中心各參數(shù)值

表5 加工能力元對(duì)各分組中心隸屬度

表6 加工能力元及設(shè)備分組結(jié)果

（2）綜合這5個(gè)參數(shù)，可以看出分到同一組的加工能力元各參數(shù)的值非常相近，具有很高的相似度；而分到不同組的加工能力元各參數(shù)的值相差很大，相似度很低。

（3）試驗(yàn)中，算法的迭代次數(shù)為6，小于10。

綜上所述，基于加工能力模糊聚類的設(shè)備分組方法，將相似性高的加工能力元分到同一組中，進(jìn)而將加工能力相似的設(shè)備劃分到同一設(shè)備組中，滿足設(shè)備分組的要求；通過(guò)選擇初始分組中心，使算法的迭代次數(shù)控制在10以內(nèi)，既提高了運(yùn)算效率，又保證了分組結(jié)果的穩(wěn)定性。

5 結(jié)束語(yǔ)

本文首先提出了基于加工能力模糊聚類的設(shè)備分組方法，引入加工能力元描述設(shè)備的加工能力。然后建立了加工能力元聚類分組的問(wèn)題模型，詳細(xì)討論了應(yīng)用區(qū)間數(shù)FCM聚類算法的加工能力元的聚類分組過(guò)程，給出了初始分組中心的選擇過(guò)程。最后實(shí)例驗(yàn)證表明，該方法能很好地滿足設(shè)備分組的需求，提高了設(shè)備的有效利用率，有利于資源的優(yōu)化配置。下一步應(yīng)重點(diǎn)研究如何制定有效的選擇策略，實(shí)現(xiàn)對(duì)設(shè)備的合理選用。

[1]王愛(ài)民，丁國(guó)智，寧汝新.制造單元快速構(gòu)建技術(shù)研究[J].北京理工大學(xué)學(xué)報(bào)，2006，26(10):85-99.

WANG Aimin，DING Guozhi，NING Ruxin.Rapid design technology for manufacturing cells[J].Transactions of Beijing Institute of Technology，2006，26(10):85-99.

[2]陳華偉，王愛(ài)民，寧汝新.制造單元構(gòu)建過(guò)程中的模塊化聚類分析[J].華中科技大學(xué)學(xué)報(bào)（自然科學(xué)版），2012，40(S2):87-90.

CHEN Huawei，WANG Aimin，NING Ruxin.Modularized cluster analysis during manufacturing cell formation[J].Journal of Huazhong University of Science and Technology(Natural Science Edition)，2012，40(S2):87-90.

[3]劉雪梅，朱麗君，李愛(ài)平，等.基于遺傳算法的生產(chǎn)車間制造單元構(gòu)建技術(shù)研究[J].制造技術(shù)與機(jī)床，2013(2):50-54.

LIU Xuemei，ZHU Lijun，Li Aiping，et al.Research of cell formation technology based on genetic algorithm[J].Manufacturing Technology and Machine Tool，2013(2):50-54.

[4]王國(guó)新，閻艷，寧汝新，等.模糊神經(jīng)網(wǎng)絡(luò)與啟發(fā)式算法相結(jié)合的制造單元構(gòu)建方法[J].計(jì)算機(jī)集成制造系統(tǒng)，2008，14(11):2175-2183.

WANG Guoxin，YAN Yan，NING Ruxin，et al.Manufacturing cell formation approach combing fuzzy neural network with heuristic algorithm[J].Computer Integrated Manufacturing Systems，2008，14(11):2175-2183.

[5]王雷，唐敦兵，許美健，等.基于粒子群優(yōu)化算法的制造單元聚類研究[J].計(jì)算機(jī)集成制造系統(tǒng)，2009，15(2):328-333.

WANG Lei，TANG Dunbing，XU Meijian，et al.Clustering of manufacturing cells based on particle swarm optimization[J].Computer Integrated Manufacturing Systems，2009，15(2):328-333.

[6]石旭東，付宜利，代勇，等.基于模糊聚類的設(shè)備分組技術(shù)[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào)，2001，33(3):287-290.

SHI Xudong，F(xiàn)U Yili，DAI Yong，et al.Machines grouping base on fuzzy clustering[J].Journal of Harbin Institute of Technology，2001，33(3):287-290.

[7]TRAN L，DUCKSTEIN L.Comparison of fuzzy numbers using a fuzzy distance measure[J].Fuzzy Sets and Systems，2002，130(3):331-341.

[8]單凱晶，肖懷鐵.初始聚類中心優(yōu)化選取的核C-均值聚類算法 [J].計(jì)算機(jī)仿真，2009，26(7):118-121.

SHAN Kaijing，XIAO Huaitie.A kernel C-means clustering algorithm with meliorated initial center .Computer Simulation，2009，26(7):118-121.

[9]周世兵，徐振源，唐旭清.新的K-均值算法最佳聚類數(shù)確定方法[J].計(jì)算機(jī)工程與應(yīng)用，2010，46(16):27-31.

ZHOU Shibing，XU Zhenyuan，TANG Xuqing.New method for determining optimal number of clusters in K-means clustering algorithm[J].Computer Engineering and Applications，2010，46(16):27-31.