资源约束项目计划外在稳健性研究*

崔万安

(1.广西民族大学 管理学院，广西 南宁 530006；2.武汉大学 博士后流动站，湖北 武汉 430072)

一、引言

资源约束项目计划考虑了稀缺资源的合理分配问题，更接近项目管理的实际情况，在实践中得到比较广泛的应用。它通常以工期(或费用、净现值)为优化的目标函数来寻找最优的项目计划，然而，活动工期的分布函数难以准确地估计，资源的最大可获得量通常也会发生变动，项目执行过程中的不确定因素也不能穷尽。因此，资源约束项目计划在执行中不可避免地发生偏离甚至被破坏。对此，许多学者提出制定稳健性的项目计划[1-3]，项目计划稳健性的直观含义是：一个计划能够承受由于不可控因素导致活动工期的“较小”的增加(即对项目工期产生有限的影响)，则称该计划具有稳健性[1-2]。

Goldratt[4]提出在活动之后插入缓冲区，以增加项目计划的稳健性。在插入缓冲区之前，必须确定活动之间的资源依赖关系，识别出关键链(Wiest[5]称之为关键序列)，否则无法确定缓冲区的插入将对其他活动产生哪些影响，而Goldratt[4]并未说明识别关键链的优化方法。在此，关键链是指由活动之间的技术优先关系和资源依赖关系以及总时差为零的活动组成的路径。刘士新等[6]、赵道致等[7]、王淑云等[8]、王仁超等[9]提出各活动之后缓冲区的设定方法。

Van De Vonder等[2]研究了项目工期与稳定性之间均衡问题，但没有说明如何建立资源链接，如何确定最晚项目计划(right-justified schedule)，不能保证活动时差的正确性。

AI-Fawzan 与Haouari[3]以项目中所有活动的自由时差之和作为稳健性的度量指标，建立了以项目工期和稳健性为优化目标函数的双目标优化模型，Abbasi 等人[10]研究了它的有效求解算法。

Kobylański与 Kuchta[11]研究表明，AI-Fawzan 与Haouari[3]方法未必能达到制定稳健性项目计划的目的。因此，Kobylański与 Kuchta[11]提出用项目中活动自由时差与工期比例的最小值(或活动自由时差的最小值)作为度量稳健性的指标。在一个既定工期T的约束下，求解稳健性最大的项目计划。该度量方法在一定程度上达到了制定稳健性项目计划的目的，缺陷在于：Kobylański与Kuchta[11]未说明如何确定活动之间的资源依赖关系，无法确定自由时差的正确性；T值如何确定尚无有效方法；该优化模型为二次优化的NP难问题，需要有效的求解算法；若T值等于资源约束项目计划最短工期时，那么，制定的稳健性项目计划的稳健性指标值都为零，等价于资源约束项目计划。

尽管前人提出制定稳健的项目计划[1-3]，但根据前人[1-3，10-12]对项目计划稳健性的研究来看，尚未发现对项目计划的稳健性进行系统的分类和研究，难以把握项目计划稳健性的关键问题，因此出现了上述问题。

崔万安和王先甲[13]把项目计划的稳健性划分为内在稳健性(Intrinsic robustness)和外在稳健性(Extrinsic robustness)，并对内在稳健性的影响因素进行了分析。其中，外在稳健性是指在内在稳健性确定的情况下，在最早项目计划中的部分或全部活动之后增加缓冲区，因此使新的项目计划工期对活动工期变化的不敏感性的增加称为外在稳健性。在此，缓冲区(buffer time)是指在活动i的自由时差之上增加的一段时间Δbi，活动推迟至此区间完成，不影响其后开始的活动，因此将这段时间称为缓冲区。

本文对外在稳健性的影响因素、度量方法进行分析。

二、外在稳健性的影响因素

缓冲区的大小、缓冲区的插入位置、活动之间的资源依赖关系这三个因素直接影响外在稳健性的大小。

(一)缓冲区的大小

如果确定在哪个(或哪些)活动之后插入缓冲区，则缓冲区越大，活动工期的变化对项目工期的影响就越不敏感。如图1，最大资源可获得量R=5个单位，矩形及其内的字母表示活动及其编号，其水平方向长度表示活动工期，垂直方向长度则表示所需资源量；若确定在最早项目计划中的活动G之后插入缓冲区3个单位，也就是项目的计划完成工期为14个单位，很显然，由此增强的项目计划稳健性是以延长项目工期为代价的。

图1 资源约束项目计划

(二)缓冲区的插入位置

如上所述，若确定图1的项目计划完成工期为14个单位(即比最早项目计划的项目工期延长3个单位)，那么，有多种插入缓冲区的方案，不同方案得到的项目计划对活动工期变化的敏感性不同。如方案1：在A、C、G后各插入1个单位的缓冲区，B之后插入3个单位缓冲区，A、B、C、D、G的最早开始时间分别变为0、0、5、7、10；如方案2：将3个单位的缓冲区都插入到A之后，其他活动之后不插入缓冲区，A、B、C、D、G的最早开始时间分别变为0、0、7、4、11；等等。显然，方案1得到的项目计划比方案2要好，对于方案2，若C或G的工期只要稍微延长，项目工期就会超过14个单位，但对于方案1，即便A、C、G的工期都延长一个单位，项目工期仍可保持在14个单位，刚好按计划完成。

(三)活动之间的资源依赖关系

一个活动完成之后其释放的资源究竟分配给哪个(或哪些)活动，一个活动究竟从哪个(或哪些)活动获取所需资源。如图1所示，在时刻t=4时，当A、B完成后，其释放的资源可以分配给C、D，在时刻t=8时，C、D释放的资源可以分配给G，分配方法有多种。如方法1：A释放的资源全部分配给C，C恰好获得所需资源，B释放的资源分配给D一个单位(剩余资源不分配)，D获得所需资源，C释放的资源分配给G，G恰好获得所需资源；方法2：B释放的资源全部分配给C，A释放的资源分配给C、D各一个单位，这时C、D得到所需资源，D释放的资源分配给G一个单位，C释放的资源分配给G两个单位，G得到所需资源。这样由方法1可以确定两条路径，即A→C→G，B→D，前一条路径比后一条路径长3个单位；而由方法2可以确定3条等长的路径，即A→C→G，B→C→G，A→D→G；方法1只需要对路径A→C→G重点控制，而方法2则需要对3条路径进行重点控制，显然后者的控制难度就更大一些。对于这两种方法，即便在同一位置插入相同大小的缓冲区，项目计划的稳健性也不一定相等。

上述三个外在稳健性的影响因素具有密切的联系，如果单独考虑一个影响因素而忽视其他因素，则难以把握项目计划稳健性对该因素的敏感程度。活动之间的资源依赖关系是研究外在稳健性的先决条件，如果该因素没有确定，另外两个因素就无法讨论，在图1中，如果在B之后插入1个单位的缓冲区时，究竟哪些活动的开始时间需要向后推迟，无法确定。而一旦活动之间的资源依赖关系确定，则任意一个位置插入缓冲区对活动开始时间乃至项目工期的影响即可确定。因此，下面假定活动之间的资源依赖关系已确定的前提下，研究外在稳健性的度量问题。

三、外在稳健性的度量方法

从缓冲区插入的位置看，可以分为关键活动之后、非关键活动之后，前者还包括一类特殊的情形，即关键序列上的最后一个关键活动之后。在此，关键序列是指考虑活动之间的技术优先关系和资源依赖关系下总时差为零的活动组成的路径。如图1，若建立资源依赖关系后，可以找到A→C→G，B→D两条路径，则A→C→G就是关键序列。

可以在关键序列(或非关键序列)上的每一个活动之后都插入缓冲区，也可以仅在其中部分活动之后插入缓冲区，也可以只在关键序列(或非关键序列)上的最后一个活动之后插入缓冲区，不同的方法，最后带来的项目计划稳健性的增加可能不同。

如图1，假定有A→C→G，B→D两条序列，若在A、C、G之后分别插入一个单位的缓冲区，项目计划工期仍为14个单位，各活动的工期延长只要不超过插入的缓冲区，就不会对紧后活动的开始时间产生影响，若仅限一个活动工期延长，活动A、C、G的工期最大延长量可以分别达到3、2、1个单位而不影响项目计划工期，若3个单位缓冲区全部插入到G之后，则A、C、G的工期最大延长量都可达到3个单位而不影响项目计划工期。对于后一种插入方式，一旦紧前活动不能按计划时间完成，紧后活动就不能按计划时间开始，可能导致资源调度费用、协调费用的增加；对于前一种插入方式，C、G的最大可延长量都小于后一种插入方式，一旦超过其最大可延长量，项目计划工期就会延长，因此将会消耗更多的资源，以及项目竣工投产收入的延迟实现等带来的直接和间接损失。

在此，根据外在稳健性的定义仅考虑缓冲区的插入与项目计划稳健性的增加之间的关系，把外在稳健性的度量指标(E)定义为：不影响项目计划工期的条件下，所有活动工期的最大可延长量中的最小值。即：

E=minj∈Abi.

其中，A为活动的集合；bi为活动i的工期最大可延长量。

四、外在稳健性度量指标E的讨论

E关注的是活动工期延长或完成时间推迟与项目工期的关系。如图1，若有A→C→G，B→D两条序列，存在方案一：在A、C、G之后分别插入一个单位缓冲区后，E值为1；方案二：仅在C之后插入3个单位缓冲区则E值为0；方案三：仅在G后插入3个单位缓冲区则E值为3。显然，对方案二来说，插入缓冲区后并未改善E值，因为G的完成时间不可以推迟，而G则决定了项目计划能否按期完成；但A、C的完成时间均可推迟，从这个意义上讲，E是一种保守的度量方法。

E可等价为求所有关键序列上最后一个活动之后缓冲区的最小值。

在插入缓冲区的值b一定的条件下，求E的最大化问题，实质就是在关键序列之后插入缓冲区b。

E与项目成本双目标优化实质上就是确定外在稳健性增加带来收益的增加与项目工期延长带来成本增加之间的关系。研究外在稳健性必须考虑成本的优化，否则没有意义。

五、结束语

本文对外在稳健性的影响因素进行了定性分析，提出了外在稳健性的度量指标并对之进行了讨论。下一步，我们将通过数学模型，研究外在稳健性增加与项目成本增加之间的数量关系，确定最优的外在稳健性的值。

参考文献：

[1] Willy Herroelen and Roel Leus.Robust and reactive project scheduling：a review and classification of procedures[J].International Journal of Production Research，2004，42(8)：1599-1620.

[2] Stijn Van de Vonder，Erik Demeulemeester，Willy Herroelen and Roel Leus.The trade-off between stability and makespan in resource-constrained project scheduling[J].International Journal of Production Research，2006，44(2)：215-236.

[3] M.A.Al-Fawzan and Mohamed Haouari.A bi-objective model for robust resource-constrained project scheduling[J].International Journal of Production Economics，2005，96(2)：175-187.

[4] Goldratt E M.Critical Chain[M].Great Barrington：North River Press，1997.

[5] Wiest J.D.Some properties of schedules for large projects with limited resources[J].Operations Research，1964，12(3)：395-418.

[6] 刘士新，宋健海，唐加福.基于关键链的资源受限项目调度新方法[J].自动化学报，2006，32(1)：60-66.

[7] 赵道致，廖 华，刘一骝.关键链法：一种新型的项目进度计划方法[J].天津理工学院学报，2005，21(2)：8-12.

[8] 王淑云，朱祥松，李 洁.基于资源约束的扩张关键路径法研究[J].管理工程学报，2006，20(6)：109-111.

[9] 王仁超，欧阳斌，王 琳，等.工程项目计划“关键性”问题拓展研究[J].系统工程与电子技术，2004，26(7)：914-917，923.

[10] Babak Abbasi，Shahram Shadrokh and Jamal Arkat.Bi-objective resource-constrained project scheduling with robustness and makespan criteria[J].Applied Mathematics and Computation，2006，180(1)：146-152.

[11] Przemyslaw Kobylański，Dorota Kuchta，A note on the paper by M.A.Al-Fawzan and M.Haouari about a bi-objective problem for robust resource-constrained project scheduling[J].International Journal of Production Economics，2007，107(2)：496-501.

[12] Hédi Chtourou.Mohamed Haouari A two-stage-priority-rule-based algorithm for robust resource-constrained project scheduling[J].Computers & Industrial Engineering，2008，55(1)：183-194.

[13] 崔万安，王先甲.资源约束项目计划内在稳健性影响因素分析[J].太原理工大学学报(社会科学版)，2010，28(1)：20-23.