基于关键链的型号软件项目进度管理技术研究

摘要：关键链是项目进度管理的一种新方法。针对关键链技术的两个难点问题：如何识别关键链和如何设置缓冲区，结合型号软件项目开发的特点，分别给出了识别关键链的数学模型的求解算法和一种改进型的缓冲区的设置方法。

关键词：型号软件项目；关键链技术；关键链识别；缓冲区设置

中图分类号：G40-034 文献标志码：A文章编号：1673－291X（2010）32－0175－04

引言

型号软件作项目是以军事需要为需求背景的具有高科技特征的特殊商品。它具有研制周期长、投资数额大、技术风险高、参研单位广、环境不确定及影响因素多等特点。这些特点决定了对其进行管理与控制的复杂性，只要一个环节出现问题，就可能会出现研制周期延长、费用开支增加，从而造成巨大的经济损失和影响。

目前，型号软件的承制单位大多为非软件企业，即其主导产品并非软件，缺乏完整有效的软件项目进度管理体系。而且开发单位长期以来受计划模式的影响，项目进度计划往往以政治任务作为制定的依据，同时，没有借助于先进的进度管理理论和方法，没能将型号软件项目看成一个完整的系统，进度计划制订过粗。其次，型号软件项目缺乏动态的进度控制，使得型号软件项目的进度经常是前松后紧，最终很可能造成进度延期。因此，在型号软件作项目进度周期中，我们可以采用关键链技术对型号软件项目进行进度管理与控制。

一、基于关键链的项目进度管理框架

（一）传统的项目进度管理问题分析

1.工期估计时，在任务中加入安全时间，导致工期估计过长

由于型号软件的开发技术难度大，而且软件是一种逻辑产品，其中很多方面无法借用现有的经验，并且型号软件项目的开发进度往往是一项政治任务，这就导致在估计工期时，往往会选择低风险的即高完成概率的工期估计，在工期中加入尽可能长的安全时间。然而，低风险（90%概率完工）的工期估计可能会是50%概率完工工期的2倍或者更多（如图1），这样就将不确定性因素包括在每个任务工期的估计上，从而大大延长了整个项目工期。

2.主张尽早开始尽早结束，过长工期估计很少被提前完成

传统的 PERT/CPM方法大多主张早开始早结束的管理理念，会把工序尽早地安排。但是，任务提前完成只会使资源早用，而且有极大可能是提前被浪费。另外，虽然在单个任务工期的估计中都考虑了不确定因素，但由于学生惰性和帕金森症的影响，实际工作中却很少提前完成，并仍然有大量延误现象。这反而使得他们误认为工期时间估计过短[1]。

3.合并事项或合并路线的影响，使任务提前完成很难被有效利用，且增加项目延误的可能性

在网络计划中通常存在着众多路线，而这些路线最终都将汇入关键路线中。而后续任务的开工必须以其所有紧前任务的完工为前提，这就淹没了部分任务提前完工的效益，而大大增加了项目延迟风险，且并行程度越高，延迟可能性越大。通常，合并任务延迟概率为： Pdelay＝1-pi。其中：pi为该合并任务的各紧前任务的完工概率。如图2所示，关键线路上有一合并任务需要前面3条线路完工才能开始。即便是3条线路的完工概率为50%，则至少有1条线路延误的概率将高达87.5%。即使3条线路的完工概率都提高到90%，那么，至少有1条线路延误的概率仍达27.1%。倘若紧前任务更多的话，情况将更加严重，延误的概率将更大。

4.无视资源竞争

传统的关键路径，没有考虑资源的竞争问题，即使计划再缜密，一个任务的延期也会打乱整个项目的进度。不能找出真正完成任务的瓶颈。同时非关键路径上的工序使用资源也会影响到关键路径上的工序对同种资源的需求。

（二）基于关键链的项目进度管理概念模型

考虑到传统的项目进度管理手段在型号软件项目的开发中的存在诸多不足，本文借鉴Goldratt约束理论（TOC）的五大步骤[1]，提出基于关键链的型号软件项目进度管理概念模型，以此来突破型号软件项目的各种制约因素。模型的具体演算步骤如下：

步骤一，确定关键链，在充分借鉴网络计划技术的基础上，将关键链与经典网络计划技术兼容、统一。使用将项目进度编制与资源分配相结合的网络图来制定进度计划，并以此确定醒目进度中的关键链。

步骤二，充分使用关键链，根据关键链中所有任务的作业时间进行计算，往后集中成为项目缓冲以吸收不确定性对关键链所产生的影响；除了关键链以外，项目中其他所有的任务、路径及资源尽全平配合关键链，增加资源缓冲RB，计算非关键链上的输入缓冲FB和项目缓冲PB以保护关键链。

步骤三，生成项目的进度计划。

步骤四，确定项目的进度控制方案，监控缓冲区的消蚀情况来控制项目的进度，当缓冲区消蚀超过设置的范围，进行进度计划的纠偏，如果采取纠偏措施后，进度仍不能满足基线计划，则需要启动计划调整程序，转到步骤一，重新制定进度计划。

步骤五，结束。

使用关键链进行型号软件进度管理的主要难点在于关键链的确定和各种缓冲区的确定方法，本文将在后两章重点介绍如何确定关键链及如何计算缓冲区的大小。

二、识别关键链

（一）关键链数学模型描述

实施关键链型号软件项目进度管理的第一步就是生成基于关键链的项目进度计划。相对于传统的PERT/CPM技术，关键链在制定进度计划时就考虑资源的约束。由于型号软件开发的特殊性，往往需要处理多资源约束的问题。关键链的项目进度计划转化成一个多资源约束的进度编排问题（MRCPSP，Multiple Resources Project Scheduling Problem）。在MRCPSP中通常包含多种资源，每个任务也可能分配多种资源，所以在编排进度的时候就需要同时考虑任务的逻辑制约和多资源的约束关系。MRCPSP的数学模型可以如下描述[2]。

假设：集合Ta|i＝1，……，n，代表N个待排进度的任务集合；集合RR|k＝1，……，K，代表资源集合，Rk代表第k类资源的可用总数；Rik代表任务ai需要占用的、类资源的数量；集合SS|i＝1，……，N代表N个任务的开始时间集合；A（t）＝a|t＜Si＜t+Di代表t时刻正在进行的任务集合；rk（t）表示t时刻正在进行的任务集合所消耗的k类资源的总数量；S（ai）代表待排任务ai的开始时间；D（ai）代表任务ai的工期；S（ai）表示后置任务的开始时间；任务之间的逻辑关系用有向图D＝＜V，E＞表示；其中，V为顶点集，代表任务集，E＝＜v，v＞|v，v∈V代表任务v是v的前置任务，任务v必须在前置任务vi完成之后才能开始。

问题：求得满足下列条件的各个任务的开始时间SS|i∈V，使得编排得到的目工期最短。

S（a）+Di（a）≤S（aj），（＜ai，ai＞∈E）（1）

rk（t）≤Rk（t），（＜ii，j＞∈E）（2）

其中：式（1）式表示待排任务的开始日期加上该待排任务的持续时间不能超过后置任务的开始日期，这表示关键链技术满足传统的PERT/CPM技术中关键路径的相关要求，是对建立在约束理论和关键路径上的新的项目进度管理技术。

式（2）表明t时刻正在进行的任务集合所消耗的k的总数量不能超过k资源的可用总数，表示关键链基数考虑了资源的约束问题，是对对传统的PERT/CPM技术升级改进。

（二）关键链数学模型求解

1.从理论上说，资源约束条件下的优化问题是一种组合优化问题，这类问题受到活动的先后次序和资源限制的双重约束，使问题本身具有内在的复杂性，难以得到数学上的最优解。本文为采用基于优先规则的启发式方法，来得到一个一定名义上的满意解。

2.基于PERT/CPM的平行调度法

基于优先规则的启发式方法包括两大类：顺序调度法和平行调度法[3]。Kolisch在文献[4]中证明了在所有生成单一可行计划的基于优先规则的启发式方法中，平行调度生成方案的计算效率要比顺序调度生成方案的计算效率高。

因此，本文选用平行调度法，并在使用PERT/CPM编制的进度计划的基础上，采用基于优先规则ACTIM的启发式方法，建立了一种基于PERT/CPM的平行调度法来对上述问题进行求解，通过改进后的算法在没有资源约束时识别出的关键链与关键路径一样，这样既吸收了传统网络计划技术的优点，同时克服了当有资源约束时传统网络计划技术的不足，具体步骤如下：

第一步，在工作结构分解（WBS）的基础上，根据PERT/CPM方法，绘制出型号软件项目开发的网络图，并确定其关键路径，采用ACTIM启发式方法中的优先规则，为关键路径上的任务赋予属性A＝1，而对于非关键路径上的任务，为其赋予属性A＝0。令集合S为该型号软件项目中的所有项目任务。

第二步，令 等于项目开始时间。

第三步，判断任务开始时间在[t，t＝1]时段内的所有任务，采用启发式规则（这里采用ACTIM准则）先安排A＝1的任务，然后调度A＝0的任务。每调度一个任务i，要判断其对第k种资源的需求量rik是否超过第k种资源的供给量Rik。若rik＞Rk，则将任务i推迟至t+1时刻开始；若rik≤Rik则对任务i进行调度，并且从S中去掉任务i。

第四步，令t＝t+1。若S不为空，则转到第三步；若S为空，则转下一步。

第六步，设置项目缓冲、输入缓冲。

第七步，输出项目进度计划。

三、缓冲区的设置方法

（一）现有计算方法比较分析

缓冲量的大小对整个型号软件项目进度计划的工期估计以及项目的可行性有着十分重要的影响。本文将首先对几种已有的缓冲量计算方法进行简单的介绍和分析，然后在此基础上提出一种新的缓冲量计算方法。目前缓冲量的计算通常有以下4种方法[5]：

（1）Goldratt法：项目缓冲和输入缓冲的大小等于前链路上各任务50%完成概率下的工期估计之和的一半，即：

buffer＝ti50%（3）

（2）剪贴法：各任务90%完成概率和50%完成概率下的工期估计的差值之和的一半，即

buffer＝Δti（4）

（3）均方差法：该方法基于项目中各任务相互独立的假定，由Lencent科技公司最早提出，即

buffer＝[（Δti）2]（5）

在方法（2）和（3）中，Δti为各任务90%完成概率和50%完成概率下的工期估计的差，任务i为位于缓冲区前链路上的任务，令Si和Ai为别为完成概率为90%和50%的工期估计，即

Δti＝Si-Ai＝ti90%+ti50%，i∈（1，……，n）（6）

（4）弹性系数法

弹性系数法以PERT的三点估计（a，m，b）为基础，以两点时间估计（a，b ）代替三点估计，将时间估计m吸收到任务弹性系数K，然后以最乐观时间进行项目计划，通过K计算出缓冲区来吸收不确定因素。利用弹性系数K来衡量缓冲区的大小，其计算公式为：

PB＝（b-a）×K（7）

FB＝（b-a）×K（8）

其中，CC表示关键链上的任务，NCC表示非关键链上的任务，K表示关键链上任务的弹性系数，K表示非关键链上任务的弹性系数。弹性系数K＝，假如PERT的三点估计（a，m，b）中的最可能时间m越接近乐观时间a，则表明任务延期的可能性越小，K值就越小；对应的m越接近悲观时间b，则表明任务延期的可能性越大，K值就越大。

前三种缓冲量确定方法虽然简洁明了，但是都没有考虑任务持续时间分布的差异以及任务的不确定性会受任务在项目进度计划中所处的位置的影响的问题，即：距离现在越遥远的事务越难预测。因此，距离项目开始时间越远的任务不确定性越大；况且也有考虑到不同的利益相关者所具有的风险偏好也不相同。例如，Goldratt法作为一种线性方法，缓冲区大小随着相关链路持续时间的增长而线性增长，而事实上，这种线性增长的缓冲区在很多情况中都显得过不合时宜。

而弹性系数法中，用K值体现了各任务持续时间分布的差异，不同的任务由于其持续时间分布的不同对输入缓冲和项目缓冲的贡献值不相同，因此K也不尽相同。这虽然解决了任务持续时间分布的差异的问题，但仍难以解决任务的不确定性会受任务在项目进度计划中所处的位置的影响这个问题。

（二）改进的缓冲区设置算法

缓冲区是为了聚合因为消减单个任务安全时间后产生的风险提出的。事实上，一方面，型号软件项目的研制的进度管理方面借鉴了一般武器装备的研制方法，每个任务的计划工期都是经过专家的评审估计出来的；另一方面，型号软件项目的研制过程中涉及诸多技术难题，其进度计划的制定一般考虑了政治和其他方面的因素，和一般社会上的软件项目的进度设置有很大的区别。

综上所述，为了避免传统的缓冲区的设置方法的缺陷，并考虑到型号软件项目自身的特点，本文在型号软件项目的进度管理中，在弹性系数法的基础上，结合型号软件的特殊型，提出在弹性系数算法模型中加入位置权数α和进度浮动因子Δ的算法。通过α值来反映任务由于在项目进度计划中所处的位置差异而表现出来的不同的不确定性，通过浮动因子Δ来反映型号软件的特殊性。

该算法的具体步骤如下：

第一步，本文采用传统PERT/CPM技术，以PERT的三点估计中的最可能时间m来确定关键链CC，并且明确关键链上的任务项和非关键链上的任务项。

第二步，分别明确关键链上浮动因子Δi和非关键链上浮动因子Δj。 是一个介于0和1之间的值。普通的方法直接使用的m只是粗暴的代表着50％的完成概率的估计工期，这往往和实际情况不符，也和型号软件开发自身的特点大向径庭。这样可以采用模糊综合评判或专家打分的方法等专家的经验为关键链和非关键链上每个任务项赋予一个浮动因子Δ。

第三步，在浮动因子Δ的基础上，以PERT的三点时间估计确定K。计算公式如下：

Kip＝Δi×K，i∈Scc（9）

Kjf＝Δi×K，j∈（Sncc）（10）

其中，K＝代表普通的弹性系数，Scc代表关键链中任务的集合，Sncc代表非关键链中任务的集合。由于分别关键链上浮动因子Δi和非关键链上浮动因子Δj各不相同，这样就解决了由于其持续时间分布的不同对输入缓冲和项目缓冲的贡献值不相同造成的问题，同时考虑了型号软件项目的特殊性。

第四步，根据任务在关键链中所处的位置，计算位置权数。通过位置权数α进一步评估项目任务的不确定性，以各任务的时间中点为基准，测量其与项目开始时间的距离，再除以项目的时间长度，称为位置权数α，所以

αip＝，i∈Scc（11）

αjf＝，j∈Sncc（12）

其中，l表示各任务的时间中点与项目开始时间的距离；L表示项目的时间长度，即关键链开始的时间到关键链结束的时间之间的距离。这就解决任务的不确定性会受任务在项目进度计划中所处的位置的影响这个问题。

第五步，利用加入了浮动因子Δi的关键链上每个任务的弹性系数Kip和位置权数αip计算项目缓冲PB，以及加入了浮动因子Δj的非关键链上每个任务的弹性系数Kjf和位置权数αip计算输入缓冲FB。计算公式如下：

PB＝（bi-ai）×K×αip，i∈Scc（13）

FB＝（b-a）×K×αjf，j∈Sncc（14）

结语

使用关键链技术对型号软件项目进行进度管理，可以消除或减少不确定性和资源的约束对型号软件项目造成的影响。本文针对关键链技术中的两个难点问题：如何识别关键链和如何设置缓冲区，进行了重点研究。在分析现有的方法基础上， 结合型号软件项目开发的特点，作了一定的改善，分别给出了识别关键链的数学模型的求解算法和一种改进型的缓冲区的设置算法，从理论上论证了其可行性，但是还有待进一步的实践检验。

参考文献：

[1] 哈罗德・科兹纳.项目管理：计划、进度和控制的系统方法[M].北京：电子工业出版社，2002：692-707.

[2] 唐力波，马力.关键链研究与基于关键链的项目管理系统[J].计算机工程与实践，2004，25（11）：2077-2078.

[3] 徐南荣，仲伟俊.科学决策理论与方法[M].南京：东南大学出版社，1996：576-598.

[4] Kolisch，R.．Serial and parallel resource-constrained project scheduling methods revisited：Theory and computation[J]．European Journal of Operational Research．1996，（90）：320-333.

[5] 王俊.航天型号项目进度管理技术研究和系统实现[D].北京：北京信息控制研究所，2008.