基于数据挖掘的通用物料清单重构方法研究

计算机集成制造系统

ComputerIntegratedManufacturingSystems

Vol.14No.2Feb.2008

文章编号:1006-5911(2008)02-0315-06

基于数据挖掘的通用物料清单重构方法研究

朱海平,王忠浩,张国军,邵新宇

(华中科技大学数字制造装备与技术国家重点实验室,湖北 武汉 430074)

摘 要:为有效地重构新型的通用物料清单,提出了基于数据挖掘的通用物料清单重构过程,运用赋权无序树形图表示产品物料清单实例,基于最小赋权对称相异度给出了相似物料清单实例之间的相似度度量算法;基于物料清单实例之间的相似度度量结果,采用k-Means聚类方法对物料清单实例进行聚类。重构后的通用物料清单来自大量的客观历史物料清单数据,其适应性和配置能力将大大改进。最后,给出该方法在国内某大型家电企业的应用实例,结果证实了其有效性。

关键词:物料清单;通用物料清单;数据挖掘;聚类分析中图分类号:TP391 文献标识码:A

Generalbillofmaterialreconfigurationmethodbasedondatamining

ZHUHai-ping,WANGZhong-hao,ZHANGGuo-jun,SHAOXin-yu

(StateKeyLabofDigitalManufacturingEquipment&Technology,Huazhong

UniversityofScience&Technology,Wuhan430074,China)

Abstract:ToeffectivelyreconfigureGeneralBillofMaterial(GBOM),reconfigurationprocessofGBOMbasedondata-miningwasproposed.BOMinstanceswererepresentedbytheweightedunorderedtreegraphgenerally,andthealgorithmofsimilaritymeasurementbetweentwosimilarBOMinstanceswerepresentedbasedontheminimumweightedsymmetricdifference.Intermsoftheresultsofthesimilaritymeasurement,allthetypicalBOMinstanceswereclusteredbasedonthek-Meansclusteringmethod.SincethereconfiguredGBOMsresultscamefromlargea-mountofsubjectivehistoricalBOMdata-resource,itsadaptabilityandconfigurationabilitywereimprovedeffective-ly.Finally,acasestudyofitsapplicationinalargedomesticelectricalappliancecorporationwaspresentedtoillus-tratetheeffectivenessofabove-mentionedmethod.

Keywords:billofmaterial;generalbillofmaterial;datamining;clusteringanalysis

0 引言

在当今的市场竞争环境下,企业必须做到既能满足不同客户群的差异需求,又能使产品体系通用性最大化。大规模定制(MassCustomization,MC)思想

[1]

个针对特定客户定制的单一产品物料清单(BillofMaterial,BOM)。尽管在产品族设计的早期已经定义了通用BOM[2](GenericBOM,GBOM)并设定了配置规则,但随着因客户需求变化而导致的BOM数据不断增加,原有GBOM的合理性和有效性会大大降低。因此有必要根据历史的BOM数据,通过有效的途径客观地重构出新型的GBOM,

正是在这样的背景下提出的。目前,在许多

家电和汽车企业的软件系统中,都存在着成千上万

收稿日期:2005-12-22;修订日期:2007-07-30。Received22Dec.2005;accepted30July2007.

基金项目:国家自然科学基金资助项目(50575084,50675082)。Foundationitem:ProjectsupportedbytheNationalNaturalScienceFounda-tion,China(No.50575084,50675082).

作者简介:朱海平(1975-),男,湖南长沙人,华中科技大学数字制造装备与技术国家重点实验室讲师,博士,主要从事制造系统建模、数据挖掘

等的研究。E-mail:haipzhu@263.net。

316

计算机集成制造系统第14卷

以适应更加复杂多变的客户定制需求。

数据挖掘方法(如聚类分析和关联分析)已被广泛而成功地应用到工程设计领域中,文献[3]提出了面向产品族设计的数据挖掘方法,通过将产品族细分成产品子族,分析每个产品子族与不同客户需求群和某个切分市场之间的关联关系,并基于关联规则挖掘找到不同时间段内的客户需求与产品子族之间的关系;文献[4]提出了基于无序树的BOM比较算法,指出任意两个BOM之间的相似度/相异度度量方法是进行BOM聚类的基础;文献[5]提出了构造支持变形设计的GBOM的数据挖掘方法,核心内容就是经典的k-Means聚类方法;文献[6]提出了基于赋权有向图的产品结构表示方法,并将其运用到产品结构中的从属关系判断、单套件数求解和产品结构比较。本文的思想则是将数据挖掘方法应用到GBOM的重构过程中来,在对大量BOM实例进行比较的基础上,通过BOM的聚类来实现GBOM的重构。

定义1 赋权无序树形图T由三元组(V,E,W)组成,其中:

1)V={v1,v2,,,vn}是一个有限非空的集合,V的元素是图D的顶点集合,表示组成产品的/件0或者BOM中的节点,V中元素数量为n。

2)E={3vi,vj4}是V中不同元素的无序对偶集合,其中viXvj。这些对偶称为T的无向弧,表示/件0与/件0之间的从属关系或者BOM中连接两节点之间的边;入度为0节点的是根,即产品名称;出度为0节点的是末端件,表示具体产品的零部件组成。

3)W={w(vi,vj)}={wij}是一个非负整数集合,wij表示父节点i包含子节点j的数量,称为权数。

定义2 与个性化客户定制对应的零部件组成称为BOM实例。BOM可以用子装配件、购买件及它们之间的关系组成的赋权无序树形图模型来表示,该模型的末端件表示BOM实例的具体零部件组成。此外,BOM实例也可以认为是已经被购买的产品所对应的BOM实体。购买件和子装配件分别与赋权无序树形图中的顶点、BOM中的节点相对应。

定义3 BOM实例用邻接矩阵的形式表示为A=[wij|1[i,j[n],显然A为稀疏方阵。在比较不同规模的BOM时,需要扩充邻接矩阵的行和列,使两个邻接矩阵维数相同。

在一般的产品结构比较中,尽管组成父件的子件数量不同,但只要被比较的两个BOM父件与子件内容和拓扑结构相似,仍认为两种BOM是相似

1 基于数据挖掘的通用物料清单重构过程

基于数据挖掘的GBOM重构过程如图1所示。首先由于数据源来自多个信息系统,如企业资源计划(EnterpriseResourcePlanning,ERP)和产品数据管理(ProductDateManagement,PDM)等,BOM数据可能存在不一致的情况,要对数据源进行预处理;然后,采用文本挖掘词频率计算和BOM项值的泛化技术,对一定数量的典型产品BOM实例进行简化;接着对适当简化后的BOM实例进行聚类,划分新的簇;基于每个簇中的BOM实例采用子树重建的方法构造新的GBOM,最后为GBOM定义新的配置规则,完成GBOM的重构。 从图1可以看出,BOM实例的相似性比较和BOM的聚类分析是其中两个最为关键的步骤,下面对这两个步骤进行深入探讨,其中BOM的形式化描述是研究的基础。

2 物料清单实例的相似性比较及物

料清单聚类分析方法

2.1 基于赋权无序树形图模型的物料清单

表示方法 在研究BOM实例的相似性比较算法之前,先根据图论相关知识作如下定义。

第2期朱海平等:基于数据挖掘的通用物料清单重构方法研究

317

的。因此可设wij=0或1,则父件与子件在数量上的关系可由两者之间的无向弧表示,此时BOM的赋权无序树形图简化为二元组T=(V,E)。

定义4 设u是有序树形图T的任一顶点,以u为根,u及所有子节点构成的顶点集记为Vc,u到这些节点的边构成的集合记为Ec,则T的子图Tc(Vc,Ec)称为以u为根的子树。

定义5 包含一个父节点和一系列子节点,且构成该子树的子节点可能是或者不是叶节点,这种子树称为一般子树,记为Gsub=(Vg,Eg);由一个父节点和一系列子节点组成,且其子节点都是叶节点,这种子树称为末端子树,记为Tsub=(Vt,Et)。示例如图2所示。

变,通过对树T2的邻接矩阵A2进行行变换或列变换,变换方式为n!,则可以找到T1和T2之间的最小拓扑差异

minT1ÝT2=min(j=1

n!

|A1-A2|)。n2(3)

|A1-A2|越小,表明对称相异邻接矩阵的稀疏度越小,T1和T2之间的拓扑差异也越小。

BOM的差异比较不是寻找完全匹配的BOM,而是将具有相似形式和内容的BOM划分到相同的聚类中,以构成针对不同产品族的GBOM。上述对称相异度仅反映了BOM在拓扑结构上的相似性,没有体现BOM内容上的相似性,因此存在局限性。下面提出最小赋权对称相异度的概念,它综合考虑了拓扑结构和内容两方面的相似性,定义公式如下:minT1ÝT2=min(j

1w1-i,2-j@x1-i,2-j)。(4)

n2T1-6,T

i2-j

1-i

其中w1-i,2-j表示一般子树T和T2-j的叶节点

(具体零部件)上的相似权重,它体现了BOM在内容上的相似程度,满足0[w1-i,2-j[1,是递减的模糊函数。零部件在设计结构、功能和制造方面的相似度度量方法在许多文献中都有叙述,特别是在成

定义6 给定两个赋权无序树形图T1=(V1,E1)和T2=(V2,E2),T1和T2的对称相异度定义为

[4]

组技术中有更有效的方法。如果两个零部件之间完全相同,则w1-i,2-j=0;如果两个零部件完全不同,则w1-i,2-j=1。x1-i,2-j表示一般子树T1-i和T2-j的匹配情况,如果两个子树能匹配,则x1-i,2-j=1,否则x1-i,2-j=0。对比式(3)和式(4)可以看出,式(3)只是计算两个树中最小的不能匹配的边的个数;式(4)则将末端子树的叶节点(零部件)相似度进行累计,找到最小赋权双向对称一般子树的差异,最后得到两个BOM之间的最小赋权对称相异度。2.2 基于最小赋权对称相异度的物料清单实例相

似性比较算法

基于最小赋权对称相异度的BOM实例相似性比较算法如图2所示。

输入:两个BOM实例树T1和T2。T1-i|Pi=1,,,n表示T1的一般子树,其对应的子节点集合为C(ai1,,,aik),i表示T1-i的根节点;T2-j|Pj=1,,,m表示T2的一般子树,其对应的子节点集合为D(bj1,,,bjl),j表示T

2-j

T1ÝT2=((V1GV2),(E1GE2)-(E1HE2))。(1)

用A1,A2分别表示T1和T2的邻接矩阵,用D12=|A1-A2|表示对称相异邻接矩阵。显然D12也是稀疏矩阵,定义稀疏度S12为两个BOM之间的相异度,即

T1ÝT2D^12

S12=。2=|V1GV2|n2BOM实例之间的相似度越大。

通常在BOM差异比较中,要同时关注BOM拓扑结构和BOM内容。由于BOM是人为构建的数据结构,其自身存在拓扑结构的不一致,导致BOM编辑(移动、删除和增加)算法开销特别大,这也是已有的BOM差异比较方法的不合理之处。如果对树T1和T2采用相同的方式来遍历(如先序遍历)并分别构造邻接矩阵,且树T1的邻接矩阵A1保持不

(2)

式中D^12为D12中的非零元素个数,S12越小,两个

的根节点。

输出:T1和T2的最小赋权对称差异度。图3

318

计算机集成制造系统第14卷

所示的流程由三个主要模块组成:¹完全末端树匹配,识别并匹配两个一般子树中的末端子树,将完全匹配即子树拓扑结构和节点值相同的子树叶节点删除;º双向权重相似度累计,对新的一般子树,采用自底向上的方法将一般子树的子节点(叶节点)的相似度权重进行累计,以得到两个BOM实例中一般

子树成对双向比较值,并将结构存入二维数组中;»最小赋权双向匹配子树搜索,固定一个BOM树,对于其所有的一般子树,在另一个BOM树的一般子树中找出具有最小赋权的匹配对,并将权重累计,以得到最小赋权对称相异度。

2.3 基于k-Means方法的物料清单聚类算法

BOM实例的相似性比较为实例的聚类提供了理论基础,BOM的聚类分析从全局上对BOM数据进行一次整理,重新生成若干GBOM,它可以优化BOM的数据结构,大大减少数据的冗余量。BOM实例聚类算法主要考虑几个方面:¹BOM实例数量巨大;º产品族差别不大;»BOM实例的相异度度量方法是针对相似BOM实例而言。如果BOM实例之间的差异较大,其比较方法将失去意义。考虑到基于k-Means的聚类方法[7]具有下面的特性:¹处理大量的数据集时,相对可伸缩和高效;º计算复杂度相对较低。因此下面采用基于k-Means方法对BOM实例进行聚类分析。

簇的数目k的选取直接决定聚类结果,而k与产品族的数目相同,每个簇中的BOM实例可认为

由一个GBOM派生,而一个GBOM通常对应一个产品族。产品族的增加和减少势必造成产品平台数量、产品变量的变化,最终导致效率和成本均衡状态变化,因此k的确定由已有产品族的数量k0为标准,不能无约束地增加和减少。

针对N个BOM实例,基于k-Means方法的BOM聚类算法如下:

步骤1 BOM实例两两进行相似度计算,得到BOM实例间的最小对称相异度,并构建相异度矩阵Mn@n,矩阵元素mij|i,jI[1,2,,,N]表示BOMi和BOMj之间的最小赋权对称相异度,显然Mn@n的对角线元素为1,且为对称矩阵,因此共需要计算N@(N-1)/2次。

步骤2 对相似度矩阵进行标准化,计算其传递闭包。

第2期朱海平等:基于数据挖掘的通用物料清单重构方法研究

319

步骤3 选择相似度阈值,建立Boolean等价矩阵。

步骤4 进行模糊聚类,选取聚类数目k,k满足min|k-k0|,其对应的聚类作为初始簇Ci,i=1,,,k,k0为初始簇数目。

步骤5 计算初始簇Ci的平均值mk,得到聚类中心。

步骤6 计算每一个BOM实例B与聚类中心mk的距离,并重新划分新的簇,如果满足E=min6Ni

i=1k

BIC

便,因此公司希望能在ERP中也实现BOM的配置管理,同时还希望能对PDM中现有的GBOM进行调整优化。针对这两个需求,笔者利用ERP中的制造BOM数据进行了GBOM的重构工作。其中的第一步就是进行BOM实例的相似性比较,下面以型号BCD200AK和BCD175S的两个BOM实例为例进行说明。

首先采用泛化方法对BOM实例进行预处理,如对搁物架采用泛化处理,不管何种搁物架都视为一种类型的搁物装置。两个BOM构建对应的邻接矩阵如图4所示,由式(2)得到稀疏度S为6/(17@17)=0.027。下面将根据如图3所示的算法来计算最小赋权对称相异度,过程如下:

(1)完全末端树匹配 寻找末端子树,并进行树匹配,在BOM1和BOM2中都不存在严格意义上的末端子树,如不进行泛化处理,搁物架q和搁物架qc都可视为末端子树,只是不匹配而已。发泡箱体f尽管在两个BOM中都是叶节点,但是f的父节点不同,因此也不能进行匹配。

(2)双向权重相似度累计 先看门体a和门体ac,两者的不同之处在于铰链e,最小距离为1。箱体b和门体ac的不同之处在于上门c,d和发泡箱体f,故最小距离为3。箱体b和发泡箱体f的最小距离为1。由于gc含有温控器,而g没有;压缩机i和压缩机ic只是功率不同,设相似度为012;冷凝器j和冷凝器jc的相似度设为011,则制冷模块g和gc之间的最小距离为113。同理可得搁物模块l和lc的最小距离为2,等等,并将上述的最小距离存储到二维数组中。

(3)最小赋权双向匹配子树搜索 对于BOM1,在BOM2中寻找最小的匹配子树,如对于子树a,在二维数组中找到最小距离为1,即:

Min(Distance(a,{ac,f,gc,lc}))=Distance(a,ac)=1;

Min(Distance(g,{ac,f,gc,lc}))=Distance(g,gc)=1+0.1@1+0.2@1=1.3;

Min(Distance(b,{ac,f,gc,lc}))=1;Min(Distance(l,{ac,f,gc,lc}))=2;sum=5.3。

根据式(4)得到的最小赋权对称相异度为0.0183。

6

+B-mk+,即E收敛,则聚类结束;

i

2

否则重新执行步骤6。其中E表示所有平方误差的总和,+#+是欧氏空间距离,Ni为簇i中的BOM实例个数。

BOM实例聚类完成后,每个簇中的BOM实例可以清晰地反映出拓扑结构和叶节点对应的零部件组成,采用子树重建的方法构造新的GBOM。一般子树重建实质上是BOM结构分解的逆过程。重建后的GBOM可能有多种形式,通过与原有的GBOM对比,可以调整部分属性和拓扑结构,以获得改进后的GBOM。由于簇中的产品BOM具有一定的相似性,它们都可以由一个通用产品结构派生,用改进后的GBOM体现出来。

3 应用实例

本文所提出的GBOM重构方法在广东海信科龙电器股份有限公司冰箱分公司中得到了初步应用验证。该分公司生产十几种型号的冰箱,其设计BOM和制造BOM数据分别存在于PDM系统(TeamcenterEngineering)和ERP系统(SAPR3)中。目前,利用PDM的配置管理功能定义了十几个设计GBOM,每一个GBOM对应一个产品型号,如BCD200AK,BCD238,BCD260等。但这些GBOM之间的关系却比较混乱,例如产品代号分别为BCD200AK-01F02和BCD200/E-01E11两个BOM实例,它们尽管结构上差异不大,但却属于两个不同GBOM(BCD200AK和BCD200/E),而另外两个差异很大的实例却可能属于同一个GBOM。ERP的配置管理功能尚未利用,制造BOM均以单一BOM的形式存在,其数量已达几千个,管理起来相当不

320

计算机集成制造系统第14卷

在SAPR3中选取50个BOM实例(每个实例具有不同的产品代号)进行聚类分析,这50个实例分别来自于五个产品型号:BCD200AK,BCD200,BCD175P,BCD200/E和BCD175S。各型号的实例数目均为10。按照上述相似性比较步骤,共做50@(50-1)/2=1225次计算,得到相异度矩阵M50@50,然后取簇数k=5,利用k-Means方法进行模糊聚类分析,最终得到五个新BOM簇(GBOM),每簇包含的元素个数分别为8,11,7,11,13,经分析发现,原来属于BCD200AK的两个BOM实例由于与BCD200AK中的其他元素差异较大,被划分到BCD200和BCD200/E型号中,同样BCD175P和BCD175S中的五个实例也发生了移动,结果如表1所示。这说明经过GBOM重构后,GBOM的组成进行了优化,结果是GBOM内部的相似性得到增强,而不同GBOM之间的相似性被减弱。

表1 GBOM聚类后归属发生变化的产品代号

实例的产品代号BCD200AK-01F02BCD200AK-01F10BCD175P-01E08BCD175P-01E09BCD175P-01E13BCD175P-01E20BCD175S-02F04

原属产品型号(GBOM)BCD200AKBCD200AKBCD175PBCD175PBCD175PBCD175PBCD175S

聚类后所属的新

GBOMBCD200/EBCD200BCD175SBCD175SBCD175SBCD175SBCD175P

4 结束语

以GBOM为核心的面向大规模定制产品族设计的关键取决于GBOM的配置灵活性和准确性。本文提出了基于数据挖掘的GBOM重构方法,通过改进最小赋权对称相异度度量算法,从大量的历史BOM数据中客观地进行BOM实例聚类,为面向大规模定制的产品族设计和优化提供了新途径。

(下转第385页)

第2期侯琳琳等:基于超模博弈的多零售商价格竞争的均衡分析

385

此,笔者将针对以上两点不足进行更深入地研究,并另文予以说明。参考文献:

[1] BIRGEJR,DROGOSZJ,DUENYASI.Settingsingle-period

optimalcapacitylevelsandpricesforsubstitutableproducts[J].InternationalJournalofFlexibleManufacturingSystems,1998,10(4):407-430.

[2] PADMANABHANV,PNGIPL.Manufacturercsreturns

policiesandretailcompetition[J].MarketingScience,1997,16(1):81-94.

[3] YAOZ,WUY,LAIKK.Demanduncertaintyandmanufac-turerreturnspoliciesforstyle-goodretailingcompetition[J].ProductionPlanning&Control,2005,16(7):691-700.[4] YAOZ,STEPHENCHL,LAIKK.Manufacturercsreve-nue-sharingcontractandretailcompetition[J].EuropeanJournalofOperationalResearch,2008,186(2):637-651.[5] BERNSTEINF,FEDERGRUENA.Decentralizedsupplychains

withcompetingretailersunderdemanduncertainty[J].Man-agementScience,2005,51(1):18-29.

[6] CACHONGP,LARIVIEREMA.Supplychaincoordination

withrevenue-sharingcontracts:strengthsandlimitations[J].ManagementScience,2005,51(1):30-44.

[7] MILGROMP,ROBERTSJ.Rationalizability,learning,and

equilibriumingameswithstrategiccomplementarities[J].Econometrical,1990,58(6):1255-1277.

[8] AMIRR.Supermodularityandcomplementarityineconomics:

anelementarysurvey[J].SouthernEconomicJournal,2005,71(3):636-660.

[9] TOPKISDM.Supermodularityandcomplementarity[M].

Princeton,N.J.,USA:PrincetonUniversityPress,1998.[10] RASMUSENE.Gameandinformation:anintroductionto

gametheory[M].WANGHui,BAIJinhui,WURenhao,transl.2nded.Beijing:BeijingUniversityPress,2003:364-367(inChinese).[拉斯缪森.博弈与信息)))博弈论概论[M].王 辉,白金辉,吴任昊,译.2版.北京:北京大学出版社,2003:364-367.]

统中多个零售商间的价格竞争问题,并引入了经济

博弈理论的最新研究进展)))超模博弈理论,证实此博弈属于超模博弈。基于此理论,证明了零售商价格竞争存在纯策略意义的纳什均衡,并给出了均衡价格的一些特点,而且证明了存在唯一纳什均衡价格的条件。最后,进行了比较静态分析,深入地探讨了契约参数对博弈均衡价格的影响,得出了零售商定价随契约参数变化的规律。但本文存在两个方面的不足:¹认为需求对价格的敏感程度是线性的,即假设零售商与价格相关的需求函数是线性的,并没有讨论一般函数形式下价格博弈的均衡情况;º并未在此基础上进一步探讨收益共享契约参数的设计问题,以更好地实现整个供应链系统的协调。因(上接第320页)参考文献:

[1] PINGH.Masscustomization)thenewfrontierinbusiness

competition[M].Press,1993.

[2] HEGGEHMH,WORTMANNJC.Genericbillofmaterial:

anewproductmodel[J].InternationalJournalofProductionEconomics,1991,23(5):117-128.

[3] AGARDB,KUSIAKA.Data-miningbasedmethodologyfor

thedesignofproductfamilies[J].InternationalJournalofPro-ductionResearch,2004,42(15):2955-2969.

[4] ROMANOWSKICJ,NAGIR.Oncomparingbillsofmater-i

als:asimilarity/distancemeasureforunorderedtrees[J].IEEETransactionsonSystems,ManandCybernetics)Part

Boston,Mass.,USA:HarvardBusiness

A:SystemsandHumans,2005,35(2):249-260.

[5] ROMANOWSKICJ,NAGIR.Adataminingapproachto

forminggenericbillsofmaterialsinsupportofvariantdesignactivities[J].ASMEJournalofComputingandInformationScienceinEngineering,2004,4(4):316-328.

[6] ZHANGGuojun,SHAOXinyu.Modelingandapplicationof

productstructurebasedonweighteddiagraph[J].ChinaMe-chanicalEngineering,2004,15(1):50-53(inChinese).[张国军,邵新宇.基于赋权有向图的产品结构建模及其应用[J].中国机械工程,2004,15(1):50-53.]

[7] HANJiawei,KAMBERM.Dataminingconceptsandtech-niques[M].SanFrancisco,Cal.,USA:MorganKaufmannPublisher,2001:227-230.