运筹学在协同设计中的应用

1、运筹学在协同设计中的应用1、研究背景及意义协同设计是指为了完成某一设计目标，由两个或两个以上的设计者，通过一定的信息交换机制和相互协同机制，分别以不同的设计任务共同完成这一设计目标，它强调设计者采用群体工作方式，从而不同程度地改善了传统设计中项目管理与设计之间、不同设计阶段之间、设计与生产之间的脱节，以及设计周期过长，设计费用高，设计质量不易保证等弊病。企业中，对一些复杂产品的设计，是一个十分复杂的处理过程。为了实现一个产品的优化合理设计，通常需要引入多种设计方法和技术来达到设计的目的，而且，一个设计问题往往含有多种不同的设计任务和多种设计数据类型。以机械产品的设计为例，需要从产品的功能、外观

2、、加工工艺、生产成本、市场需求、质量控制以及重用性等几个方面来并行地、整体地、综合地考虑其设计过程。在产品的设计过程中，涉及到与产品相关的各个领域的知识或专业知识，还涉及到对这些多领域知识、经验、数据的综合处理和利用，设计过程的复杂性对协同式的设计提出了最直接的需求。设计还是一个知识密集型的创新过程。在工程设计中，不仅需要丰富的专业知识和设计基础数据，还需要一定的实践经验知识，更需要对上述知识进行加工处理，产生设计新产品所需要的新概念和新知识。这是一个创新的过程，这使得设计成为一个以知识为基础的计算过程，不仅需要不同领域的知识和设计者的经验，而且需要综合和协同这些设计者的知识。知识密集型的特点

3、对协同设计提出了更加迫切的要求。设计也是一个通信密集型的过程，不同的设计任务和设计数据之间相互交换、相互反馈、相互协调。因此在设计方法上提出了设计者的通信和协调问题，这从设计支持环境的角度对协同设计提出了明确的要求。不仅仅是企业中，我们在平时的学习或科研中也会遇到工程项目，需要人员间的互相配合。因此，我们有必要研究协同设计，以使我们能更高效率更高质量的完成任务，这对我们现在的科研或以后的工作都有重要的意义。而运筹学恰好是一门能运用在研究我们的协同设计的一门科学，所以本文我们就以企业为例，阐述下运筹学是如何在协同设计中运用的。文中主要从项目管理和冲突解决两个方面加以具体阐述运筹学理论与方法在企业

4、协同设计中的应用。2、运筹学的定义运筹学(Operations Research，简称OR)是一门典型的理论与实际结合紧密的学科，PMMorse与GEKimball给运筹学的定义为：“运筹学是在实行管理的领域，运用数学方法，对需要进行管理的问题统筹规划，作出决策的一门应用科学。”运筹学的核心内容有规划论、排队论、对策论、决策论、存储论、搜索论等。我国的运筹学研究近几年取得了许多好的科研成果，对于系统优化、排序、规划、竞争决策的运用机理进行了深入的研究和应用，形成了比较完备的一套理论。但我国的运筹学应用与发达国家相比还有较大差距，尤其是在企业管理方面的应用。2l世纪企业管理的许多领域，如企业制度

5、、管理组织、战略管理、生产管理、质量管理、劳动人事管理等都有运筹学的身影。因此，研究运筹学理论，尤其是理论的实际应用具有很强的现实意义。运筹学在实际应用中表现如下的基本特征：(1)系统性：运筹学研究对象是有组织的系统，解决组织的规划和管理问题。(2)定量性：应用各种科学的方法、技术与工具，用定量分析的方法解决实际问题。(3)效益性：运用运筹学可以使组织中的人、财、物和信息得到最有效的利用，使系统的效益最大化。(4)实用性：运筹学已被广泛应用于工商企业、军事部门、民政事业等研究组织内的统筹协调及管理问题。(5)战略性：根据现有数据可以提供战略规划和战略，以系统最佳的方式来寻求最佳的行动方案。运筹

6、学常见的几种重要的问题类型，主要有：分配、库存、更新与维护、排序与协调、排队、网络路线、竞争性问题、搜索问题等等。在解决工程项目协同设计的问题时，运用运筹学往往能取得很好的效果。但是如何取得好的应用效果，为企业带来经济效益，是运筹学应用推广的一个难题。3、运筹学在协同设计中的具体应用3.1项目管理与任务规划项目管理是一种为了在确定的时间范围内，完成一个既定的项目，通过一定的方式合理地组织有关人员，并有效地管理项目中的资源(人员、设备等)与数据，控制项目进度的系统管理方法。项目管理包括两方面：其一是项目组织，即根据项目的特点和项目计划，围绕项目合理组织项目中的人员，有效管理项目所需的各种资源和数

7、据，保证项目按计划顺利完成；其二是项目控制，即围绕项目跟踪其进度掌握其各项工作现状，以便进行适当的资源分配和进度调整。在具体实施项目的过程中，随时对项目进行跟踪，以使项目按计划规定的进度、技术指标完成，并提供现阶段工作的反馈信息，以利于后续阶段的顺利开展和整个项目的完成。图1 项目管理系统的体系结构目前国内外对于工程项目的管理研究都积累了较为丰富的经验，形成了比较完整的理论体系，但是在生产制造领域，项目管理的研究还很不够，尤其是支持分布式环境下面向开发的流程工作方式的项目管理系统还比较少。311 协同设计项目管理的功能实现：实现项目管理，将协同设计的各项工作交由计算机处理规划，其中在很多功能中

8、都用到运筹学的理论及思想，下面通过项目管理具体功能描述加以介绍。(1)项目分解和规划把一项复杂的项目工作分解为简单的、可操作的工作任务是项目计划中有效的手段。通常按照任务本身的性质或者完成任务的部门，分解成不同的层次，定义任务之间的约束关系。运用运筹学图与网络的相关理论提供一种图形化的编辑工具，生成任务网络图。同时定义每一个具体任务的任务目标和任务描述。最后按照某一目标进行优化，得出最优方案。图2 产品任务分解结构树任务规划时采用网络计划技术计算项目的关键路径和任务的相关时间参数，明确标识出项目的关键任务和关键路径，使任务轻重缓急关系一目了然。通过利用工作的总时差和单时差，可以不断改善网络计划

9、方案，优化项目计划，真正做到以最短的周期、最少的费用，对资源作最有效的利用。图2是具体产品任务分解的一种示例。(2)资源管理与调度资源管理与调度功能完成人员、时间、费用、设备等资源的管理，根据资源能力状态图，进行资源平衡和优化，并管理项目生命周期内的文档资料。根据项目进展需要，围绕关键任务，动态地调整资源的分配。(3)项目控制项目控制主要有启动、停止、暂停和恢复项目。建立项目模型，完成项目的分解和配置以后，就可以启动项目的执行。当一个项目或任务由于特殊原因不能继续执行时，就可以暂停它的执行，该项目下的所有任务也全部暂停。时机成熟时，恢复项目的执行，各个任务恢复到原来的状态。(4)监控项目该功能

10、主要是在项目运行过程中，时刻监视项目的进展，使项目负责人和单位领导能够随时查看任务进度、费用使用状况等信息。另外，系统还具有报警功能，允许负责人自行设定报警时间间隔。一旦某些任务超期，或者费用超支，能够及时通知任务负责人和项目管理人员，以便做出调整。(5)任务调度任务调度分静态调整和动态调整。静态调整是针对因计划不当引起的关键线路的持续时间大于规定的工期的情况，主要是对关键线路持续时间的调整。动态调整是根据任务进展和进度需要，调整任务网络关系或者任务的持续时间。任务调整时，应该协调人员、时间、设备等资源的分配，优先满足关键项目、关键任务的需求，确保关键项目、关键任务的完成。(6)统计和查询项目

11、按照任务状态统计项目内的任务，并列出任务的所有信息供浏览。可以按照任务的不同状态统计，例如执行、完成、暂停的任务，方便项目负责人控制进展。在进行一项新项目过程中，如果想借鉴以往项目积累的经验和教训，更加合理地安排新项目，可以通过查询功能完成。系统提供简单和复杂的多种查询方式，可以是按照项目的单个属性或者是按照多个属性的组合进行查询。312项目管理中的任务规划项目管理中上述功能的实现，一个重点工作就是任务规划，下面具体介绍应用运筹学理论实现功能的过程。任务规划包括任务分解和任务调度，就是在众多的匹配方法中寻找一个最合理的设计任务分配方案。通过对产品开发过程的规划可以给出指导其优化运行的策略，一个

12、项目可以按照任务规划的模式统一规划。任务规划流程如图三所示。任务调度的目标是在合适的时间内，将子任务分配给合适的协同设计小组。虽然目前对任务规划的研究较多，但是动态任务规划中的冲突解决问题始终没有能够得到有效解决。在任务分解和分配的研究方面，目前有以下几个方法：局部全局规划、分布式搜索、协商方法和基于动机的行为方法等，课题根据任务的难易程度分别综合运用不同的方法，达到速度与功能完善的协调统一。任务分解后，各子任务间通过输入、输出信息建立联系，从而直接构成了各任务在执行顺序和时间上的相互制约关系。任务重组就是要合理调整各子任务的组合，建立尽可能并行的、优化的设计过程模型。由于协同设计采用以人际合

13、作关系为基础的群体协同工作模式，设计者通过网络进行设计，因此设计者必须遵守以下的规则：(1)设计者要有全局概念；(2)设计要面向修改，在产品设计中要考虑上、下游各环节，要保证产品能方便地实现修改，要有开放性、灵活性；(3)发挥工作组的职能，工作组的集体智慧是设计的源泉；(4)充分发挥网络的功能，保证设计信息的共享性和实时性；(5)重视信息反馈。在该项目的设计中，按照协同产品设计过程集成的要求，运用运筹学的理论及管理思想，以基于工作流程的协同项目管理系统设计为主导思想，以管理和控制制造业的分布式环境下流程工作方式的产品设计过程，采用基于图论中半序网拓扑排序法和强分支搜索算法的任务流程图自动生成算

14、法，解决了子任务的规划问题。采用受资源约束的动态关键路径法，解决了子任务的运行和调度问题。图3 任务规划流程313项目管理中任务规划的实施(1)任务规划算法项目规划的目的是生成项目的任务流程图。当子任务数量很多时，由项目管理员人工规划各子任务的执行步骤是非常困难的。在本系统中，结合强分支搜索算法和树的拓扑排序算法，形成任务流程图的自动生成算法。该算法不仅能自动地根据各子任务的依赖和时序关系排序，而且还能找到某些子任务的不合理分解，并提出优化建议。具体算法如下：Step1 将各个子任务的相互依赖条件转换成任务初始关系图G。Step2 对图G采用寻找强分支的搜索算法，找出最小的环并予以隔离形成一个

15、新的任务关系图G。Step3 重复Step 2直至任务关系图中不再存在环，从而形成了一个半序网。Step4 对该半序网调用扩展拓扑排序算法，得到一个带优先权的任务队列。Step5 将该队列转换成任务流程图，转换方法是：1) 把具有同一优先权的所有子任务放到任务流程图的同一层次中。2) 精简每一子任务的前序任务，只保留位于该子任务的前一层次的前序任务，删除其余的前序任务。3) 加入有向边连接所有的前序任务和后序任务。(2)任务调度任务调度的目标是在不违反规划好的任务流程图的时序关系和任务资源约束前提下，在最短的时间周期内完成高质量的项目。项目任务调度的一个经典算法是关键路径法，给定一个任务流程图

16、，找到其中的关键路径的方法是图论的一个基本问题。传统意义上的关键路径法要求任务流程满足两个基本假设：1两个任务模块只需在时序关系上满足并行执行的条件即可并行执行，不受人员、资源的约束，即假设这两个任务模块或者不共享同一资源，或者共享资源是保证充分供应的。2每一个任务模块的完成时间是事先就可精确确定的。不受执行过程中环境因素的影像。而对企业的项目开发来说，这两个假设往往都是不成立的，这就要求采用受资源约束的动态关键路径法来实现任务调度功能。其具体算法如下：Stepl 利用动态规划和匈牙利方法求解项目中每一未完成任务结点的资源等待时间，同时获取了受资源约束的实际任务调度时序；Step2 求解每一未

17、完成任务结点的最早完成时问和最晚完成时间，从而求得项目的关键路径；step3 判断项目任务是否已完成。若已完成则调度结束；否则选取所有当前可以运行的任务通知相关用户执行，如果是项目关键路径上的任务结点则通知项目管理员重点监控；Step4 当某一任务完成是判断其完成时间，若早于其最早完成时间或晚于其最晚完成时间则转Step l，否则转Step 3。32冲突消解冲突消解是一个典型的运筹学研究问题，协同设计是多个主体参与的过程，由于各主体的目标、方案和对象往往存在冲突和矛盾，因此冲突识别和消解是协同设计系统中的关键问题。冲突的消解是使设计由局部最优向全局最优进化的过程。由于协同设计是多功能小组参与到

18、一个项目的设计过程中，各小组之间存在着大量相互制约、相互影响的关系，同时又由于它们对产品开发的考虑角度、评价标准、领域知识、使用技术、数据结构、操作系统等不尽相同，这些因素必然导致协同设计过程中产生冲突。冲突的消解在很多方面体现了运筹学的管理思想，下面在整个冲突处理过程中分别加以阐述。321冲突解决流程实现冲突管理的三个关键支持技术是：冲突避免技术、冲突检测技术和冲突消解技术。冲突管理的三种关键技术在工作时共同作用，能够使冲突尽可能地得到消解。冲突避免技术是针对冲突产生的根源而建立的，通过解除冲突产生的根源而达到避免冲突的目的。冲突检测主要运用相关领域的知识来判断冲突是否发生。冲突的消解主要依

19、据冲突产生的不同原因按不同的方式给予解决。冲突管理的流程如图4所示。图4 冲突解决流程322冲突解决由于冲突所涉及的范围较广，给冲突的消解带来困难。国内外对冲突消解作了大量的研究工作，归纳起来主要分为：基于规则、基于实例、基于知识、基于专家系统以及基于协商的冲突消解系统。本系统结合协同设计的过程特点将冲突解决模块划分为冲突避免、冲突检测、冲突分析、冲突解决、自学习功能五个主要模块。其框图如图5所示。通过运筹学原理对资源进行优化组合，并利用知识共享与信息系统集成技术减少冲突出现的可能。设计小组接到工作任务进行资源配置时，系统辅助进行资源优化配置，减少资源冲突；协同平台上建立共享工作空间，通过共享

20、工作空间增强知识交流与参考知识的一致性；通过系统集成确保系统数据的实时性与一致性。图6所示为冲突避免策略框架。系统中按照运筹学动态规划的理论，动态规划的最优性原理提出冲突解决策略。图5 冲突解决框图 图6 冲突避免策略框架323冲突检测与分析冲突检测是通过冲突检测识别模块动态识别报价过程存在的各类冲突。冲突分析则为分析检测到的冲突所属类别，寻找可能的解决方案，为冲突解决提供信息支持，它主要包括冲突分析知识库与逻辑规则，如图7所示。324冲突解决方案冲突解决包括基于协商的冲突解决、基于综合约束的冲突解决和基于实例的冲突解决三种方案，具体的冲突解决均以此为理论基础。利用运筹学的决策分析理论，分析冲

21、突的类型，提出优化的对策。(1)基于协商的冲突解决：通过协同使能工具进行协商解决报价过程中出现的冲突。协同使能工具主要包括共享音频、共享视频、网络会议、多媒体电子邮件、协同浏览器、知识冲突解决工具等。(2)基于约束综合的冲突解决：基于弱约束的冲突解决：自身约束级别相对较低，只能通过修改自己的约束内容实现冲突消解。基于强约束的冲突解决：自身约束级别相对较高，可以通过强制修改其他约束内容实现冲突消解。基于约束综合的冲突解决：冲突双方约束级别相同，只能通过共同修改冲突双方的约束内容实现冲突消解。图7 冲突检测与分析(3)基于实例的冲突解决：基于实例推理的冲突解决本质是通过运用解决旧冲突的解决办法来解

22、决新冲突，它能够更好地反映人类专家的思维过程，与基于规则的冲突解决遥相呼应。因为基于规则的冲突解决需要把大量的领域知识转换为冲突解决的规则，而复杂冲突解决问题很难用规则描述，所以此处将基于规则的冲突作为基于实例冲突解决的补充。系统获取冲突信息后，首先经过规则推理系统，若冲突不能解决则进入实例冲突解决系统。4、结论本文介绍了运筹学理论在研发一个企业协同设计平台中的几个实际应用，实际上在整个项目的设计和研究中，涉及运筹学的应用还很多，有基本理论的运用，也有理论集成和应用突破，在这里只是介绍了协同设计系统中两个方面的运用。运筹学是一门综合性的学科，不是具体针对某一门学科的。学好运筹学，能够对我们的科

23、研工作有很大的帮助，会使我们一生受用。能够深入理解运筹学这门课，将更多的运筹学理论运用于平时的实践中去，是我们掌握运筹学的标志。这学期学了运筹学这门课，虽然时间短，信息量大，我们不能完全理解及掌握所有的相关理论，但是至少我们接触到了运筹学，知道有这门学科的存在，大致知道相关的优化理论，那么我们在具体的科研中就有可能在需要的时候加以详细的学习，比如说学习某一个优化理论及算法，例如遗传算法、蚁群算法、神经网络算法等等。相信，随着学习的深入，我以后会更加深入的理解运筹学也能适当的运用运筹学解决具体的问题，那么学习这门课的目的也就达到了。在这里，我也要感谢老师带我们走进运筹学的知识殿堂。参考文献：1

24、常锋娟.协同技术在机械设计中的应用研究. 江苏大学硕士学位论文. 20022 龙子泉管理运筹学M武汉：武汉大学出版社，2002，123 樊飞运筹学发展的历史回顾J南京工业大学学报(社会科学版)，2003一Ol-0079-064 郑波，袭著燕.运筹学在企业协同设计平台研究中的应用. 中国企业运筹学学术交流大会论文集. 20085 章祥荪等运筹学：21世纪通向繁荣的大道第15届国际运筹学会联合会大会综述中国科学院院刊，20006 D1anaki Ram，NVivekananda,CSrinivas Rao，NKrishna,MohanConstraint Meta-Object：A new Obj

25、ect Model for Distributed Collaborative DesigningIEEE Transactions on Systems，man and Cybernetics-Part A：System and Humans，1 997，27(2)：208-2207 Kazuo MiyashitaCAMPS：A Constraintbased Architecture for Multiagent Planning and SchedulingJournal ofIntelligent Manufacturing,19989(2)：1471548 Venkat J RCoo

26、peration Requirements Planning(CRP)for Multi-processors：Optimal Assignment and Execution PlanningJournal ofIntelligent and Robots Systems，1996，15(5)：419-4359 Tamio Arai，Jun OtaLet US Work Together-Task Planning of Multiple RobotsIEEE Intemational Conference on Intelligent Robots and Systems，v l。1996

27、：29830310 卢开澄图论及其应用M北京：清华大学出版社，198111 肖位枢图论及其算法M北京：航空工业出版社，199212 王诺网络计划技术及其拓广研究北京：人民交通出版社，199913 孟明辰，韩向利并行设计北京：机械工业出版社，199914 董仲元，蒋克铸设计方法学北京：高等教育出版社，199115 苏德洋现代设计方法上海：上海交通大学出版社，199616 虞付进计算机支持的协同设计研究综述机电工程2000(5)：5-717 史美林，向勇，杨光信计算机支持的协同工作理论与应用北京：电子工业出版社，200018 卢开澄，卢开明图论及其应用清华大学出版社，199519 曹键，张友良等计

28、算机支持下的协同设计及其环境研究计算机工程与应用1999(51：39-4120 GQHuang，JHuang，KLMakAgentbased workflow management in collaboriative product development on the internetComputer Aided Design2000(32、：133一14421 LALHakim，AKusiak，JMathewA graph-theoretic approach to conceptual design with functional perspectivesComputer Aided Design2000(32)：86787522 32 Upenda B，et a1Dynamic Scheduling of design Activities with resource constraints