计划协同工作中的冲突检测与消除算法研究

滕海坤+李伦彬+刘心声+刘芳芳

摘 要：针对跨企业计划协同工作中的资源冲突问题，提出了一種新的跨企业项目协同工作的冲突检测和消除模型，利用基于供需时间的计划协同冲突检测算法实现跨企业协同项目中的资源冲突检测，采用基于启发式规则的计划冲突消除算法消除冲突。基于研究结果设计、开发了项目计划管理原型系统，以高铁项目任务的管理为例进行了验证，表明了研究结果的有效性。

关键词：协同工作；冲突检测；供需时间；启发式规则

中图分类号：TP393.09 文献标识码：A DOI：10.15913/j.cnki.kjycx.2017.08.008

随着越来越多的跨行业、跨地域的企业间产品经营协作的出现，大企业之间——跨企业合作的项目大量涌现。项目的计划编制是跨企业项目管理的核心，是避免资源浪费，有效组织、提高效率的手段，因此，计划协同在跨企业项目管理中具有重要的作用。资源是项目执行和最终实现的必要保障，对于大型制造企业的跨企业项目来说，复杂的产品结构、分布式的项目组织、时间过长的项目执行周期等都有可能导致资源的时间重叠性，即关键资源的竞争，这就引发了不同企业之间的计划冲突，影响到整个项目的进程。针对跨企业项目任务集合的约束进行无限能力约束的网络计划（NetPlan）编制，确定出任务相关的时间表、关键路径和执行周期等重要参数。在此基础上，综合考虑现有资源动态利用率，对网络计划进行分时段动态能力统计和对比，找出资源冲突的时间和产生资源冲突的相关任务，并消除资源冲突，最终确定项目的执行计划和资源分配情况。本文针对这种实时资源冲突检测和消除策略进行了研究，以期为日后的相关工作提供参考。

本文以复杂产品制造企业之一的高铁生产企业为背景，在编制跨企业项目计划的过程中，利用基于供需时间的冲突检测算法实现对计划协同过程中产生的资源冲突的实时检测，采用基于启发式规则的冲突消除算法消除冲突，最终确定项目进度计划和资源管理。

1 跨企业项目计划协同过程概述

跨企业项目计划在项目管理中占有非常重要的位置，跨企业项目计划将直接影响跨企业项目的执行情况，也会直接关系到多个企业的运作结果。考虑到跨企业项目的复杂度，跨企业项目网络计划协同过程主要分为3个阶段，即协作控制计划编制阶段、设备生产进度控制阶段、协作控制计划变更阶段。跨企业项目计划协同主要发生在协作控制计划编制阶段。

本文针对总装企业设备需求计划模型（ZGJ）和协作企业设备供货计划模型（XGJ）编制网络计划协同过程，在确定了与任务相关的各时间参数、关键路径等基础上，提出了基于计划协同冲突检测和冲突消除的两阶段协同过程，具体如图1所示。该过程首先对来自总装企业的设备需求计划和关键协作企业的设备供货计划进行协同冲突检测。当存在非正常供货情况时，可按照相应的冲突消除方法生成解决策略，并按照预先定义的性能评价指标对消除策略进行评价选择，最终将选定的消除策略下发到总装企业和协作企业实施。总装企业和关键协作企业实施消除策略后，重新提交需求计划和供货计划，生成新的网络计划，直至检测到没有计划冲突为止。

2 跨企业项目计划协同冲突检测消除算法

2.1 问题描述

在跨企业项目计划协同的过程中，整个项目执行过程中的设备需求计划与供货情况可能会发生各种各样的冲突。引发资源冲突的主要原因有以下3点：①供需时间，即任务的时间重叠；②前序任务延期，未按计划时间完成，对后序任务造成了影响；③任务时间与资源调度日历不符。这些原因的共同之处在于任务对资源占用时间的重叠。因此，本文针对设备供需时间进行计划协同冲突检测，主要是完成对总装企业设备需求计划和协作企业供货计划供需时间的冲突检测，并根据检测结果确定下一步计划的变更。

冲突检测的步骤是：①选择设备需求信息和对应的设备供货计划；②基于供需时间进行计划冲突检测，并根据不同的检测结果预定处理策略。计划冲突检测消除的执行流程如图2所示。当设备发生非正常供货时，由于设备不能按原计划到达，导致整个任务延期。此时，则认为发生总装企业拟编制的整体计划与关键协作企业拟编制的设备生产和供应计划发生计划协同冲突。

2.2 基于供需时间的计划协同冲突检测算法

本文根据关键协作企业给出的供货时间和总装企业要求的最早供货时间与最迟供货时间之间的关系，提出了基于供需时间的计划协同冲突检测算法，用于检测网络计划编制过程中可能存在的冲突。该算法通过供需时间判断供货方式、冲突类型及其他相关信息，冲突供货对后续协作设备的约束信息，该冲突对生产计划的影响情况。本文将冲突类型分为提早供货、正常供货、延迟供货直接冲突和间接冲突四类。

基于供需时间的冲突检测算法具体描述如下。

2.3 基于启发式规则的计划冲突消除算法

针对提早供货情况，本文通过关键协作企业和总装企业共同承担增加的附加费用，来实现跨企业组织之间的利益共享、风险共担，进而最终实现共赢的目标。本文主要研究延期供货的情况。针对延期供货而产生的直接冲突，本文将采用基于启发式规则的冲突消除算法来处理。针对前续任务所需设备延期供货产生的间接冲突，可等待前续任务的直接冲突消除完后，再调用计划冲突检测算法进行新一轮冲突检测，最终把间接冲突转换为一般的供货情况或直接冲突情况来处理。

基于启发式规则的计划冲突消除算法具体描述如下。

输入：延期供货导致的计划冲突集合、ZGJ、XGJ、NetPlan、自由松弛时间FL、设备最大偏离值CMi.

输出：计划冲突消除策略集合CCL。

算法具体描述：①初始化活动队列Q和冲突消除策略集合CCL。②分别根据项目调度规则和任务调度规则对检测结果集合C_3的数据项PRi和任务分解WBSi进行基数排序，并且按处理优先级由前到后的顺序插入队列Q中。③判断Q是否为空。如果为空，算法结束；否则，从Q中取出队首元素aij，操作步骤④⑤⑥⑦⑧⑨，直至队列为空。④判断aij是否为关键活动。如果是，转到步骤⑧，否则继续执行。⑤判断aij以计划开工时间Sij作为起点任务工期向右移动min{CMi，FLij}个单位是否满足有限资源约束。如果满足，转到步骤⑦，否则继续执行。⑥计算在现有资源约束下aij能向右移动的最大时间t。将aij以Sij作为起点，任务工期向右移动t个单位，且CMi更新为CMi-t，把aij加入到队列Q中，转到步骤③。⑦确定非关键活动

的调整总代价 和消除策略Lij，按协作企业的供货计划达成

共识，转到步骤⑩。⑧针对关键活动aij，将采用3种方案生成冲突消除策略，即单独由总装企业消除冲突，协调中心调用总装企业的关键任务工期动态调度算法生成相应的消除策略；单独由协作企业来消除冲突，协调中心调用基于网络计划的项目工期压缩算法生成相应的消除策略；由双方共同消除冲突。此时，双方分别承担的冲突消除时间为t1和t2，其中，{（t1，t2）│t1+t2=CMi，t1>0，t2>0}，协调中心调用对应的消除算法生成相应的策略。⑨协调中心利用性能评价指标评价生成的策略，从中选择最优的冲突消除策略Lij分配给总装企业和协作企业实施。如果达成共识，则转到步骤⑩；如果未达成共识，则继续选择次优消除策略分配，直到达成共识或消除策略为空。如果消除策略为空，协调中心与双方协商项目拖期天数和相应的协调策略，在保证拖期天数最少的前提下使双方达成共识，然后转到步骤⑩。⑩按雙方预先商定的附加费用分摊机制计算双方应承担的费用，生成最终的冲突消除策略，双方按此协作，算法结束。

3 系统实例验证

根据对跨企业项目计划协同计划冲突的检测方法和管理技术的研究，本文以高铁制造企业为应用背景，建立了一个项目资源管理原型系统，系统包括计划编制管理、计划进度管理、协作计划变更管理、计划协同冲突检测和计划协同冲突消除等主要模块，提供了对项目网络计划的编制、执行过程中的资源冲突检测、检测结果的表达和基于计划动态调整的冲突消除等主要功能。协调中心根据接收到的总装企业提交的设备需求计划和关键协作企业提交的设备供货计划进行基于供需时间的计划协同冲突检测。计划协同冲突检测结果如图3所示。

根据检测结果的不同类型进行不同的处理。当设备发生延期供货并引发计划冲突时，则利用基于启发式规则的计划冲突消除方法处理，生成的结果界面如图4所示。

协调中心根据预先定义的性能评比指标评比生成的计划冲突消除策略，并根据评比结果，选择最优的消除策略分配给总装企业和协作企业，以便它们落实冲突消除策略。

实例验证表明，应用计划协同冲突检测消除算法可以有效发现项目任务中存在的资源冲突，多视图的表达方式直观、明确，系统对资源计划冲突信息的管理十分有效。

4 结束语

本文以高铁项目任务为背景，通过对基于供需时间的计划协同冲突检测算法和基于启发式规则的消除策略在跨企业项目中的应用研究，解决了在跨企业项目管理系统中存在的问题，大大提高了企业之间联合运作的效率，并通过实例验证了所建项目资源管理原型系统的可行性，为解决跨企业协同项目中的资源管理问题提供了一种有效的解决方案。针对跨企业协同项目资源计划冲突问题在理论和方法上的相关研究仍需继续进行，以满足我国大型项目管理的实际需要。

参考文献

[1]屈正庚.协同工作中冲突消除机制的研究[J].计算技术与自动化，2012，31（3）：104-108.

[2]乔丽红，王超.多级协同项目执行中的资源冲突检测与管理[J].北京航空航天大学学报，2008，34（11）：1266-1271.

[3]Yujun Zheng，Jinquan Wang，Jinyun Xue.Distributed Cooperative Planning and Scheduling for Disaster Management.2007 IEEE International Conference，2007.

[4]何霆，武冬冬，徐汉川.基于PM/ERP集成模式的跨企业协同计划问题研究[J].计算机工程与设计，2008，29（2）：287-291.

[5]林鸣，马士华.动态联盟项目管理新模式[M].北京：电子工业出版社，2003.

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

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

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

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

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

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

〔编辑：白洁〕