基于关键链的项目进度计划方法的研究

基于关键链的项目进度计划方法的研究刘建桥，盛步云，王辉（武汉理工大学机电工程学院，湖北武汉430070）

来稿日期：2018-08-24基金项目：国家重点研发计划项目（2016YFB1101700）；湖北省自然科学基金（2015CFA115）作者简介：刘建桥，（1992-），男，湖北随州人，硕士研究生，主要研究方向：制造系统集成与信息化技术；盛步云，（1964-），男，湖南华容人，博士研究生，博士生导师，教授，主要研究方向：数字制造技术

1引言随着经济的发展和社会的进步，现代项目变得越来越大，所涉及到的资源越来越多，复杂程度也越来越高，项目进度计划的制定也变得更加困难，尤其是在面对多资源约束和环境不确定性等情况时，项目频繁出现进度延误甚至返工等现象。传统的关键路径法（CriticalPathMethod，CPM）和计划评审技术（ProjectEvaluationandReviewTechnique，PERT）一直是制定项目进度计划的有效方法[1]，

并在一些项目中取得了良好的效果，但是它们都只考虑了在资源不受限条件下的任务间的逻辑关系及任务的时间裕度，一旦资源发生了冲突，运用它们制定的项目进度计划就失去了存在意义。为解决传统计划方法存在的缺陷，1997年来自以色列的管理大师Goldratt提出关键链方法（CriticalChainMethod，CCM）[2]，运用此方法制定进度计划时不仅需要考虑任务之间的逻辑约束关系，而且还需要考虑资源约束关系，并根据心理学中帕金森定律以及学生综合症的情况，对任务工期进行压缩，同时设立缓冲区以应对不确定因素[3]。

当前针对关键链法的项目进度计划的研究大多集中在关键链的识别及缓冲区大小的计算上。文献[4]面对资源约束提出基于动态规划的启发式算法来确定关键链和非关键链；文献[5]针对信息系统研发项目设计出改进的资源调度法识别关键链；文献[6]提出一种混合遗传算法，通过对项目任务排序来识别关键链；文献[2]

提出的剪切法和文献[7]建议采用根方误差法计算缓冲区时间；文献[8]考虑了项目运行过程中的复杂情况，提出了进度计划中估算缓冲的新思路；文献[9]根据活动间的依赖关系，提出缓冲区大小确定方法。针对关键链方法在项目进度计划制定里面的应用，国内外专家学者做了很多研究和尝试，但都未综合分析研究多资源约束、环境不确定性对关键链识别及缓冲区计算产生的影响。综上所述，在综合考虑多资源约束、环境不确定性等因素对任务影响的基础上，提出基于关键链的项目进度计划方法，制定出工期最小项目进度计划，方便管理人员全方位掌握项目的实际进展，确保项目如期完工。

摘要：为解决项目进度计划因资源冲突及环境不确定性而导致的计划失效、工期延误等问题，在传统项目进度计划方法的基础上引入关键链法，通过对现存的关键链识别算法及缓冲区估算方法进行分析研究，提出基于关键链的项目进度计划方法。该方法采取基于优先规则的启发式算法识别关键链，在充分考虑项目中的多资源约束、环境不确定性等因素的基础上设置缓冲区，制定出工期最小项目进度计划。最后，通过对项目实例进行分析验证，表明使用该方法制定的项目进度计划是可行的。关键词：多资源约束；关键链；启发式算法；缓冲区；项目进度计划中图分类号：TH16；TH186文献标识码：A文章编号：员园园员-3997（圆园19）02-0005-04

ResearchontheProjectSchedulePlanBasedontheCriticalChainLIUJian-qiao，SHENGBu-yun，WANGHui

（SchoolofMechanicalandElectronicEngineering，WuhanUniversityofTechnology，HubeiWuhan430070，China）

粤遭泽贼则葬糟贼：Tosolvethefailureanddelaysoftheprojectscheduleplancausedbytheresourceconflictsandenvironmentaluncertainty，onthebasisofthetraditionalprojectschedulingplanningmethod，thecriticalchainmethodwasintroduced.Onthestudyoftheexistingcriticalchainidentificationalgorithmandthebufferestimationmethod，theprojectscheduleplanningmethodsbasedoncriticalchainwereproposed.Themethodadopttheheuristicalgorithmbasedonthepriorityrulestoidentifythecriticalchain，afterthefullconsiderationofthemultiresourceconstraintsanduncertaintiesoftheproject，thebufferwasset，theprojectscheduleplanwascompiledwithminimumtotalduration.Finally，byanalyzingtheprojectexample，theresultsshowedthatthemethodforthepreparationofprojectscheduleplanisfeasible.KeyWords：MultipleResourceConstraints；CriticalChain；HeuristicAlgorithm；BufferSetting；ProjectSchedulePlan

酝葬糟澡蚤灶藻则赠阅藻泽蚤早灶驭酝葬灶怎枣葬糟贼怎则藻机械设计与制造第2期

圆园19年2月52关键链识别模型的构建及求解

关键链法（CCM）是在传统的关键路径法（CPM）的基础上发展而来的，它在制定项目进度计划时不仅考虑了任务间的逻辑关系，而且还考虑了任务间的资源限制条件。因此关键链的识别就是先根据项目任务间的前后关系及任务的持续时间确定网络图，再根据资源冲突情况修改任务的紧前关系，最后得到的总时间最长的那条路径就是关键链。2.1关键链识别模型的构建

假设项目总共有N个任务，用vi代表第i个任务，S（vi）代表任务vi的开始时间，D（vi）代表任务vi的持续时间，Pvi代表任务vi

的紧前任务集合。项目总共有K类资源，且所有的资源都是可反

复利用的，vki代表任务vi需要第k类资源，r（vki）代表任务vki所需要的第k类资源的数量，At代表在（t，t+1］时间段内同时实施的任务集合，Rtk为At时间段内第k类资源的供应量。综合上述假设和使用的符号，推理得出识别关键链的数学模型如下所示：MinT（1）

s.t.S（vi）+D（vi）燮S（vj）；vi沂P

v（2）

vi沂At

移r（vk

i）燮Rtk；k=1，2，…，K；t=1，2，…，T（3）

S（vi）叟0；i沂｛1，2，…，N｝（4）

式（1）是目标函数，T为项目工期；式（2）定义紧前约束，也就是某任务只能在其所有紧前任务全都结束后才可以开始；式（3）定义资源约束，也就是在任意时间段内，项目任务对每类资源的需求量都必须小于该资源的供应量；式（4）定义任务的时间约束，也就是项目任务的开始时间都不能小于零。2.2关键链识别模型的求解

采取基于优先规则的启发式算法对识别模型进行分析，首先需要根据项目任务间的逻辑关系得出初始网络图，然后针对项目任务工期的不确定性，采用PERT三点估计法估算出第i项任务的最乐观时间值ai，最可能时间值mi，最悲观时间值bi，考虑到心理学中帕金森定律以及学生综合症的情况，需要对任务工期进行压缩，因此选取最乐观时间值ai作为任务工期。按任务尽可能晚开始制定出初始项目进度计划，选取总时间最长的那条路径为关键路径，接着在此基础上，从后往前循环调度，根据优先规则解决多资源约束，完成对识别模型的求解。2.2.1优先规则

如果任务遇到资源不足的情况，则按照下面的顺序对冲突的任务指定优先级：（1）未完成任务优先级最高；（2）关键路径上的任务的优先级高于非关键路径上的任务的优先级；（3）非关键路径上的任务，按照开始时间从大到小的顺序依次分配优先级，时间相同时，按照任务顺序分配优先级。2.2.2启发式算法的主要步骤

根据上述优先规则所设计的启发式算法流程，如图1所示。主要步骤如下：

第一步：从j=1开始，确定决策点tj。即在未调整任务集Qj中选择最迟结束的任务的完成时间作为决策点，起始决策点是项目的结束时间。第二步：找出可行任务集Wj。即未调整任务集Qj中所有完

成时间与决策点一样的任务的集合，令Q忆j=Qj-Wj。第三步：综合考虑可行任务集Wj与已调整任务集中开始时间小于决策点的任务并按照资源种类分为k个资源任务集合Ak。

YNN

NYY

开始（1）未调整任务集Qj中设立决策点tj

（2）找出可行任务集Wj

（3）确定K个资源任务集Ak

（4）计算Ak的资源量rit及资源总量Rtk

（5）判断rtk>Rtk

（6）对Ak中活动分配优先级vki（n）

（7）确定不变任务集BAk及关键活动vBAk和需调整任务集BAk

（8）修改vBAk的紧前工序集及未调整任务集Qj

（9）k=k+1

（10）j=j+1结束

k>K？

Qj

=埸覫

图1基于优先规则的启发式算法流程图Fig.1TheFlowChartofHeuristicAlgorithmBasedonPriorityRules

第四步：从k=1开始，计算资源任务集合Ak中全部任务对于k资源的需求总量rtk及此时间段内项目资源供应量Rtk。

第五步：比较此时间段内k资源需求量rtk与资源供应量Rtk

的大小，若rtk>Rtk，则表示此时间段k资源冲突，执行第六步；否

则，转到第九步。第六步：根据前文提到的优先规则按优先级别从高到低的

顺序给Ak中的全部任务排序，即得到vki（n）。第七步：在集合Ak中根据优先级别依次累加任务vki（n）消耗的k资源的数量，直至超过供应量Rtk为止，此时得到不变任务集BkA及其中具有最大开始时间的任务VkA和需调整任务集BkA。

第八步：将需调整任务集BkA中的任务加入到VkA的紧前任务集中，数学公式为：PVkA=PVkA∪BkA；将需调整任务集BkA中的任务归入未调整任务集Qj中，数学公式为：Qj=Q忆j∪BkA。

第2期刘建桥等：基于关键链的项目进度计划方法的研究6