计算机搜索算法在企业中的应用

计算机搜索算法在企业中的应用

动态联盟是促进瑞利制造的重要形式。制造企业寻求合作伙伴是动态企业联盟形成过程中的关键步骤。如果制造企业模型是定性模型,则搜索算法就是定性搜索算法;如果制造企业模型是定量模型,则通常首先采用定性搜索算法搜索出几种可行的企业联盟方案,然后再采用定量评价算法,从这几种方案中评出最佳联盟组成方案。其中,按照关键词进行企业-任务匹配的算法,就是一种典型的定性搜索算法,例如,我们熟知的Yahoo搜索方式。但是,现有的定性搜索方法不能全面满足企业的这一需求。因为采用关键词匹配方法进行搜索,给出的是满足搜索条件的所有潜在合作伙伴,由于无法按照企业希望的原则对搜索结果进行优先排列,如果搜索出的潜在合作伙伴数量多,面对如此大量的搜索信息,企业将无所适从。为此,有必要研究和提出针对制造企业寻求合作伙伴的定性搜索方法,满足企业组建动态联盟的特定需求。1能力-需求匹配原则按照行业特点,可以定义集合RB≜{rb1,rb2,…,rbh}为某个行业,或子行业的基本任务需求单元集,其中rbi(i=1,2,…,h)表示该行业的基本任务需求单元,针对不同的行业,基本任务需求单元有不同的行业解释。针对企业的某个任务需求为Rt(t=1,2,…,k),将该企业提出的任务用基本任务需求单元所构成的集合表示,就是Rt≜{rt1,rt2,…,rtm(t)},其中Rt⊆RB。按照行业特点,同样能够定义某个行业,或子行业的企业基本能力单元集合为CB≜{Cb1,Cb2,…,Cbh},其中Cbi(i=1,2,…,h)表示该行业企业基本能力单元。同样,针对不同的行业,基本企业能力单元有不同的行业解释。例如,模具行业或注塑模具子行业,基本企业能力单元可以是模具的设计能力、模具的工程分析能力、模具的数控加工能力、模具试模能力、模具型腔的热处理能力等。而铝型材制造行业,基本企业能力可以是精练、铝型材挤压模具的设计与制造、铝型材挤压生产线、氧化、喷涂、电泳等。行业内某个企业的能力可以表征为Cj(j=1,2,…,n),将该企业的能力用本行业企业基本能力所构成的集合表示,就是Cj≜{cj1,cj2,…,cjl(j)},其中Cj⊆CB。能力-需求匹配原则建立了RB与CB之间的一一对应的关系,cbi⇔rbi(i=1,2,…,h)。针对某个任务Rt,利用上述的匹配原则,可建立相应的解决该任务所必需的基本能力集合CT≜{ct1,ct2,…,ctm(t)},如果存在一个(或多个)企业,其能力集合分别为Ctj(j=1,2,…,s),使得CΤ⊆s∪j=1CtjCT⊆∪j=1sCtj,那么,称这些企业能力Ctj的组合(联合)覆盖了任务需求Rt。针对覆盖了任务需求Rt的某个s∪j=1Ctj∪j=1sCtj,定义它关于CT的冗余集为CRedΤ≜s∪j=1Ctj\CΤ。其中pT≜dim{CRedΤ}为冗余种类,且0≤pT≤dim{CB\CT}。而对应于∀cbi∈CRedΤ,覆盖s∪j=1Ctj冗余了qi次(即在s∪j=1Ctj中,有qi+1个Ctj中包含元素cbi)。因此,整个冗余集CRedΤ的最大冗余次数定义为qΤ≜maxcbi∈CRedΤ{qi},且0≤qT≤dim{CT}。这样,针对某个客户提出的任务Rt,如何按照能力-需求匹配原则,确定各种可能的企业组合,其相应能力的总和s∪j=1Ctj能覆盖该任务需求Rt,并按照优化准则Pa(a=1,2,…γ),对所有可能的能力覆盖进行排序。常用的优化准则(最小化目标):在所有满足条件CΤ⊆s∪j=1Ctj的企业组合s∪j=1Ctj中,寻找(1)具有最少企业数量s的企业组合s∪j=1Ctj,即p1=s;(2)具有最小冗余种类的企业组合s∪j=1Ctj,即p2=p;这样,可使客户在满足必要条件的企业组合中,通过定量评价的方法,确定合适的合作伙伴。2中小型企业企业能力集合的逻辑运算为了便于优化搜索,需要建立企业能力与行业基本能力单元的关系表(简称关系表),以便分析问题和建立算法。可以分别针对某个行业或子行业来建立相应的关系表。以该行业或子行业的企业基本能力单元集合CB≜{cb1,cb2,…,cbh}为表行中的项目;以该行业或子行业中每个企业的能力集合为表列中的项目,如果某个企业具有某种基本能力,则在相应的表格中的逻辑变量是“True”,反之为“False”,如表1所示。基本假设1:针对某个行业或子行业的企业基本能力单元集合CB中的任意一个企业基本能力单元cbt,至少存在一个企业,它拥有这种基本能力。即对∀cbi∈CB,∃Cj,使得cbi∈Cj。这一假设可称为能力完备性假设,即一个行业的整体一定具有完成所有该行业内所面临的需求任务。基本假设2:针对属于该行业的每个企业,必须至少具备一项该行业的基本能力单元,即任意一个企业的能力集合Cj为非空集合。这一假设可称为企业的行业特征假设。表1中每一行对应着每个企业的能力集合,每一列则对应着该行业中每个基本能力特征(或称技术特征)在本行业所有企业中的分布情况。该行业的任一需求Rt与企业能力的相互关系,都可以用关系表中CT包含的cbt所在的列表示,简称这些列是“属于”需求Rt的列。为了有效地分析算法,需要定义以下几种集类、子类、限制及关系表1中行与列的逻辑运算。定义某个行业的所有企业能力集合构成的集类为C≜{C1,C2,…,Cn},而其中任意j个集合所构成的子集类为Cji≜{Ci1,Ci2,…,Cij},所有仅包含CT中基本企业能力单元的那些企业能力集合构成的子集类为CT0。对∀cbi∈CcΤ≜CB\CT,所有仅包含CT中基本企业能力单元,又只包含cbi的那些企业能力集合所构成的子类为CT1(i);对∀cbi,cbj∈CcΤ,所有仅包含CT中基本企业能力单元,同时又只包含cbi和cbj的那些企业能力集合所构成的子集类为CT2(i,j),依此类推。显然,根据这些子集类的定义,它们彼此不相交。此外,CDΤ为CT中无法被CT0中所有集合的组合(联合)所覆盖的子集。(1)⊕|C1i|Cλ‚Cλ⊆CB。在子集类C1i≜{Ci}上,即在集合Ci所在的行中,仅属于子集Cλ列上的逻辑量联合进行“或”运算(行或),并将结果放入Cand列对应于Ci的行中,即做dim{Cλ}-1次“或”运算。(2)⊕|Cji|Cλ,其中j≥2。在子集类Cji=≜{Ci1,Ci2,…,Cij}上,每个Cil(l=1,2,…,j)所在行中仅属于子集Cλ的列上的逻辑量,与同一子集类中其他行中对应列上的逻辑量联合进行“或”运算(列或),结果放在Cor栏中相应的列上,即做(j-1)dim{Cλ}次“或”运算。(3)⊗|Cji|Cλ。在子集类Cji≜{Ci1,Ci2,…,Cij}上,每个Cil(l=1,2,…,j)所在的行中所有仅属于子集Cλ列上的逻辑量联合进行“与”运算,结果放在列的对应行中,即做j(dim{Cλ}-1)次“与”运算。(4)⊗|{Cor}|Cλ。在Cor所在的行上,所有仅属于子集Cλ列上的逻辑量联合进行“与”运算,结果放在cand列的对应行中,即做dim{Cλ}-1次“与”运算。定理1:s∪j=1Cij能覆盖任务需求Rt的充分必要条件是,两阶段逻辑运算⊕|Csi|CΤ‚⊗|{Cor}|CΤ的执行结果是“True”。证明:(1)必要性。如果s∪j=1Cij能覆盖任务需求Rt,则针对∀rbi∈Rt,其对应的cbi∈s∪j=1Cij。也就是说,∃Cij,使得cbi∈Cij,即Cij行中对应于cbi列上的逻辑量的值是“True”。因此,当执行联合“或”运算⊕|Csi|CΤ后,Cor栏中对应于cbi列上的逻辑量的值也一定是“True”。由于前面所针对的rbi∈Rt是任意的,这蕴含着在Cor栏与Rt中所有rbi∈Rt对应的cbi列上的逻辑量的值都是“True”。那么,执行逻辑运算⊗|{Cor}|CΤ的结果也一定是“True”。(2)充分性。如果运算⊕|Csi|CΤ的执行结果是“True”,则Cor栏中与Rt中所有rbi∈Rt对应的cbi列上的逻辑量的值都是“True”。也就是说,对所有这样的cbi,∃Cij,使得cbi∈Cij,即任务需求Rt的每个部分rbi,都在s∪j=1Cij中至少有一个企业具有相应的基本能力cbi满足要求,故s∪j=1Cij一定能覆盖任务需求Rt。定理2:针对任何需求Rt,一定存在一个企业组合能力覆盖s∪j=1Cij,其中所包含的企业个数不超过m(Rt)=dim{Rt}=dim{CT},即∃s,使得s≤m(Rt),m(Rt)是需求Rt中包含的元素个数。证明:根据基本假设,对∀rbi∈Rt,其对应的cbi(共有m(Rt)个)所在的列中至少有一个逻辑量的值是“True”,假设该列中所有值为“True”的逻辑量所在的行号集合为Nbi,那么Nbi非空;如果所有的Nbi彼此两两的交集都为空集,则在每个Nbi中选定一个行号,对应m(Rt)个Cij的联合能力一定可以覆盖需求Rt;如果存在某两个Nbi1和Nbi2,它们的交集非空,则从这一交集中选定一个行号,在其余的Nbi中每个选定一个行号,对应的m(Rt)-1个Cij的联合能力也一定可以覆盖需求Rt。定理3:任务需求Rt存在无冗余解的充分必要条件是两阶段逻辑运算⊕|CΤ0|CΤ(如果CT0只包含一个集元素,则该步运算就变为将该集所在行的逻辑量依次送入Cor所在的行),⊗|{Cor}|CΤ的执行结果是“True”。证明:(1)必要性。如果s∪j=1Ctj是能覆盖任务需求Rt的无冗余解,则CΤ=s∪j=1Ctj。对∀rbi∈Rt,其对应的cbi∈s∪j=1Ctj。也就是说,∃Cij,使得cbi∈Cij,即Cij行中对应于cbi列上的逻辑量的值是“True”,并且Cij∈CT0。因此,当执行联合“或”运算⊕|CΤ0|CΤ之后,Cor栏中对应于cbi列上的逻辑量的值也一定是“True”,而对∀cbi∈CcΤ,对应于cbi列上的逻辑量的值也一定是“False”。由于前面所针对的rbi∈Rt是任意的,这蕴含着在Cor栏中与Rt中所有rbi∈Rt对应的cbi列上的逻辑量的值都是“True”;那么,执行逻辑运算⊗|{Cor}|CΤ的结果也一定是“True”。(2)充分性。如果运算⊕|CΤ0|CΤ的执行结果是“True”,则Cor栏中与Rt中所有rbi∈Rt对应的cbi列上的逻辑量的值都是“True”,而对∀cbi∈CcΤ,对应于cbj列上的逻辑量的值也一定是“False”。也就是说,对所有这样的cbi,∃Cij,使得cbi∈Cij,即任务需求Rt的每个元素rbi,都在s∪j=1Cij中至少有一个企业具有相应的基本能力cbi满足它,故s∪j=1Cij一定能够覆盖任务需求Rt。3基于pi的搜索算法Algorithm(pi)|Cji|Cλ:说明该搜索算法是以pi为优化目标,并仅限于子集类Cji≜{Ci1,Ci2,…,Cij}所在的行上,以及那些属于子集Cλ的列上进行。(1)任务系统生成针对优化目标p1,提出如下搜索算法,简称Algorithm(p1)|C|CΤ。第一步:判断是否存在一个企业,它能够独立覆盖任务需求Rt;如果有,找出所有合格的企业序号,并放入数组qualification中,结束。否则执行第二步。以伪代码的形式表示,即:qualification=1;m=0;For(j=1,j<n+1,j++){ΙF(⊕|C1i|CΤ=“True”){m++;qualification[m]=j;}}IF(m>0)stop。第二步:判断是否存在两个企业,它们组合能够覆盖任务需求Rt;如果有,将找出的合格企业组合的序号组,放入数组qualification中,结束。如果满足要求的企业组合很多,当超过用户预先设定的个数M后,程序结束。否则执行第三步。以伪代码的形式表示,即:qualification=2;m=0;For(j1=1,j1<n,j1++){For(j2=2,j1<j2<n+1,j2++){⊕|C2i|CΤ；ΙF(⊗|{Cor}|CΤ=“True”){m++;qualification[m]=j1;m++;qualification[m]=j2;IF(m>2M)stop;}}}IF(m>0)stop。第三步:判断是否存在三个企业,它们组合能够覆盖任务需求Rt;如果有,将找出的合格企业组合的序号组,放入数组qualification中,结束。如果满足要求的企业组合很多,当超过用户预先设定的个数M后,程序结束。否则执行第四步。类似地这样做直到第m(Rt)步为止。根据定理2可知,一定存在能够覆盖任务需求Rt的企业组合。(2)算法1,cj[1控制】针对优化目标p2,提出如下搜索算法,简称Algorithm(p2)|C|CΤ。第一步:判断是否存在无冗余解,如果有,找出具有最小个数企业组成的无冗余企业组合,将解放入数组qualification中,结束。否则转向第二步,以伪代码的形式表示,即:m=0;For(j=1,j<n+1,j++){ΙF(⊕|C1j|CcΤ=“False”){m++;CT0[m]=j;}}⊕|CΤ0|CΤ;ΙF(⊕|{Cor}|CΤ=“True”){Algorithm(p1)|CΤ0|CΤ;}第二步:判断是否存在冗余类数为1的解,如果有,寻找冗余次数最小的企业组合。结果放在数组qualification中,结束。将部分解一与部分解二合并(集合的并运算),就得到最后解。否则转向第三步,其中CcΤ(i)≜CcΤ\Cji}。以伪代码的形式表示,即:For(i=1,i<h-u+1,i++){m=0;For(j=1,j<n+1,j++){ΙF(⊕|C1j|CDΤ=“True”AΝD⊕|C1j|CcΤ(i)=“False”){m++;CT1[i][m]=j;}}}For(i=1,i＜h-u+1,i++){⊕|CΤ1(i)|CDΤ；ΙF(⊗|{Cor}|CDΤ=“True”){Algorithm(p1)|CΤi(i)|CDΤ;部分解一Algorithm(p1)|CΤ0|{CΤ\CDΤ};部分解二}}第三步:判断是否存在冗余类数为2的解,如果有,寻找冗余次数最小的企业组合。结果放在数组qualification中,结束。如果满足要求的企业组合很多,当超过用户预先设定的个数M后,程序结束。否则执行第四步。类似地,最多做到第dim{CB\CT}步为止。根据冗余种类pT的性质0≤pT≤dim{CB\CT}可知,一定存在冗余类数不超过dim{CB\CT}的企业组合,能覆盖任务需求Rt。定理4:以上两种算法是关于企业总个数n的多项式算法。证明:针对算法一,第一步不超过n(dim{CT}-1)次“或”运算;n次加法运算;2n+2次赋值运算;n+1次“判断”运算。第二步不超过n(n-1)2dim{CΤ}次“或”运算;n(n-1)2(dim{CΤ}-1)次“与”运算;n(n-1)次加法运算;n(n-1)2(dim{CΤ}+3)+2次赋值运算;n(n-1)+1次“判断”运算。类似地,可以归纳地建立算法一直到第dim{CT}步的最大可能运算次数,它是一个n关于dim{CT}次方的代数多项式。由于CT⊆CB,则dim{CT}≤dim(CB)=h,而h是一个仅与行业和任务性质分类有关的固定常数,一般远远小于行业中的企业个数n,所以当n很大时,算法一的运算次数可表示为n关于dim{CT}次方的代数多项式,即算法一是多项式算法。针对算法二,第一步不超过n(dim{CB}-1)-dim{CT}次“或”运算;dim{CT}-1次“与”运算;n次加法运算;2n+2次赋值运算;n+1次“判断”运算;以及执行算法一一次的运算次数。第二步不超过ndim{CB\CT}(dim{CB}+dim{CT}-3)次“或”运算;dim{CB\CT}(n+dim{CT}-1)次“与”运算;ndim{CB\CT}次加法运算;ndim{CB\CT}(dim{CB}+dim{CT}-2)+dim{CB\CT}次赋值运算;dim{CB\CT}(3n+1)次“判断”运算;以及执行算法一2dim{CB\CT}次的运算次数。类似地,可归纳地建立算法二直到第dim{CB\CT}步的最大可能运算次数,它是一个n关于dim{CB\CT}次方的代数多项式。由于CT⊆CB,则dim{CB\CT}≤dim{CB}=h,而h是一个仅与行业和任务性质分类有关的固定常数,一般远远小于行业中的企业个数n,所以当n很大时,算法二的运算次数可以表示为n关于dim{CB\CT}次方的代数多项式,即算法二也是多项式算法。4客户模具的设计和制造能力要求b根据广东省模具协会1997年的统计,广东省拥有各类模具制造企业和车间8000余家。在目前正在设计开发的模具行业网站上,搜索引擎的设计是关键技术。我们设计的搜索引擎将采用定性搜索与定量评价相结合的方法。对模具行业调研的部分结果列于表2,为了便于观察,表2中的False没有在表中标出。已知注塑模具行业中的部分企业,其能力与行业基本能力单元之间的关系如表2所示。(续表2)表2中,cb1——注塑模具的工程分析能力;cb2——注塑模具的快速原型实现能力;cb3——注塑模具的结构设计能力;cb4——注塑模具的数控编程能力;cb5——注塑模具的曲面加工能力;cb6——注塑模具的电加工能力;cb7——注塑模具的