计算机研究与发展
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999年　第36卷　第10期　Vol.36　No.10　1999



ZD-PDM中面向目标的项目管理模型的设计
刘乃若　董金祥　李善平　陈刚
　　摘　要　随着制造业竞争的日益激烈，传统的组织管理方法已不能适应市场的要求.PDM系统中的项目管理功能日益得到重视，但大多数现有PDM系统的项目管理功能很弱，甚至没有.文中针对这些情况，提出了一种面向目标的项目管理方法，主要对项目管理中的资源约束、项目子任务的分解设计、项目子任务的规划排序、项目子任务的运行调度进行，分别给出了面向子任务分解的层次分解方法、强分支搜索算法的任务流程图自动生成算法、受资源约束的动态关键路径法，并在ZD-PDM系统中予以实现.
　　关键词　PDM，项目管理，任务，生命周期
　　中图法分类号　TP391
DESIGN OF A GOAL-ORIENTED MODEL FOR PROJECT
MANAGEMENT IN ZD-PDM
LIU Nai-Ruo, DONG Jin-Xiang, LI Shan-Ping, and CHEN Gang
（Department of Computer Science and Engineering, Zhejiang University，Hangzhou 310027）
　　Abstract　With the increasing global competition, the traditional method for organization and management is not suitable to demands from the market. So a project management approach in a PDM system is attracting attention, but few PDM systems support it. For these conditions, a goal-oriented managing method is proposed in this paper, which includes resource constrained, requirement analysis for project goal, subtask design, subtask planning, subtask control and project evaluation. This paper gives methods of task-oriented hierarchical decomposition, auto-producing flowing charts by strong-branch search, and dynamic key path restricted by resource. They are realized in ZD-PDM.
　　Key words　PDM，project management，task，life cycle
1　引言
　　企业的生产目的是为了最大限度地满足市场或顾客的需求、获取最大限度的经济效益.这就要实现利用最低的成本，以最短时间生产出市场需要的产品.解决的办法就是集中主要精力保证最薄弱的环节满负荷工作，以最短的时间完成生产.整个生产系统生产效率最薄弱的环节称为关键资源，一般是人、设备、物料等.随着全球工业化市场的发展，传统的生产管理模式已不能很好地满足市场对企业的要求，新的组织管理方式应运而生，这种面向目标的组织方式就是PDM中的项目管理.项目管理最早始于控制论和系统理论，在如何最大限度地利用现有资源（人员、设备）在最短的时间内完成任务方面所做的所有努力均可划入项目管理的范畴，一般认为要包括3个方面的内容［1～3］：
　　(1) 项目是面向目标的.所有的项目都有一个给定的目标，项目建立的目的就是实现此目标.目标并不须指明如何完成，则只须指明要达到的最终状态.
　　(2) 项目具有生命周期.目标的实现过程必须在一个有限的时间间隔内完成，实现过程包括计划和实现两个阶段.
　　(3) 项目目标的过程是由人来完成，称为项目用户.项目用户通常分为定义目标、规划控制目标实现的项目管理员和执行具体功能的项目工作人员.
　　项目管理是PDM系统一个不可缺少的组成部分，但在现有的PDM中项目管理的功能或者没有，或者只有象征性的功能支持.同时，项目管理对缩短产品开发周期、提高企业的反应能力、适应不同产品需求具有重要作用，因此开展对项目管理的进一步研究就很有必要.
　　项目管理并不存在固定模式，本文的目标是得到一种大多数企业都适用的通用模式，即是一个较高层次上的管理模型，而不是一个细化到可以适合每一企业特点的专用模式.文献［1］、［4］给出了项目管理的一般步骤，在此基础上，本文提出了一个比较通用的项目开发生命周期，即认为项目生命周期包括项目目标需求分析、项目子任务的分解和设计、项目子任务的规划和排序、项目子任务的运行、调度和项目目标评估5个步骤.本文首先给出了项目及相关的定义；对于子任务的分解和设计问题，采用自顶向下的层次分解方法解决；对于子任务的规划问题，介绍了一个强分支搜索算法的任务流程图自动生成算法；对于子任务的运行和调度问题，本文提出了一个受资源约束的动态关键路径法.并将上述思想用于浙江大学开发的一个通用的PDM系统—ZD-PDM中［4］.
2　定义
　　定义1. 项目目标.
　　项目目标可定义为一个四元组(E,D,E,T)，其中：E是项目目标的具体描述；D是项目目标的数据指标，表示当项目完成后评价项目完成情况的一些量化描述；E是项目目标的经济指标，表示项目目标的实现经费限制；T是项目目标的时间指标，表示项目目标完成的时间期限.
　　定义2. 子任务.
　　子任务可定义为一个四元组（H,D,R,A），其中：H是执行该子任务的项目工作人员集；D是该子任务的时间期限；R是分配给该子任务的资源集；A是该子任务的执行活动，可定义为一个映射, 其中：i(C)是该子任务的输入参数集；o(C)是该子任务的输出参数集；DOM(v)是参数v的类型.
　　定义3. 项目.
　　项目P可以定义为一个五元组 (G,T,R,M,E)，其中：G是该项目要求实现的项目目标；T是该项目所属的所有子任务集；R是该项目所属的所有任务关系集；M是管理该项目的管理员；E是出现任务执行出现错误时的非正常出口集.
　　定义4. 项目管理.
　　项目管理可以定义为一个三元组 (P,S,M)，其中：P是管理的项目对象；S是项目P的约束规则集；M是对项目P的扩展、操纵动作集.
3　资源约束
　　资源约束描述了项目内部各类人员、软件、设备等资源的分配和调度过程.ZD-PDM系统定义了3类矩阵来描述项目的资源约束.假设项目P包含K个子任务、J类固定资源（包括人员以及车床、计算机等固定设备）、K个固定资源、P类数据资源（包括各类原材料、资金等），那么这3类矩阵可被定义为
　　矩阵X=［Xij］是一个I×J的整数矩阵，其中某一项Xi描述了子任务i必须占用固定资源类的数量；
　　矩阵Y=［Yik］是一个I×K的布尔矩阵，其中某一项Yik描述了子任务i是否可以占用固定资源k；
　　矩阵Z=［Zip］是一个I×P的实数矩阵，其中某一项Zi描述了子任务i必须占用数据资源类p的数量.
　　由于这些矩阵一般情况下都是稀疏矩阵，因此可以采用链表的方式简化系统存储.链表方式可分为以任务为主的方式和以资源为主的方式.以任务为主的链表方式对应于上述矩阵的行，其优点是方便从任务出发寻找其相对应的资源分配和约束情况.由于ZD-PDM系统的项目管理采用了以任务为中心的设计思想，所以系统中采用了以任务为主的链表方式.
4　项目的生命周期
　　项目生命周期有5个阶段: 项目目标需求分析、项目子任务的分解和设计、项目子任务的规划和排序、项目子任务的运行和调度、项目目标评估，其控制流程如图1所示［1］：


图1　项目的生命周期图
4.1　任务的分解和设计
　　任务的层次结构通常可分为3类：
　　(1) 联合结构：联合结构是应用最广泛的层次模型，在联合结构中，每一任务结点被划分为若干个子任务结点，每一子任务结点均更详细定义了其父结点的一个任务子集.完成父任务结点的前提是所有子任务结点都必须完成.
　　(2) 分离结构：另一种较普遍的层次模型是分离结构，与联合结构不同的是在分离结构下，只需有一个子任务结点完成就可保证其父结点完成任务.
　　(3) 混合结构：混合结构是任务树内部同时具有联合结构和分离结构的一种层次模型，最简单的一种混合结构可以用与或树表示.
　　ZD-PDM系统中的任务分解树以联合结构为主，在某些情况下也支持混合结构的任务层次分解.ZD-PDM系统提供了一个图示化的任务树编辑器，充分支持用户的子任务分解工作：
　　① 子任务的完全层次分解. ZD-PDM中的任务划分严格遵循了逐步分解的层次结构，上层只传递给下层一个任务目标，而对任务的设计细节、实现方法则不作过多的干涉，只起修改协调的作用；
　　② 局部充分自治.下层设计者在完成上层任务目标和不违反全局资源约束的前提下可以充分发挥能动性，能够在局部范围内解决的问题决不提交到上层解决;
　　③ 支持分权和并行工作模式. ZD-PDM系统并不要求所有的任务分解工作都由一个人完成，系统允许任务负责人将某些子任务的分解工作移交给另一些人完成，同时支持他们的并行工作.
4.2　子任务的规划
　　子任务规划工作的目的是生成项目的任务流程图.当子任务数量很多的情况下，由项目管理员人工规划各子任务的执行步骤是非常困难的.ZD-PDM系统实现了一个基于图论的子任务规划算法，算法的提出首先是基于这样的假设：项目管理员在分解和设计完项目所属的子任务后，往往已经明确了每一子任务的前序任务，即得到了任务的初始关系图，但还不能立即得出项目的任务流程图.在项目任务复杂、子任务数量很多的情况下，人工完成这一工作比较困难.
　　在子任务数目非常巨大的情况下，其中初始任务关系图中有可能包含环.为此引入了强分支的搜索算法，可在初始关系图中隔离出环，该算法基于图的深度优先搜索算法实现，它可描述为［6］：
　　算法1. 强分支搜索算法.
　　步骤1. 初始化队列ORDER1和ORDER2；
　　步骤2. 从任意一个初始结点N开始对任务的初始关系图G进行深度优先搜索，在队列ORDER1中记录下所有被访问过的结点.深度优先搜索的递归过程可简单表示为：
　　① 将当前结点加入一全局队列L中；
　　② 寻找每一个不在队列L中的当前结点的后序结点；
　　③ 如果不存在这样的结点，过程返回，反之将每一个这样的结点作为当前结点递归进行深度优先搜索.
　　步骤3. 将任务关系图G的每一条弧线的箭头颠倒，得到新的任务关系图G′；
　　步骤4. 从同一个初始结点N开始对任务关系图G′也进行深度优先搜索，将所有被访问过的结点都记录到队列ORDER2中.
　　步骤5. 对两个队列ORDER1和ORDER2作交集，得到的就将是一个环，把这个环压缩成一个大结点，从而产生了一个新的任务关系图Gt.
　　步骤6. 对图Gt重复以上步骤，直到从任意结点开始的深度优先搜索都找不到这样的环后结束（参见图2、图3）.


图2　规划前的子任务图


图3　规划后的子任务图
　　根据强分支搜索算法得到的环中各结点对应的子任务是相互依赖的，在ZD-PDM系统的项目管理中不支持这种情况.因此当系统检测到这样的环后，将提醒项目管理员手工消除这样的环，或者将这些子任务自动结合成为一个大的子任务.
　　结合强分支搜索算法和树的拓扑排序算法，ZD-PDM系统中任务流程图的自动生成算法如下：
　　算法2. 任务流程图自动生成算法.
　　步骤1. 将各个子任务的相互依赖条件转换成任务初始关系图G；
　　步骤2. 对图G采用寻找强分支的搜索算法，找出最小的环并予以隔离形成一个新的任务关系图G′；
　　步骤3. 重复步骤2直至任务关系图中不再存在环，从而形成了一个半序网；
　　步骤4. 对该半序网调用扩展拓扑排序算法，得到一个带优先权的任务队列；
　　步骤5. 将该队列转换成任务流程图，转换方法是：
　　① 把具有同一优先权的所有子任务放到任务流程图的同一层次中；
　　② 精简每一子任务的前序任务，只保留位于该子任务的前一层次的前序任务，删除其余的前序任务；
　　③ 加入有向边连接所有的前序任务和后序任务.
　　经过该算法处理后，图4所示的任务初始关系图被自动转换为图5所示的任务流程图.


图4　任务初始关系图


图5　转换后的任务关系图
　　对一个具有或关系前序任务的子任务来说，无法直接应用上述算法.假设一个任务结点T具有m个前序任务结点，其中有n个前序任务结点只需有一个完成便可激活该任务的执行，换句话说，这n个前序任务结点之间是或的关系，对此解决策略是：
　　(1) 首先将任务结点T分解为n个结点 (T1，T2，...,Tn) ,每一结点均具有m-n+1个前序任务结点.将所有具有或关系前序任务的任务结点都经过此过程转换后就去除了任务关系图中的所有或分支；
　　(2) 接着将经过上述变换得到的任务关系图应用算法2得到没有或分支子任务的任务流程图.由于T1，T2，…，Tn具有相同的后序任务结点，因此这些结点在经过算法2处理后应具有相同的优先权；
　　(3) 重新合并T1，T2，..., Tn为一个统一的结点T，将T1，T2，...,Tn的前序结点的交集作为T的公共前序任务结点，差集之间则具有或关系，T同时具有与T1，T2，...,Tn相同的后序任务结点，从而得到了带或关系的任务流程图.
　　最后要指出，对于循环的任务结点，在ZD-PDM系统的任务流程图自动生成处理中将其视为一个结点.至于循环的次数、循环的结束条件等必须由项目管理员指定.
4.3　任务的调度
　　任务调度的目标是在不违反规划好的任务流程图的时序关系和任务资源约束前提下，在最短的时间周期内完成高质量的项目.
　　关键路径：项目任务流程图的关键路径是一个从项目入口到项目出口的任务结点和有向边集，该集合中所有任务结点的时间期限之和为最大.这些任务节点也就决定了该项目是否能如期完成.在ZD-PDM系统中引入了称之为受资源约束的动态关键路径法来实现任务调度功能.首先给出：
　　最早完成时间：假设P是项目初始结点T0到任务结点Ti的任意一条路径，tp(Ti)是从T0沿着路径P到达经过的所有任务结点时间期限的总和，则称tp(Ti)的最大值为任务结点Ti的最早完成时间，记为TE（Ti），即TE（Ti）=max{tp(Ti)}.假设Ti有j个前序任务结点，TE（Ti）可以递归地由下式得到：TE(Ti)=max1≤k≤j{TE(Tik)+Γ(Ti)+W(Ti)}，其中，Tii是Ti的第k个前序任务结点，Γ(Ti)是Ti的执行时间期限，W(Ti)是Ti的资源等待时间.
　　在明确了任务的最早完成时间概念后，很明显地，项目关键路径的长度就是项目结束任务结点的最早完成时间.
　　最晚完成时间：在项目结束任务结点的最早完成时间不增加的前提下，允许从入口点T0最晚到达任务结点的时间，称为Ti的最晚完成时间，记作TLTi.假设Ti有j个后序任务结点，TLTi可以递归地由下式得到：TL(Ti)=max1≤k≤j{TL(Tik)-Γ(Tik)-W(Tik)}，Tik是Ti的第k个后序任务结点，Γ(Ti)与W(Ti)的定义同上.在定义了这两个概念后，就得出了一个重要的定理.
　　定理1. 如果任务结点Ti满足条件TE(Ti)=TL(Ti)，那么Ti位于项目的一条关键路径上.
　　证明. 假设结点Ti满足条件TE(Ti)=TL(Ti)，但却不在项目的关键路径上，也就是说，存在一条从入口结点T0经过Ti到结束结点Te的路径，该路径的执行时间小于项目结束任务结点的最早完成时间TE(Te).设从Ti到结束结点Te的路径的执行时间为P(Ti,Te)，则P(Ti,Te)<TE(Te)-TE(Ti).根据任务最晚完成时间的定义，TL(Ti)≥TE(Te)-P(Ti,Te)TL(Ti)>TE(Ti)，与前面的假设相矛盾，定理得证.
　　定理1指明了项目关键路径的获取算法，即首先必须求得每一任务结点的最早完成时间和最晚完成时间，找出那些最早完成时间和最晚完成时间相等的任务结点即构成了项目关键路径.但是这里还有两个问题尚未解决，其一是资源等待时间W(Ti)的求值，其二是当某些任务提前或滞后于给定的时间期限完成时，可能会使原先求得的项目关键路径有所改变.
　　关于问题1的解决方法，即资源等待时间W(Ti)的求值，可以结合前面给出的任务流程自动生成算法和资源分配、约束矩阵对问题进行求解.事实上，假设根据任务流程自动生成算法寻找到所有与Ti具有同一优先权的任务结点共有p个，（包括Ti本身），这些结点在时序关系上可以并行执行，表示为Ti1,Ti2,Λ,Tip，且共享m个资源，那么资源等待时间W(Ti)的求值问题就可转换为求解动态0-1最优规划问题：

　　约束:
　　其中：Γ(Tik)为任务Tik的执行时间期限；φ1和φ2都是0-1参数，如果任务Tik与其它任务受资源约束无法并行执行，则φ1和φ2都等于1，否则若W(Tik)>Γ(Tik), 则φ1=1,φ2=0；若W(Tik)<Γ(Tik)，则φ1=0，φ2=1；Rn为第n个资源总数，Xnk为任务Tik需占用资源Rn的总数；λk是一个0-1参数，是任务Tik是否正在执行.
　　而每一个W(Tik)又可递归地表示成任务Tik不参与下的动态0-1最优规划问题，即可表示为

　　约束:
　　经过一系列的递归过程后，问题被转化为静态的0-1最优规划问题，可利用匈牙利方法求解［5］.实际上，求解完这一0-1最优规划问题后，不仅求得了任务Tik的资源等待时间，而且获取了任务Ti1,Ti2,Λ,Tip的实际调度时序.
　　关于问题2的解决方法，ZD-PDM系统的解决策略是时刻监测当前的所有已完成的任务结点，如果某一任务结点的完成时间早于其最早完成时间或晚于其最晚完成时间，则必须重新计算剩余任务结点的最早完成时间和晚于其最晚完成时间，更新项目的关键路径［6］.
　　综上所述，ZD-PDM系统项目管理的任务调度算法为
　　步骤1. 利用动态规划和匈牙利方法求解项目中每一未完成任务结点的资源等待时间，同时获取了受资源约束的实际任务调度时序；
　　步骤2. 求解每一未完成任务结点的最早完成时间和最晚完成时间，从而求得项目的关键路径；
　　步骤3. 判断项目任务是否已完成，若已完成则调度结束；否则选取所有当前可以运行的任务通知相关用户执行，如果是项目关键路径上的任务结点则通知项目管理员重点监控；
　　步骤4. 当某一任务完成时判断其完成时间，若早于其最早完成时间或晚于其最晚完成时间则转步骤1，否则转步骤3.
4.4　项目评价
　　项目评价是项目管理的一个重要部分，通过项目评价确定项目目标是否已真正实现，即确定是否可以终止该项目；如果项目目标离预期效果尚有一定距离，系统应能自动确定需改进的瓶颈问题，并提出具体的改进建议.限于篇幅，本文不讨论项目评价的实现方法.
5　结论与展望
　　随着PDM的日益广泛应用，作为其中的一个重要功能的项目管理，也越来越得到用户的注意，对项目管理的功能提出了更多的要求.本文作者所在的科研组开发了具有自主版权的ZD-PDM系统，它的项目管理按本文提出的思路进行设计，具有较强的功能，对其项目评价部分将另文介绍.以后的工作将着重于其智能化、并行化的研究工作.
本课题得到国家“八六三”计划项目(项目编号 863-511-9842-014)基金资助.
作者简介：刘乃若，男，1972年5月生， 博士研究生，主要研究方向为STEP、CIMS、PDM等.
　　　　　董金祥，男，1945年7月生，教授，博士生导师，主要研究方向为CAD、CIMS、数据库等.
　　　　　李善平，男，1963年6月生，教授，主要从事CIMS、信息集成、PDM等研究.
　　　　　陈刚，男，1973年9月生，讲师，主要从事PDM、人机交互等研究.
作者单位：浙江大学计算机科学系　杭州　310027
参考文献
　1　　Betina Schweyer. Multiagent design of a role-based model for project management. Integrated Computer Aided Engineering, 1997, 4(1): 210～234
　2　　Betina Schweyer, Grasset A, Haurat A. Information system design for project management. In: Proc of Int'l Conference on Industrial Engineering and Production Management, Marrakech, Morocco, 1995
　3　　Betina Schweyer, Haurat A, Roche C. Enterprise modelling in terms of projects using multi-agent systems. In: Proc of 15th International Conference on Modelling, Identification and Control, Innsbruck, Austria, 1996. 19～22
　4　　陈刚. 柔性、开放式产品数据管理系统的设计和实现［博士论文］. 浙江大学，1998
　　　(Chen Gang. Design and implementation of flexible and open PDM system［Ph D dissertation］. Zhejiang University, 1998)
　5　　Sarker V. Partitioning and scheduling parallel programs for multiprocessor. Cambridge, Mass: MIT Press, 1989
　6　　魏权令等. 数学规划与优化设计. 北京：国防工业出版社， 1993
　　　(Wei Quanling et al. Mathematical Planning and Optimization Design. Beijing: National-Defense-Industry Publishing House, 1993)
原稿收到日期：1999-01-07；
修改稿收到日期：1999-05-12.
