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

运筹学在协同设计中的应用1、研究背景及意义协同设计是指为了完成某一设计目标，由两个或两个以上的设计者，通过一定的信息交换机制和相互协同机制，分别以不同的设计任务共同完成这一设计目标，它强调设计者采用群体工作方式，从而不同程度地改善了传统设计中项目管理与设计之间、不同设计阶段之间、设计与生产之间的脱节，以及设计周期过长，设计费用高，设计质量不易保证等弊病。企业中，对一些复杂产品的设计，是一个十分复杂的处理过程。为了实现一个产品的优化合理设计，通常需要引入多种设计方法和技术来达到设计的目的，而且，一个设计问题往往含有多种不同的设计任务和多种设计数据类型。以机械产品的设计为例，需要从产品的功能、外观、加工工艺、生产成本、市场需求、质量控制以及重用性等几个方面来并行地、整体地、综合地考虑其设计过程。在产品的设计过程中，涉及到与产品相关的各个领域的知识或专业知识，还涉及到对这些多领域知识、经验、数据的综合处理和利用，设计过程的复杂性对协同式的设计提出了最直接的需求。设计还是一个知识密集型的创新过程。在工程设计中，不仅需要丰富的专业知识和设计基础数据，还需要一定的实践经验知识，更需要对上述知识进行加工处理，产生设计新产品所需要的新概念和新知识。这是一个创新的过程，这使得设计成为一个以知识为基础的计算过程，不仅需要不同领域的知识和设计者的经验，而且需要综合和协同这些设计者的知识。知识密集型的特点对协同设计提出了更加迫切的要求。设计也是一个通信密集型的过程，不同的设计任务和设计数据之间相互交换、相互反馈、相互协调。因此在设计方法上提出了设计者的通信和协调问题，这从设计支持环境的角度对协同设计提出了明确的要求。不仅仅是企业中，我们在平时的学习或科研中也会遇到工程项目，需要人员间的互相配合。因此，我们有必要研究协同设计，以使我们能更高效率更高质量的完成任务，这对我们现在的科研或以后的工作都有重要的意义。而运筹学恰好是一门能运用在研究我们的协同设计的一门科学，所以本文我们就以企业为例，阐述下运筹学是如何在协同设计中运用的。文中主要从项目管理和冲突解决两个方面加以具体阐述运筹学理论与方法在企业协同设计中的应用。2、运筹学的定义运筹学(OperationsResearch，简称OR)是一门典型的理论与实际结合紧密的学科，P．M．Morse与G．E．Kimball给运筹学的定义为：“运筹学是在实行管理的领域，运用数学方法，对需要进行管理的问题统筹规划，作出决策的一门应用科学。”运筹学的核心内容有规划论、排队论、对策论、决策论、存储论、搜索论等。我国的运筹学研究近几年取得了许多好的科研成果，对于系统优化、排序、规划、竞争决策的运用机理进行了深入的研究和应用，形成了比较完备的一套理论。但我国的运筹学应用与发达国家相比还有较大差距，尤其是在企业管理方面的应用。2l世纪企业管理的许多领域，如企业制度、管理组织、战略管理、生产管理、质量管理、劳动人事管理等都有运筹学的身影。因此，研究运筹学理论，尤其是理论的实际应用具有很强的现实意义。运筹学在实际应用中表现如下的基本特征：(1)系统性：运筹学研究对象是有组织的系统，解决组织的规划和管理问题。(2)定量性：应用各种科学的方法、技术与工具，用定量分析的方法解决实际问题。(3)效益性：运用运筹学可以使组织中的人、财、物和信息得到最有效的利用，使系统的效益最大化。(4)实用性：运筹学已被广泛应用于工商企业、军事部门、民政事业等研究组织内的统筹协调及管理问题。(5)战略性：根据现有数据可以提供战略规划和战略，以系统最佳的方式来寻求最佳的行动方案。运筹学常见的几种重要的问题类型，主要有：分配、库存、更新与维护、排序与协调、排队、网络路线、竞争性问题、搜索问题等等。在解决工程项目协同设计的问题时，运用运筹学往往能取得很好的效果。但是如何取得好的应用效果，为企业带来经济效益，是运筹学应用推广的一个难题。3、运筹学在协同设计中的具体应用3.1项目管理与任务规划项目管理是一种为了在确定的时间范围内，完成一个既定的项目，通过一定的方式合理地组织有关人员，并有效地管理项目中的资源(人员、设备等)与数据，控制项目进度的系统管理方法。项目管理包括两方面：其一是项目组织，即根据项目的特点和项目计划，围绕项目合理组织项目中的人员，有效管理项目所需的各种资源和数据，保证项目按计划顺利完成；其二是项目控制，即围绕项目跟踪其进度掌握其各项工作现状，以便进行适当的资源分配和进度调整。在具体实施项目的过程中，随时对项目进行跟踪，以使项目按计划规定的进度、技术指标完成，并提供现阶段工作的反馈信息，以利于后续阶段的顺利开展和整个项目的完成。图1项目管理系统的体系结构目前国内外对于工程项目的管理研究都积累了较为丰富的经验，形成了比较完整的理论体系，但是在生产制造领域，项目管理的研究还很不够，尤其是支持分布式环境下面向开发的流程工作方式的项目管理系统还比较少。3．1．1协同设计项目管理的功能实现：实现项目管理，将协同设计的各项工作交由计算机处理规划，其中在很多功能中都用到运筹学的理论及思想，下面通过项目管理具体功能描述加以介绍。(1)项目分解和规划把一项复杂的项目工作分解为简单的、可操作的工作任务是项目计划中有效的手段。通常按照任务本身的性质或者完成任务的部门，分解成不同的层次，定义任务之间的约束关系。运用运筹学图与网络的相关理论提供一种图形化的编辑工具，生成任务网络图。同时定义每一个具体任务的任务目标和任务描述。最后按照某一目标进行优化，得出最优方案。图2产品任务分解结构树任务规划时采用网络计划技术计算项目的关键路径和任务的相关时间参数，明确标识出项目的关键任务和关键路径，使任务轻重缓急关系一目了然。通过利用工作的总时差和单时差，可以不断改善网络计划方案，优化项目计划，真正做到以最短的周期、最少的费用，对资源作最有效的利用。图2是具体产品任务分解的一种示例。(2)资源管理与调度资源管理与调度功能完成人员、时间、费用、设备等资源的管理，根据资源能力状态图，进行资源平衡和优化，并管理项目生命周期内的文档资料。根据项目进展需要，围绕关键任务，动态地调整资源的分配。(3)项目控制项目控制主要有启动、停止、暂停和恢复项目。建立项目模型，完成项目的分解和配置以后，就可以启动项目的执行。当一个项目或任务由于特殊原因不能继续执行时，就可以暂停它的执行，该项目下的所有任务也全部暂停。时机成熟时，恢复项目的执行，各个任务恢复到原来的状态。(4)监控项目该功能主要是在项目运行过程中，时刻监视项目的进展，使项目负责人和单位领导能够随时查看任务进度、费用使用状况等信息。另外，系统还具有报警功能，允许负责人自行设定报警时间间隔。一旦某些任务超期，或者费用超支，能够及时通知任务负责人和项目管理人员，以便做出调整。(5)任务调度任务调度分静态调整和动态调整。静态调整是针对因计划不当引起的关键线路的持续时间大于规定的工期的情况，主要是对关键线路持续时间的调整。动态调整是根据任务进展和进度需要，调整任务网络关系或者任务的持续时间。任务调整时，应该协调人员、时间、设备等资源的分配，优先满足关键项目、关键任务的需求，确保关键项目、关键任务的完成。(6)统计和查询项目按照任务状态统计项目内的任务，并列出任务的所有信息供浏览。可以按照任务的不同状态统计，例如执行、完成、暂停的任务，方便项目负责人控制进展。在进行一项新项目过程中，如果想借鉴以往项目积累的经验和教训，更加合理地安排新项目，可以通过查询功能完成。系统提供简单和复杂的多种查询方式，可以是按照项目的单个属性或者是按照多个属性的组合进行查询。3．1．2项目管理中的任务规划项目管理中上述功能的实现，一个重点工作就是任务规划，下面具体介绍应用运筹学理论实现功能的过程。任务规划包括任务分解和任务调度，就是在众多的匹配方法中寻找一个最合理的设计任务分配方案。通过对产品开发过程的规划可以给出指导其优化运行的策略，一个项目可以按照任务规划的模式统一规划。任务规划流程如图三所示。任务调度的目标是在合适的时间内，将子任务分配给合适的协同设计小组。虽然目前对任务规划的研究较多，但是动态任务规划中的冲突解决问题始终没有能够得到有效解决。在任务分解和分配的研究方面，目前有以下几个方法：局部／全局规划、分布式搜索、协商方法和基于动机的行为方法等，课题根据任务的难易程度分别综合运用不同的方法，达到速度与功能完善的协调统一。任务分解后，各子任务间通过输入、输出信息建立联系，从而直接构成了各任务在执行顺序和时间上的相互制约关系。任务重组就是要合理调整各子任务的组合，建立尽可能并行的、优化的设计过程模型。由于协同设计采用以人际合作关系为基础的群体协同工作模式，设计者通过网络进行设计，因此设计者必须遵守以下的规则：(1)设计者要有全局概念；(2)设计要面向修改，在产品设计中要考虑上、下游各环节，要保证产品能方便地实现修改，要有开放性、灵活性；(3)发挥工作组的职能，工作组的集体智慧是设计的源泉；(4)充分发挥网络的功能，保证设计信息的共享性和实时性；(5)重视信息反馈。在该项目的设计中，按照协同产品设计过程集成的要求，运用运筹学的理论及管理思想，以基于工作流程的协同项目管理系统设计为主导思想，以管理和控制制造业的分布式环境下流程工作方式的产品设计过程，采用基于图论中半序网拓扑排序法和强分支搜索算法的任务流程图自动生成算法，解决了子任务的规划问题。采用受资源约束的动态关键路径法，解决了子任务的运行和调度问题。图3任务规划流程3．1．3项目管理中任务规划的实施(1)任务规划算法项目规划的目的是生成项目的任务流程图。当子任务数量很多时，由项目管理员人工规划各子任务的执行步骤是非常困难的。在本系统中，结合强分支搜索算法和树的拓扑排序算法，形成任务流程图的自动生成算法。该算法不仅能自动地根据各子任务的依赖和时序关系排序，而且还能找到某些子任务的不合理分解，并提出优化建议。具体算法如下：Step1将各个子任务的相互依赖条件转换成任务初始关系图G。Step2对图G采用寻找强分支的搜索算法，找出最小的环并予以隔离形成一个新的任务关系图G’。Step3重复Step2直至任务关系图中不再存在环，从而形成了一个半序网。Step4对该半序网调用扩展拓扑排序算法，得到一个带优先权的任务队列。Step5将该队列转换成任务流程图，转换方法是：1)把具有同一优先权的所有子任务放到任务流程图的同一层次中。2)精简每一子任务的前序任务，只保留位于该子任务的前一层次的前序任务，删除其余的前序任务。3)加入有向边连接所有的前序任务和后序任务。(2)任务调度任务调度的目标是在不违反规划好的任务流程图的时序关系和任务资源约束前提下，在最短的时间周期内完成高质量的项目。项目任务调度的一个经典算法是关键路径法，给定一个任务流程图，找到其中的关键路径的方法是图论的一个基本问题。传统意义上的关键路径法要求任务流程满足两个基本假设：1．两个任务模块只需在时序关系上满足并行执行的条件即可并行执行，不受人员、资源的约束，即假设这两个任务模块或者不共享同一资源，或者共享资源是保证充分供应的。2．每一个任务模块的完成时间是事先就可精确确定的。不受执行过程中环境因素的影像。而对企业的项目开发来说，这两个假设往往都是不成立的，这就要求采用受资源约束的动态关键路径法来实现任务调度功能。其具体算法如下：Stepl利用动态规划和匈牙利方法求解项目中每一未完成任务结点的资源等待时间，同时获取了受资源约束的实际任务调度时序；Step2求解每一未完成任务结点的最早完成时问和最晚完成时间，从而求得项目的关键路径；step3判断项目任务是否已完成。若已完成则调度结束；否则选取所有当前可以运行的任务通知相关用户执行，如果是项目关键路径上的任务结点则通知项目管理员重点监控；Step4当某一任务完成是判断其完成时间，若早于其最早完成时间或晚于其最晚完成时间则转Stepl，否则转Step3。3．2冲突消解冲突消解是一个典型的运筹学研究问题，协同设计是多个