鲁棒性视角下的关键链项目调度新方法

张静文， 刘耕涛

(西北工业大学 管理学院，陕西 西安 710072)



鲁棒性视角下的关键链项目调度新方法

张静文， 刘耕涛

(西北工业大学 管理学院，陕西 西安 710072)

探究传统关键链方法在实践应用中出现的问题并提出改进措施。首先剖析出三个方面的不足：第一，基准调度计划不唯一；第二，非关键链的识别方式导致输入缓冲失效；第三，对插入输入缓冲时引起的二次资源冲突问题，现有的解决方法与缓冲的本质作用相背离。据此，基于鲁棒性调度优化的思想，采用理论分析和案例说明相结合，针对三个方面分别提出了相应的解决方案，形成鲁棒性视角下的关键链项目调度新方法。研究结论对于将关键链方法科学地应用于项目管理实践提供了理论指导。

关键链；调度计划；输入缓冲；资源冲突；二次调度

0 引言

Goldratt提出的关键链方法(Critical Chain Method/Critical Chain, CCM/CC)[1]被认为是继经典CPM/PERT(Critical Path Method/Program Evaluation and Review Technology)之后项目管理技术发展中的又一重大里程碑事件。现代项目结构及规模日趋复杂，面临环境日益多变，项目外部的不确定性和风险不断增大；同时，经济全球化导致市场竞争日趋激烈，众多项目对稀缺资源的竞争愈加激烈，经典CPM/PERT已不能适应项目管理实践的需要，而CCM在应对不确定的项目实施环境时具有一定的效果[2]。CCM从人的行为特征、资源约束和活动工期三个方面突破了经典的项目管理方法，是一种管理理念上的提升[3]。然而，任何一种理论或方法都需要根据适用环境的改变而不断改进，针对目前CCM在应用中存在的三个突出问题，本文从鲁棒性(Robustness)调度优化角度，提出一种鲁棒性视角下关键链项目调度新方法。为表述方便，本文中将Goldratt提出的关键链方法称为传统CCM。

1 鲁棒性和关键链中的鲁棒性内涵分析

鲁棒性项目调度作为一种不确定型项目调度理论，是目前项目调度领域的研究热点之一[4，5]。鲁棒性调度指调度计划的稳健性，即能够抵控由于不可控因素导致的计划拖延，使项目的完成过程具有较好的稳定性。Al-Fawzan等人[6]首先将鲁棒性概念真正引入资源约束项目调度问题(Resource-constrained Project Scheduling Problem, RCPSP)，采用资源约束下活动的自由时差之和来度量调度方案的鲁棒性。Vonder等人[7]将调度鲁棒性区分为两类：第一类是质量鲁棒性(quality robustness)，指调度计划对于绩效目标的稳定性，如对项目工期的稳定性；第二类是解的鲁棒性(solution robustness)，指调度过程的细节，如活动开始时间的稳定性。Chtourou等人[8]针对活动工期拖延的RCPSP，提出一种基于优先规则的两阶段算法，借助12种指标最大化调度计划的鲁棒性。刘琼[9]等人以鲁棒性和多项目工期为目标研究多项目鲁棒性调度模型，然而他们并没有关注到传统CCM在应用过程中的一些最基本的问题。

关键链是在满足资源约束和活动间相互依赖的关系下，制约项目工期的最长的活动链。根据活动的估计工期和资源限量识别出项目网络的关键链和非关键链。在非关键链汇入关键链入口处设置FB，用来吸收由于非关键活动的拖延对关键链的影响；在关键链末端设置PB，用来吸收由于关键链上的活动拖延对项目工期的影响。CCM中蕴含的鲁棒性思想分析如下：

(1)缓冲机制层面的鲁棒性：CCM通过在调度计划中设置缓冲机制来消除不确定因素对实施调度计划的影响，缓冲的本质作用是吸收活动工期的拖延并将其在项目执行过程中进行消化。CCM的精髓在于缓冲机制，而缓冲使得项目计划具有一定的抗外界变化环境干扰的鲁棒性特征。

(2)缓冲微观层面的鲁棒性：在CCM计划中，各FB的大小通常由对应的非关键链上活动的安全时间确定，唯一的PB的大小由关键链上的活动的安全时间来确定。因此，从时差角度分析，设置FB本质是对某条非关键链上所有活动时差的集中管理，设置PB本质是对关键链上所有活动时差的集中管理；各FB分散在调度计划的各个阶段，期望保证调度计划在执行过程中的稳定性，体现了解的鲁棒性；PB置于调度计划末端，期望保证项目工期的稳定性，体现了质量鲁棒性。因此，从两类缓冲的位置和大小的微观层面看，FB和PB分别体现了解的鲁棒性和质量鲁棒性。

尽管CCM中蕴含了鲁棒优化调度的思想，然而传统 CCM中仅考虑项目工期目标，忽略了能体现关键链重要特质的鲁棒性指标，所以传统的关键链概念是狭义上的，这也直接制约了传统CCM更广泛地应用于实践。本文首先剖析了传统CCM在实践应用中的三个方面的不足，据此针对每个方面分别提出了基于鲁棒优化调度思想的改进策略，形成了鲁棒性视角下的关键链项目调度新方法的主要内容。

2 传统CCM的不足

图1 包含10个实活动的项目网络及参数

2.1 存在多个基准调度方案

在某一资源限量下，最短项目工期可能对应多个不同的基准调度方案S，每个S都可以确定活动网络的关键链和非关键，但是究竟选择哪一个基准调度计划作为插入FB后执行二次调度计划的依据，传统CCM没有涉及此问题。例如对图1中的活动网络，当资源限量R=7时，采用分支定界算法获得的最短项目工期为26，对应两种不同的基准调度计划如图2所示。

图2a 基准调度计划S1

图2b 基准调度计划S2

在图2中，虚线链接起来的活动构成CC。在图2a中，CC为4→5→6→8→10，在图2b中，CC为2→4→7→5→6→8→10。在这种情形下，选择哪一个作为实施CCM的基准调度计划来确定输入缓冲的位置和尺寸，需要进一步决策。请注意，这点与传统CCM中提到的存在多条CC的情形不同，后者提及的多条CC指基于同一个S，基于网络结构中的链路结构关系而形成的多条CC。

2.2 输入缓冲的设置方式

2.3 输入缓冲引起的资源冲突问题

3 改进的CCM

针对传统CCM中存在的上述三个方面的问题，我们分别提出了解决方法，形成了基于鲁棒性视角下的新的CCM。

3.1 确定唯一的基准调度计划

当最短项目工期对应多个S时，如何确定某个S作为实施CCM的基准调度计划。我们提出两种解决方案：

(1)客观的方式

很清楚，不同的调度计划中具有不同的关键活动集合和非关键活动集合，因此不同S中具有不同的时差分布和不同的输入缓冲设置状态(位置及尺寸)。CCM的基本思想是通过插入缓冲来确保调度计划在实施中的稳定性。基于此，我们提出从鲁棒性目标的角度进一步区分多个调度方案的优劣。借鉴基本RCPSP中的鲁棒性度量方式来量化每个S的鲁棒性指标，比如最直观地，以调度计划中所有非关键活动的自由时差和来体现鲁棒性。对于图2中的两种调度方案S1和S2，从鲁棒性调度优化角度分析，自由时差在S1中的分布比在S2中更分散，即S1中具有更多的非关键活动，因此S1对活动拖延的吸收能力比S2强。采用Lambrechts等人[13]提出的基于时差效用函数的鲁棒性度量公式来量化两种调度方案的鲁棒性：

(2)主观的方式

尽管最短项目工期可能对应多个基准调度方案，但是通常此基准调度方案的总数较少。此时项目经理可以根据其实践经验来选择其中一个作为实施CCM的基准调度方案。比如，如果在某个基准调度方案的CC中，包含了较多对项目实施过程产生重大影响的活动，则此时就可以选此方案作为基准调度方案。例如对图2中的S1和S2，两种方案的差别在于是否选择活动2和活动7作为关键活动，如果根据项目经理的判断，这两个活动的工作内容对整个项目的实施起着关键性的作用，则此时就选择S2作为基准调度方案，否则，将选择S1。进一步，基于选定的基准调度方案确定FB(位置和尺寸)和PB的尺寸。

3.2 输入缓冲的合理设置

图3 基于图2a设置各FB

改进的设置FB的方法使得各条FB起到了应有的作用，同时尽可能地保证关键活动的如期执行，最终将使实际进度更接近于制定的调度计划，同时也能够体现出CCM是一种前摄性的鲁棒调度优化方法。

3.3 消除资源冲突的鲁棒性策略

针对2.3中的问题设计解决方法，传统CCM并没有充分考虑所获得的二次调度计划在实施中的效果。通常项目经理希望实际进度与调度计划的偏离尽可能地小，以此来减小由于计划变更导致的转换费用并节省时间。同时，项目经理也需要制定出的调度计划具有一定的柔性，即当实际活动工期偏离计划工期时，对进度计划作最小的调整即可以重新获得较优的调度计划。因此，从实施项目计划的动态角度出发，项目经理期望CCM给出的调度计划能够具有较好的鲁棒性。所以，基于鲁棒调度优化的思想，针对插入FB导致的资源冲突问题，本文提出一种启发式的协调策略，即在二次调度计划中的活动偏好规则。首要地，二次调度计划基于基准调度计划进行，具体说明如下：

(1)从起始时间开始，根据时间点从前向后依次插入每个FB；当发生资源冲突时，仅解决当前缓冲插入位置到下一个输入缓冲插入点之间的资源冲突。

(2)当插入FB时导致发生资源冲突的活动同时涉及关键活动和非关键活动时，首先保证关键活动的开始时间不变，向右移动非关键活动，同时与此非关键活动相联系的FB中应减去后移的时间量。

(3)当插入FB后导致发生资源冲突的活动仅涉及关键活动时，此时必须后移关键活动的开始时间。并且，当后移某个关键活动时，将从PB中减去关键活动后移的时间量。PB被消蚀完之后，继续有关键活动后移表示项目工期增加。

(1)实际项目进展中，非关键链上活动的拖延未超过其链路具有的自由时差时，即缓冲的实际消耗并未引起资源冲突。尽管二次调度计划后移了紧随其后的关键活动的开始时间，但是此时可以不根据二次调度计划的时间开始关键活动，而根据其最早开始时间开始紧后的关键活动，这相当于在二次计划中删掉了多余的缓冲时间，其之后的活动调度计划整体前移，而不必对计划进行重新调度。

(2)起到了将PB分散到调度计划过程中的效果。在项目实施中，当某个关键活动拖延时，其拖延通过链条的传递作用将影响之后的每个关键活动，如果仍保持之后的非关键活动的开始时间不变，则很可能引起后面调度计划中多处出现资源冲突。然而，通过上面消除冲突的策略，在二次调度中将某些关键活动后移的同时也相当于给被后移的关键活动的紧前关键活动设置了缓冲，当前面的紧前活动有拖延时，此处设置的FB可以吸收这种拖延，而由于后推关键活动导致的资源冲突问题在实施二次调度计划过程中已经考虑到了，最终达到项目实际进展中对调度计划偏离尽可能小的目的。因此，如此设置FB和消除资源冲突的策略，相当于将PB分散到了调度计划中的一些关键活动之后。

基于上述三个方面的研究：(a)根据鲁棒性目标确定唯一的基准调度计划；(b)结合基准调度计划和网络结构关系识别非关键和设置FB；(c)消除FB引起的资源冲突的启发式二次鲁棒性调度策略，本文形成了鲁棒性视角下的新的CCM。

4 结束

传统CCM的管理理念得到了认可，然而它在项目管理实践中的应用却面临一些困惑。本文针对传统CCM在应用过程中的三个不足提出解决方案。首先，对于最短项目工期对应的基准调度不唯一的情形，提出了进一步从鲁棒性目标角度或根据项目经理的知识经验来确定唯一的基准调度方案。其次，针对设置FB时忽略了基准调度计划而导致FB失效，提出了将基准调度计划和网络结构链路关系结合起来设置FB的方法。第三，插入FB可能引起二次调度中的资源冲突问题，分析了现有方法的缺陷，提出了基于鲁棒调度优化思想的解决缓冲资源冲突的策略。研究工作期望对CCM在项目管理实践中的应用提供指导。

由于偏幅所限，本文仅通过一个实例说明了鲁棒性视角下的关键链项目调度新方法的有效性，紧随的研究工作将从优化模型的构建、鲁棒性指标的设计及有效性测度、开发模型的求解算法和大规模算例的仿真测试等方面，比较新方法和传统CCM的效果，以进一步从理论上证明新方法对实践的有效性。另一方面，CCM在本质上是一种前摄性的鲁棒项目调度优化方法，而目前对CCM的定义仅局限于工期最短的框架下，鲁棒性目标并没有在CCM方法中体现出来，且工期最短的调度方案并不一定鲁棒性也最好。因此，同时考虑工期和鲁棒性目标的多目标CCM将是我们下一步的研究内容。

[1] Goldratt E M. Critical Chain[M]. Great Barrington: The North River Press Publishing Corporation, 1997.

[2] Herroelen W, Lues R. Project scheduling under uncertainty: survey and research potentials[J]. European Journal of Operational Research, 2005, 165(2): 289-306.

[3] 张静文,李若楠.关键链项目调度方法研究评述[J].控制与决策,2013,28(9):1281-1287.

[4] Deblaere F, Demeulemeester E, Herroelen W. Reactive scheduling in the multi-mode RCPSP[J]. Computer & Operations Research, 2011, 38(1): 63-74.

[5] 庞南生,孟俊姣.多目标资源受限项目鲁棒调度研究[J].运筹与管理,2012,21(3):27-32.

[6] Al-fawzan M A, Haouari M. A bi-objective model for robust resource-constrained project scheduling[J]. International Journal of Production Economics, 2005, 96(2): 175-187.

[7] Vonder S V, Demeulemeester E, Herroelen W, Leus R. The use of buffers in project management: the trade-off between stability and makespan[J]. International Journal of Production Economics, 2005, 97(2): 227-240.

[8] Chtourou H, Haouari M. A two-stage-priority-rule-based algorithm for robust resource-constrained project scheduling[J]. Computer & Industrial Engineering, 2008, 55(1): 183-194.

[9] 刘琼,林魁,张超勇,朱海平.基于关键链多项目鲁棒调度[J].计算机集成制造系统,2012,18(4):813- 820.

[10] 刘士新,宋健海,唐加福.资源受限项目调度中缓冲区的设定方法[J].系统工程学报,2006,21(4):381-386.

[11] 彭武良,金敏力,纪国焘.多模式关键链项目调度及启发式求解[J].计算机集成制造系统,2012,25(1):123-131.

[12] 田文迪,崔南方,付樟华.基于分支定界法的关键链项目计划重排[J].计算机应用研究,2011,28(11):4035- 4039

[13] Lambrechts O, Demeulemeester E, Herroelen W. A tabu search procedure for developing robust predictive project schedules[J]. International Journal of Production Economics, 2008, 111(2): 493-508.

An Improved Critical Chain Project Scheduling Method in thePerspective of Robustness

ZHANG Jing-wen, LIU Geng-tao

(School of Management, Northwestern Polytechnical University, Xi′an 710072, China)

We investigate some puzzles in practice from the traditional critical chain method (CCM), and several correcting measures are put forward. Three pitfalls of the CCM are pointed out in this paper. Firstly, the baseline schedules are not unique. Secondly, the effect of feeding buffers fails because of the improper means to identify non-critical chains. Thirdly, the existing ways, which are used to eliminate the second resource conflicts resulting from the insertion of feeding buffers, deviate from the nature role of feeding buffers. Accordingly, based on the thought of robust optimization, three solutions are respectively presented to overcome the three drawbacks by integrating theoretical analyses and case interpretations. Therefore, a new critical chain project scheduling method is formed based on the three aspects of improvements on the traditional CCM. The results show that our new CCM can provide the scientific instructions for project managers when they adopt the CCM in reality.

critical chain; schedule; feeding buffer; resource confliction; rescheduling

2013- 07-17

国家自然科学基金资助项目(70702026)；陕西省自然科学基金资助项目(2011JQ9001,2015JM7368)；西北工业大学管理振兴及管理学院优秀青年教师培养资助计划(RW201309)；校研究生创业种子基金资助项目(Z2014075)

张静文(1976-)，女，陕西人，副教授，研究方向为项目调度优化的理论和方法。

C935，F224.3

A

1007-3221(2015)03- 0197- 08