协同工作中冲突消解机制的研究

摘要：协同工作就是利用网络技术众多设计者共同合作完成任务，及时更新信息，保证网络信息的一致性与快速响应性。但是在协同工作过程设计成员自身条件差异，不可避免在协同设计中会产生冲突，所以准确及时对冲突检测与消解是协同工作的关键。因此提出一种新的集成化冲突消解模型，给出模型算法，利用模式匹配技术在这个模型中进行冲突检测与消解，采用克莫普匹配法进行冲突消解。通过实验证明，集成化模型和模式匹配技术很有效，对冲突检测准确，对冲突消解效率高，尤其处理大批量冲突时速度很快，效果非常显著，算法复杂度也很低。



关键词：协同工作；冲突检测与消解；集成化模型；模式匹配技术

中图分类号：TP391.9文献标识码：A



Collaborative Work in Conflict Resolution Mechanism



QU Zhenggeng

（The department of computer science， Shangluo University， Shangluo726000，China）

Abstract：Collaborative work is the use of network technology， many designers work together to complete the task， and update the information in a timely manner to ensure consistency with the rapid response of the network information. But the difference in the process of working together members of its own conditions， unavoidable in collaborative design conflict， so accurate and timely conflict detection and digestion is the key to work together. Therefore， a new integrated conflict resolution model， the model algorithm， pattern matching In this model， collision detection and digestion， with KMP matching method for conflict resolution. The experiments show that the integrated model and pattern matching techniques is very effective， accurate conflict detection， conflict resolution， high efficiency， especially when dealing with large quantities of conflict quickly， the effect is very significant， the complexity of the algorithm is very low.



Key words：collaborative work； conflict detection and resolution；integrated model； pattern matching techniques



1引言

协同工作是指利用计算机网络技术，多个设计人员围绕同一个设计项目展开自己的设计任务，并行交互的工作，最终得到符合设计条件的结果。在协同工作中，设计人员的工作思路、考虑问题角度、参考标准、知识领域的不同，肯定会在设计过程中产生冲突。冲突对协同工作过程既起到消极作用，又起到积极作用，一方面冲突的存在必然会导致设计的不和谐，数据的不一致；另一方面冲突是一个优秀产品设计的开端，冲突不断产生与消解，使一个最优的设计诞生了，提高了产品的整个性能指标。

目前国内外对冲突消解做了深入研究，常见的方法有基于规则、基于实例、基于约束以及基于协商的冲突消解技术[1，2]。但是这些消解技术只是从单一的角度去考虑问题，在实际应用中具有一定的片面性和局限性。协同工作是一个复杂的、多样的、动态的变化过程，协同工作系统中发生的冲突不可能依赖于某一种冲突消解方案可以化解掉的，需要将多种策略科学的、合理的结合起来才能达到理想的状态。因此提出了集成化的冲突消解模型，并利用模式匹配算法进行验证，得到了很好的效果。

2冲突消解的概述

2.1冲突概念

协同冲突是指多个相互有联系的对象之间存在一种不一致、不稳定、不和谐、不兼容的状态。防止和解决冲突是冲突管理追求的目标。一般来说，进行冲突管理会涉及到三个方面关键技术：冲突避免技术、冲突检测技术和冲突消解技术，它们相辅相成，彼此影响，如1图所示。

图1冲突管理

冲突避免就是在冲突发生之前弄清楚冲突的根源，然后通过一定的技巧和措施避免潜在冲突的发生。冲突检测主要利用领域相关法和领域无关法。冲突消解主要对无法避免冲突采用合理的办法去有效地化解。

2.2冲突消解现状

冲突消解在协同工作系统中具有特殊的位置，选择最优的措施来解决已发生的冲突。引起冲突发生的原因复杂多样，形成冲突类型也很繁琐，造成冲突消解很艰难。目前国内外对冲突消解进行了大量研究[3，4]，主要的方法有基于规则、基于实例、基于约束以及基于协商的冲突消解技术。对于产品开发过程中的个人矛盾可以利用基于规则、基于实例、基于约束的方式解决，合作团队、知识领域、部门专家之间的矛盾一般协商技术。但是这些技术只从单一角度考虑问题，只能解决一些简单问题，对于实际存在的复杂问题无法实现，而且协同工作本身是一个动态变化的过程，需要一种全面的技术在实际工作中使用。

3集成化冲突消解的模型

3.1消解模型

在建立协同工作冲突消解模型过程中，需要考虑很多方面的因素：第一，设计小组之间信息的传递速度和反馈意见[5，6]；第二，消解冲突使用的方法应该如何实施；第三，各种冲突消解方法在解决问题是如何有效的集成起来；第四，消解过程实时调度问题。

计算技术与自动化2012年9月

第31卷第3期屈正庚：协同工作中冲突消解机制的研究

认真分析与考虑上述要求后提出冲突消解模型如2图所示。

图2冲突消解模型



冲突消解过程大致分为以下几个步骤：第一步，通过冲突检测工具对设计过程进行冲突检测，对检测到的冲突分类汇总，按照一定的规律排序。第二步，根据冲突的关联性，判断冲突是否有连锁效应，如果有则采用约束消解技术，否则采用事例和规则消解技术。第三步，通过上述三种方法都无法解决的冲突则采用协商消解技术。在协商过程中，大家提出各自的意见，共同商量、沟通、探讨，确定出一致性的决策。如果失败则进行仲裁。第四步，仲裁人综合考虑各方面的因素后，提出最为恰当的方案，供大家去解决冲突[7，8]。最终还有人不接受则只有转换冲突消解策略，将冲突转移到协同设计的上一层，重新对协同工作进行设计与规划。

3.2消解算法

利用特定工具检测出来的冲突进行消解的算法描述如下：

冲突进行分类与排序

{ if冲突有关联性then

{约束技术

if解决成功then

冲突化解

}

else 实例或者规则技术

if解决成功then

冲突化解

else

{协商技术

if 协商成功 then

冲突化解

else

{仲裁

if 仲裁成功 then

冲突化解

else

冲突层次转换

}

}

}

4模式匹配的冲突消解技术

4.1基本思想

根据协同工作中冲突的类型与含意，建立一个实例库和规则集，设计人员进行协同工作。如果不可避免的发生了冲突，判断出冲突类别，根据类别在实例库或规则集中进行匹配，匹配成功，则冲突就可以解决，失败则匹配最相似的冲突，对最相似的冲突进行修改，修改后就可以消解冲突；如果仍然不能解决则转换思维，对冲突进行分解，反复匹配，直到解决为止[9]。 

假设实例库和规则集为S=”ababcabcacb”，产生的冲突集：C=”abcac”。C在S中进行匹配，匹配过程如3图所示。

图3冲突匹配过程

4.2冲突消解过程

采用模式匹配消解冲突时，需要考虑到四个方面的因素：第一、建立的实例库和规则集必须详细，尽可能的多；第二、对发生的冲突进行匹配时，要利用快速有效地方法去分类；第三，如果匹配几次仍无法解决，及时换转思维，调换策略，防止死“循环”。第四，设计人员要有丰富的工作经验。

模式匹配冲突消解基本结构如4图所示，主要有冲突检测器、冲突分类器、匹配器、消解器组成[10]。

模式匹配冲突消解过程：首先在冲突检测器中检测到的冲突信息传递给分类器，分类器根据冲突的破坏性、根源、大小、类别详细的分类；然后再匹配器中进匹配，匹配成功则消解，不成功改变策略，对冲突分解后再次匹配；最后在消解其中对冲突评价和修改，进一步更新匹配器[11，12]。

图4模式匹配冲突消解结构



4.3冲突消解的算法

冲突信息的具体描述：

Des_ConflictDescribe

{ public：

int Des_ConflictHarm；//冲突破坏性

int Des_ConflictSour； //冲突根源

int Des_ConflictClass； //冲突类别

int Des_ConflictSize； //冲突大小

voidDes_Collect //实例库和规则集的总和

voidDes_ConflictSolve //对应的冲突消解成功

}

算法描述如下：

for（i=1；i

{ 

if（Des_ConflictSour && Des_ConflictClass） == Des_Collect

thenDes_ConflictSolve

else分解冲突模块

{ if（Des_ConflictSour && Des_ConflictClass） == Des_Collect

thenDes_ConflictSolve

elsestop }

对冲突评价

修改Des_Collect

}

字符串匹配算法中，实例库和规则集用数组S，冲突集用数组C，next数组表示next函数的相关值。从数组S中的K位置寻找和冲突集C相匹配的解决方案，具体如下：

inti，j

i=K， j=1；

while （ i<=S[0] && j<=C[0] ）//没有找见结束

if（ j==0||S[i]==C[j] ）

{ i++；

j++； }

elsej=next[j]； //右滑

if（j>C[0]）

return i—C[0]； //匹配成功，消解冲突

else return 0； //匹配失败

}

inti，j// 冲突集C的next值并入next数组中

i=1， j=0；

next[1]=0；

while （ i

{ if（ j==0||C[i]==C[j]）

{ i++；

j++；

next[i]=i； } 

else j=next[j]；

}

4.4算法效果分析

发生的冲突与实例库和规则集匹配时，可以采用两种模式匹配算法：基本匹配法（BF）和克莫普匹配法（KMP）[13，14]。为了测试BF算法和KMP算法性能，选取2.5Mbit的英文文本，在其中查找多个模式串，找出所有出现的位置。在实验中，选取3组不同长度的模式串，每组的模式串数目从1到25以4为单位递增。测试环境为Pentium3.0GHz、内存1GB，操作系统Windows XP，编译环境VC++6.0。实验结果如表3所示。

表3查找时间（单位：ms）

模式串长度

算法

模式串数目

1

5

9

13

17

21

25

2

BF算法

643

657

688

721

745

760

795

KMP算法

225

238

255

279

296

327

347

10

BF算法

655

678

693

733

767

793

833

KMP算法

220

228

245

268

279

290

310

18

BF算法

668

689

703

747

779

801

855

KMP算法

208

212

227

243

253

265

270

5结语

协同工作最主要的任务就是冲突检测与消解，并且保证协同数据一致性与及时响应性。通过实际应用，上述的研究方案有很好的效果，提高了工作效率[15，16]。算法也是可行的，复杂度比较低，运行速度快。但是在冲突消解过程中协同数据传输有点迟缓，需要进一步研究。

参考文献

[1]孟秀丽.协同设计支持环境及冲突消解理论与方法[M].南京：东南大学出版社，2010.

[2]孙博，张荣国，王艳艳，等.协同设计中的模糊冲突消解方法[J].计算机工程与应用，2009，45（3）：84—86.

[3]李海波，余金山，陈维斌.一种本体协同冲突的检测方法[J].华侨大学学报：自然科学版，2011，32（6）：66—69.

[4]杨育，王小磊，曾强.协同产品创新设计优化中的多主体冲突协调[J]. 计算机集成制造系统，2011，17（1）：255—258.

[5]蒋国瑞，段晓敏，张瀚林.基于冲突检测的供应链协同计划[J]，计算机工程，2010，6：86—89.

[6]孟秀丽，易红，倪中华.基于模糊评价的协同设计冲突仲裁技术研究[J].计算机集成制造系统，2005，3（11）：399—405.

[7]汪大勇，金炜东.协同设计中的并行冲突检测算法[J].计算机应用，2007，3（27）：650—653.

[8]曹将栋.采用模糊估算的产品协同开发中成本冲突消解方法的研究[J].现代制造工程，2011，（1）：18—21.

[9]钱屹，侯义斌.一种快速的字符串匹配算法[J].小型微型计算机系统，2004， 25（3）：410—413.

[10]王丽萍，江波，邱飞岳.基于多目标进化算法的协同设计冲突消解方法[J].计算机集成制造系统，2010，16（9）：174—176.

[11]张莉.缝制设备协同开发过程中冲突消解方法的研究[J].工程设计学报，2010，17（2）：188—190.

[12]赵阳，刘弘.协同设计中基于规则推理的冲突消解研究[J].计算机应用研究，2006，10（1）：54—57.

[13]PIERRE A Y.A CSP approach for the network of product life cycle constraints consistency in a collaborative design context[J].Engineering Applications of Artificial Intelligence，2009（06）：123—126.

[14]SIDHARTHA P，NARAYANA P P.Comparison of particle swarm optimization and genetic algorithm for FACTS—based controller design[J]. Applied Soft Computing Journal， 2008（04）：66—69.

[15]SLIMANI K，FERREIRA D S C，MEDINI L.Conflict mitigation in collaborative design[J]. International Journal of Production Research， 2006（09）：106—109.

[16]CHEN Ming，LIU Jinfei，KONG Qinghua.Application of ontological thought in collaborative product R & D oriented to automobile lifecycle[M]. Washington，DC：IEEE，2010：326—319.