张立辉, 邹 鑫, 乞建勋, 孟宪威

(华北电力大学 经济与管理学院，北京 102206)



重复性建设项目中确定关键路线的方法研究

张立辉, 邹 鑫, 乞建勋, 孟宪威

(华北电力大学 经济与管理学院，北京 102206)

本文提出了一种确定重复性建设项目关键路线的新方法。借助约束线，首先给出了工序间存在各种约束条件(时间和距离约束)下潜在关键点的确定方法；为处理大规模项目，进一步提出了与图示法相对应的数值算法。以此为基础，提出了确定关键工序和关键路线的具体步骤，并定义和分析了三种不同类型的关键工序。与现有的方法相比，本文提出的确定关键路线的方法更为准确，适用性更强，而且有利于调度优化目标的实现。

项目管理；关键路线；约束；潜在关键点；重复性项目

0 引言

重复性建设项目是指在建设工程的每个阶段(unit)各个工序不断重复进行的项目，如高速公路、管道工程、铁道工程、隧道工程、高层建筑等。关键路线法(Critical Path Method, CPM)是解决一般项目调度问题强有力的工具[1]，但对于重复性项目，CPM就存在很多的不足之处[2]。主要表现在：①不能保证资源的连续性[3]；②不能表示工序之间在距离上的约束[4]；③不能表示项目进展的工作效率[5]；④在某个工序或约束发生变化时，对整个调度方案进行更新比较困难[6]。由于重复性项目在工程中极其常见，因此涌现了许多对重复性项目调度方法的研究[7～9]。这些方法虽然各有差异，但基本上都是以“时间—距离”的二维图展示工程项目进度计划情况。因此在本文中统一将它们归入重复性项目调度方法(Repetitive Scheduling Method, RSM)，并以纵坐标表示时间，横坐标表示工程阶段。

重复性建设项目研究在我国具有很大的应用价值。我国现在处于基本建设大发展时期，“十二五”期间全国铁路运营里程将由现在的9.1万公里增加到12万公里左右，公路网总里程将由“十一五”末的230万公里达到450万公里，随着城市的发展其它如地铁、高楼项目如雨后春笋般发展。而且这些项目大多具有投资大、周期长的特点，因此有必要针对重复性建设项目调度与优化问题进行研究。国内学者钱昆润等将重复性项目调度称为“流水施工”[10]；蒋根谋[11]等称其为线性计划方法，并介绍了线性进度计划的绘制方法和步骤。但总体来看，国内对此类问题的研究尚处于介绍和探索阶段。

关键路线的长度直接决定项目的总工期，因此确定关键路线是项目调度的核心问题之一。许多学者提出了RSM中确定关键路线的方法。Harmelink和Rowings[9]首先区分了工序的类型及其在RSM中的意义，然后提出了一种通过上行搜索和下行搜索确定关键路线的方法。Harris和Ioannou[3]提出的关键路线则是由技术约束、可用资源、资源连续性要求共同决定的。上述确定关键路线的方法都是基于工序之间只存在最小约束的假定。Kallantzis和Lambropoulos[12]则提出了在工序之间同时具有最小和最大两种约束的RSM中关键路线的确定方法。Ammar 和Elbeltagi[13]提出了一种考虑资源连续性约束条件下的确定关键路线的方法，该方法是假定生产效率恒定不变，并且存在开始-开始和结束-开始约束、以资源连续性为前提的寻找关键路线的方法。在确认关键路线方法的基础上，Harmelink[14]、Lucko[15]等提出了RSM中的时差分析方法，Mattila和Abraham[16]等人提出了资源均衡等优化方法。

但是上述确定关键路线的方法都存在或多或少的问题，主要表现在：①对关键路线和关键工序的定义不明确，导致同一个项目可能出现不同的关键路线和关键工序；②有的方法会导致错误关键工序和关键路线的产生；③寻找关键路线的方法依赖于特定条件，缺乏普遍适用性(详见第4节)。

本文将提出确定重复性项目关键路线的新方法：首先利用约束线正向确定所有潜在关键点，然后从项目结束点反向确认所有的关键点、关键工序和关键约束，最后连接所有关键工序和关键约束的路线就是关键路线。这种方法避免了现有方法的一些错误，准确地确定关键路线，同时又有更强的适用性。为了能有效地处理大规摸项目，本文将进一步提出不依赖于RSM图形表示的数值算法。

1 基本概念

图1 工序的类型及图形表示

重复性项目中的工序主要分为三类，分别是线形、块形和条形工序。如图1，工序A和B为线形工序，要求按单元顺序连续不间断地完成所有单元上的工作。线形工序在单位单元上的工作表示为一个线段，线段的两端分别表示该单元的开始和结束时间；工序C为块形工序，要求在所有单元内的工作必须同时开始、同时结束。块形的底边和顶边分别表示工序的开始和结束时间；工序D为条形工序，只要求在某一个单元的开始或结束位置执行作业任务。条形工序是一种特殊的块形工序。特别地，本文假定条形工序只位于单元的结束位置。设“定义域”Di表示工序i所涵盖的单元。如图1，有DA={2,3,…,6},DB={1,2,…,6},DC={3,4}和DD={5}。

2 潜在关键点的确定

工序之间的约束关系一般可分为时间和距离约束，例如混凝土浇注和拆模之间需要有最小时间约束；为避免干扰，在高速路工程中沙石和沥青铺设之间需要有最小距离约束。时间约束又包含四种类型，分别为“开始-开始(SS)”、“开始-结束(SF)”、“结束-开始(FS)”和“结束-结束(FF)”。令CSS、CSF、CFS和CFF分别为满足对应类型的时间约束的工序对集合；CD包含所有满足距离约束的工序对。定义关键点为处于关键工序上与其他关键工序相连接的点。在确认关键路线的过程中，只有工序对中的约束关系确定的约束点才有可能成为关键点，因此定义其为潜在关键点(pCP)。

2.1 时间约束下潜在关键点的确定

图2(a)中，(A,B)∈CFS，即在各单元上工序A完成α(≥0)天后工序B才能开始。为了确定潜在关键点，首先确定工序A对B时间约束的边界线，记为TCL(A→B)。因为工序A和B满足(FS)型时间约束，所以边界线可通过上移工序Aα天，再向左移一个单元后得到，如图2(a)中虚线所示。TCL(A→B)与A之间的阴影区域对工序B而言就是禁入区域，否则将违背时间约束。然后向下移动工序B，直至其与TCL(A→B)相切时停止。此时工序B上的切点就是被来自工序A的约束所确定的潜在关键点，记为pCP(B←A)；而在工序A上与pCP(B←A)相对应的约束点也被确认为潜在关键点，记为pCP(A→B)。图2(b)-(d)分别给出了其他三种类型时间约束下潜在关键点的确定过程。当潜在关键点确定后，工序B在各个单元上的最早开始时间也就随之确定。

图2 时间约束下确定潜在关键点

上述确定潜在关键点的方法属于图示法。这种方法不能有效地处理大规模的项目，因此本文进一步提出了与图示法对应的数值算法(简称算法1)。对于任意具有时间约束关系的工序对(i,t)，算法1能自动确定潜在关键点pCP(i→t)和pCP(t←i)，以及工序t在各单元的最早开始时间-sij。令dij表示工序i在第j单元的工期。

算法1

步骤0 初始化参数λ和γ.若(i,t)∈CSF∪CFF,λ=1;否则λ=0.若(i,t)∈CFS∪CFF,γ=1;否则γ=0;

步骤1 初始化工序t在各单元上的最早开始时间.

stj*:=∑k∈Ωdtk,Ω={j|j≤j*-1,j∈Dt}(规定∑k∈φdtk=0);

步骤2 计算工序t的上移量Δt以及潜在关键点所在的单元jp,令D*=Dt∩Di;

步骤3 修正工序t的最早开始时间.stj:=stj+Δt,j∈Dt;

步骤4 确定潜在关键点.pCP(i→t)={jp-1+γ,sijp+γdijp},pCP(t←i)={jp-1+λ,stjp+λdtjp}。

块形或条形工序是一类特殊的工序，要求在所有单元上的工作必须同时开始、同时结束。这使得块形工序对其他工序的时间约束线是顶边的平行线，而条形工序则是一个点，此时潜在关键点位于块形工序顶边的左侧或者条形工序的顶端，如图4(a)和(b)中的工序A和B；反过来，其他工序对块形或条形工序的时间约束线通过将该工序上移α天后得到，此时潜在关键点位于块形工序底边的右侧或者条形工序的底端，如图3(a)和(b)中的工序C和A。

2.2 距离约束下潜在关键点的确定

图4中，(A,B)∈CD，即工序A和B在任意时刻都要保持至少θ(≥1)单元的距离。同时间约束下潜在关键点的确定方法一样，首先确定工序A对B距离约束的边界线，记为DCL(A→B)，该边界线可通过左移工序Aθ个单元后得到，如图4中虚线所示。然后向下移动工序B直至其与DCL(A→B)相切时停止。此时工序A和B上的切点就分别是由距离约束所产生的一对潜在关键点，即pCP(A→B)和pCP(B←A)。

图3 块(条)形工序潜在关键点的确定

图4 距离约束下潜在关键点的确定

类似于算法1，本文提出了距离约束下确定潜在关键点的数值算法(简称算法2)。对于任意具有距离约束关系的工序对(i.t)，算法2按如下步骤执行。

算法2

步骤1 与算法1相同;

步骤3 与算法1相同;

3 关键路线的确定和关键工序的类型

3.1 关键路线的确定

设重复性项目包含m个工序和n个单元，在约束关系和工序工期已知情况下，关键路线可按如下步骤确定：

步骤0 按优先关系(时间约束和距离约束)顺序排列全部工序；

步骤1 若工序t(t=1,2,…,m)无紧前工序，则令其在零时刻开始，并确定该工序的开始点为潜在关键点；否则对所有约束工序t的工序ik(i=1,2,…,K)，根据算法1和算法2，分别计算出工序对(ik,t)中工序t的上移量Δtk，然后令Δtk*=max(Δik)，那么由工序对(ik*,t)所确定的切点就为潜在关键点，最后根据Δtk*确定工序t在各单元的开始时间；

步骤2 若所有工序的时间参数均被计算，则进入下一步；否则返回步骤1；

步骤3 找到结束时间最大的工序，将其结束点定义为关键点，然后将该工序上的所有与紧前工序相对应的潜在关键点(简称紧前潜在关键点)归入集合β；若该工序无紧前工序，将其开始点确定为关键点，转至步骤5；

步骤4 若β=φ，进入下一步；否则∀pCP(t←i)∈β，它与约束工序i上对应的潜在关键点pCP(i→t)一同被确认为关键点，并且连接这两个关键点之间的约束被确认为关键约束。将工序i上所有的紧前潜在关键点归入集合β。若工序i无紧前工序，那么确认其开始点为关键点。从集合β中移除pCP(t←i)，然后继续此步骤；

步骤5 工序t中关键点所夹的部分确定为关键工序，连接所有关键工序和关键约束，所得路线就是关键路线。

3.2 关键工序的类型

一个关键工序一般会有两个关键点，分别与紧前和紧后关键工序相连，称为紧前关键点和紧后关键点。比较这两个关键点的实现时间，分为将关键工序分为如下的三类：

(1)正关键工序：紧前关键点早于紧后关键点实现的关键工序，其特点是工序工期的延长将导致总工期的延长。对于线形的正关键工序，其紧前关键点在紧后关键点的左侧，而关键路线上的块形和条形工序均为正关键工序。

(2)点关键工序：紧前关键点与紧后关键点同时实现的关键工序，其特点是工序工期的延长或缩短不会改变总工期，但是关键点的提前或推迟会相应的缩短或延长总工期。

(3)反关键工序：紧前关键点晚于紧后关键点实现的关键工序。对于线形的反关键工序，其紧前关键点位于紧后关键点的右侧。反关键工序具有一个非常重要的特性，即在一定范围内它的工期与项目总工期呈反方向变化。当后向关键工序工期延长时，项目总工期会因此而缩短。这非常类似于广义优先网络中的逆关键工序[17]。

4 与现有方法的比较

与现有方法相比，本文提出的确定关键路线的方法具有如下优势：

(1)适用性更强。现有方法大多假设各工序在不同单元上的工作效率均相同，然后通过判断工序对的相对位置(收敛或发散)来确定潜在关键点的位置[3][9]。事实上，由于地理、气候和学习效应等因素的影响，各工序在不同单元上的工作效率经常改变，这就很难判断两个工序是收敛还是发散的。约束关系是由项目本身所决定的，本文通过约束线来确定潜在关键点，能适应更多的情况，具有更强的适用性。

(2)确定出的关键点、关键工序和关键路线更为准确。基于工序在各单元效率相同的假设，Harmelink和Rowings[9]断定最小时间间隔与最小距离间隔总是发生在同一位置。其确认关键点的方法是：首先找到最小时间约束点，然后将该点的距离(水平)连线作为关键约束。这种方法存在两处错误：第一，当各单元工作效率不同时，最小时间间隔与最小距离间隔往往并不在同一位置。如图5(a)，工序A和B上的最小时间间隔位于点a，但最小距离间隔却位于点b。第二，可能会导致错误的关键点和错误的关键约束。如图5(b)，(A,B)∈CSS，Harmelink和Rowings[9]的方法将bc确定为关键工序，ca确定为关键约束。实际上ca代表了两工序间的距离约束，ba才真正代表时间约束，因此bc并非关键工序。

另一方面，不同的约束关系会导致不同的潜在关键点以及工序开始时间的产生，本文严格区分工序间的约束关系更能体现工程的内在要求，也更为准确。Kallantzis和Lambropoulos[11]，Lucko[19]假定工序的时间约束均为(SS)∪(FF)，这导致了比实际要求更强的约束，从而得到比实际要求更迟的项目完成时间。

(3)能够识别反关键和点关键工序。Harris[3]发现了反关键工序与总工期反向变动这一奇异现象，但并未进一步深入研究；Kallantzis和Lambropoulos[11]，Harmelink和Rowings[9]等甚至不认为这些工序是关键工序。反关键工序可以通过投入更少的资源使得项目总工期缩短，因此在优化项目工期、资源和费用过程中将起到极其重要的作用。限于篇幅在此不作详细探讨。

图5 关键点及关键路线

5 算例分析

一段公路铺设工程，全长1500米，具体数据如表1所示。表2给出了各工序的开始和结束时间，以及潜在关键点的位置。利用本文提出的方法确定出的关键路线如图6(a)中粗线所示，对应的项目总工期为35天。工序D的开始点被确定为潜在关键点pCP(D←A)，但并未被确定为关键点，因此工序D不是关键工序。工序F上关键点CP(F←E)与CP(F→G)之间的部分是反关键工序，工序H上仅有CP(H←G)构成点关键工序，其它关键工序均是正关键工序。利用反反关键工序的特性，减少工序F上的资源投入后，项目总工期由35天减少到了32.5天，优化后的关键路线及关键点如图6中粗线所示。

图6 关键路线

工序名称工作区间：工作效率约束类型：约束量(天)类型地点A挖掘路堑与清理0～600(米)∶100(米/天)(B，A)∈CFS∶1线形全路段600～1200∶1201200～1500∶80B排水工程2天条形1350米C路基防护6天(A，C)∈CFS∶1块形840～960米D供水设施建设300～600∶60(A，C)∈CFS∶1线形300～600米E路面基层施工0～1200∶120(C，E)∈CFS∶1线形全路段1200～1500∶100(A，E)∈CSS∶5(D，E)∈CFS∶0F路面施工0～900∶150(E，F)∈CFF∶2线形全路段900～1500∶200G人行道铺装施工0～900∶180(F，G)∈CSS∶2线形全路段900～1500∶100(F，G)∈CD∶150米H路缘及收水井施工0～600∶150(G，H)∈CFF∶5线形全路段600～1500∶180

表2 工序开始结束时间及潜在关键点

6 结论

关键路线的确定是工程项目调度的基础。本文提出了在重复性建设项目中确定关键路线的方法。与现有的方法相比，本文提出的方法更加准确，适应性更强，而且更有利于结果的优化。但是，本文仅仅考虑了工序之间存在的最小约束。因此，下阶段将研究在同时存在最小和最大约束条件下，重复性建设项目中关键路线的确定方法。同时，作为本研究的继续，还将深入研究后向关键工序的优化方法及其在资源均衡、最短工期、时间-费用权衡等问题中的具体应用。

[1] 张立辉,乞建勋,佟鹤晶.CPM网络中机动时间的使用效率及应用[J].运筹与管理,2009,18(1):109-114.

[2] Zhang L H, Qi J X. Controlling path and controlling segment analysis in RSM[J]. Journal of Construction Engineering and Management, 2012, 138(11): 1341-1345.

[3] Harris R B, Ioannou P G. Scheduling projects with repeating activities[J]. Journal of Construction Engineering and Management, 1998, 124(4): 269-278.

[4] Kallantzis A, Lambropoulos S. Correspondence of activity relationships and critical path between time-location diagrams and CPM[J]. Operational Research, 2004, 4(3): 277-290.

[5] Kallantzis A, Soldatos J, Lambropoulos S. Linear versus network scheduling: a critical path comparison[J]. Journal of Construction Engineering and Management, 2007, 133(7): 483- 491.

[6] Yamín R A, Harmelink D J. Comparison of linear scheduling model(LSM)and critical path method(CPM)[J]. Journal of Construction Engineering and Management, 2001, 127(5): 374-381.

[7] Arditi D, Tokdemir O B, Suh K. Effect of learning on line-of-balance scheduling[J]. International Journal of Project Management, 2001, 19(5): 265-277.

[8] O’Brien, J J. VPM scheduling for high-rise buildings[J]. Journal of the Construction Division, ASCE, 1975, 101(4): 895-905.

[9] Harmelink D J, Rowings J E. Linear scheduling model: development of controlling activity path[J]. Journal of Construction Engineering and Management, 1998, 124(4): 263-268.

[10] 钱昆润,葛筠圃.建筑施工组织与计划[M].南京：东南大学出版社,1989.

[11] 蒋根谋,熊燕.线性计划方法及其应用研究[J].华东交通大学学报,2008,25(5):8-11.

[12] Kallantzis A, Lambropoulos S. Critical path determination by incorporating minimum and maximum time and distance constrains into linear scheduling[J]. Engineering Construction and Architectural Management, 2004, 11(3): 211-222.

[13] Ammar M A, Elbeltagi E. Algorithm for determining controlling path considering resource continuity[J]. Journal of Computing in Civil Engineering, 2001, 15(4): 292-298.

[14] Harmelink D J. Linear scheduling model: float characteristics[J]. Journal of Construction Engineering and Management, 2001, 127(4): 255-260.

[15] Lucko G, Pena Orozco A A. Float types in linear schedule analysis with singularity functions[J]. Journal of Construction Engineering and Management, 2009, 135(5): 368-377.

[16] Mattila K G, Abraham D M. Resource leveling of linear schedules using integer linear programming[J]. Journal of Construction Engineering and Management, 1990, 124(3): 232-244.

[17] Elmaghraby S E, Kamburowski J. The analysis of activity network under generalized precedence relations[J]. Management Science, 1992, 38(9): 1245-1263.

Critical Path Identification in Repetitive Project Scheduling

ZHANG Li-hui, ZOU-xin, QI Jian-xun, MENG Xian-wei

(NorthChinaElectricPowerUniversity,Beijing102206,China)

This paper proposes a new method to determine the critical path in repetitive construction project. Firstly, a method is presented to identify the potential critical points by constrained line with various constraints(time and distance constraints)in between activities. Then, the method for identifying the critical path and critical activities is proposed. In order to model large-scale projects, this paper further develops a numerical algorithm. Three types of critical activities are defined and analyzed. Compared with the existed methods, the proposed method is more convenient, correct, and better for optimization in project scheduling.Key words:project management; critical path; constraints; potential critical point; repetitive construction project

2012- 07-26

国家自然科学基金(71271081);中央高校基本科研业务费专项基金(13ZD08)

张立辉(1974-)，男，湖南宁乡人，博士生导师，教授，研究方向：项目调度与优化。

TB115

A

1007-3221(2015)01- 0142- 07