, 张建平清华大学 土木工程系, 北京 100084
收稿日期：2019-07-11
基金项目：国家重点研发计划项目（2016YFC0702107）；北京市自然科学基金资助项目（8194067）；中国科协青年人才托举工程项目（QNRC2016001）
作者简介：王珩玮(1990-), 男, 博士研究
通讯作者：林佳瑞, 助理研究员, E-mail:lin611@tsinghua.edu.cn
摘要：多模式资源受限项目调度问题（MRCPSP）是建设项目进度优化问题的重要数学模型。但传统的MRCPSP模型难以同时表征工序时长、成本与资源需求之间的多种关系。为了解决这一问题，该文提出了一种MRCPSP模型，并利用约束规划（CP）对算例进行了求解。该问题模型通过定义生产力函数以及各工序对各类资源总需求的组合表征工序时长、成本以及资源需求之间的关系。经验证，该模型可以模拟施工过程中生产力变化的情况，并允许在优化求解时考虑工艺选择对结果的影响，相比传统的MRCPSP模型，求解结果有更明确的工程含义，具有实际应用价值。
关键词：施工进度优化资源受限项目调度问题(RCPSP)约束规划(CP)数学建模
Resource-constrained project scheduling problem considering productivity and construction methods
WANG Hengwei, LIN Jiarui
, ZHANG JianpingDepartment of Civil Engineering, Tsinghua University, Beijing 100084, China
Abstract: The multimode resource-constrained project scheduling problem (MRCPSP) is an essential mathematical model for construction schedule optimization. However, such models cannot easily simultaneously represent multiple relationships between activity duration, cost, and resource requirements. This paper presents an MRCPSP model that includes multiple relationships that is solved using constraint programming (CP). The model represents the relationships between activity duration, cost, and resource requirements by introducing a productivity function and the total resource requirements for combinations of activities. The model can simulate the construction productivity changes and the influence of construction methods on the results. The results then have a more explicit engineering meaning to improve actual projects than the traditional MRCPSP.
Key words: construction schedule optimizationresource-constrained project scheduling problem (RCPSP)constraint programming (CP)mathematical modeling
建设项目中，为了提升施工效率、减少损耗、增加利润，项目管理人员会对进度计划与资源配置进行优化以保证项目成功进行[1]。资源受限项目调度问题(resource-constrained project scheduling problem, RCPSP)是实现建设项目进度与资源优化的关键数学模型[2]，但RCPSP模型的基本假设中，各工序的时长与资源配置固定，与实际建设项目存在较大差异。因此有研究提出了多模式资源受限项目调度问题(multimode resource-constrained project scheduling problem, MRCPSP)，其中的模式指各工序拥有的不同资源需求、成本与工序时长的组合[3]。但是如工序成本与资源需求的关系、工序时长与劳动力资源需求的关系等实际上并不能很好地在MRCPSP中进行描述。
RCPSP属于多项式复杂程度的非确定性(mon-deterministic polynomial，NP)问题[4]，也是制约这类问题复杂程度的关键原因。约束规划(constraint programming, CP)是建设项目RCPSP或MRCPSP的有效求解方法，且求解速度与准确度不亚于一般启发式算法[5]，因此有研究者在CP的基础上建立新的问题模型并实现求解。Liu等[6]提出了考虑现金流约束并以最大净现金流为目标的MRCPSP，并使用CP完成了求解。Menesi等[5]利用CP实现了考虑总工期与资源均衡的多目标MRCPSP求解。Liu等[7]提出了考虑材料供给约束、成本约束与多种劳动力模式因素的MRCPSP并实现了CP求解。可见，有关研究并未深入分析生产效率、工艺变化及其相互关系对问题求解的影响，而是简单地将其抽象为一系列的组合模式。
针对该问题，本文提出同时考虑生产效率、工艺选择等因素的MRCPSP模型及其基于CP的问题求解方法，并通过算例验证证明所提出模型的可行性与正确性。
1 数学模型定义考虑需利用CP求解，因此在定义MRCPSP模型时需要明确变量、表达式、约束与目标函数以符合CP的要求[8]。其中，变量指的是在指定有限值域中可任意取值的量。在一个问题中，所有变量的值域组合构成了解空间。表达式可由变量或其他表达式通过运算组合而成。而变量属于一类特殊的表达式。约束指的是对某一表达式的限制，如最大值与最小值约束。而目标函数指的是作为优化目标的表达式。优化目标也包括最小、最大等。
1.1 基本定义与约束基本定义主要明确资源约束项目调度此类问题的基本解空间(变量定义)以及变量之间的基本关系。这类问题中包括2个关键元素：工序与资源。其中工序有3个关键量：开始时间、结束时间和时长。这3个量之间存在一个方程，因此包含2个变量。一般而言，可以将开始时间和时长作为变量，而在CP中，有专门适合于工序时长的变量，即区间变量(interval variable)。1个区间变量的作用与2个数值变量对等，包括起始点、终止点以及长度，可分别代表一个工序i的开始时间Si、结束时间Fi以及时长Di。2个工序之间存在顺序关系，一般包括4种[9]：结束—开始(FS)、结束—结束(FF)、开始—结束(SF)以及开始—开始(SS)，同时设置时间间隔的最大值与最小值，即
| ${\rm{LL}} \le {P_j} - {P_i} \le {\rm{UL}}{\rm{.}}$ |
资源有1个关键量，即各工序对该资源的需求。在RCPSP中，工序对资源的需求在工序进行期间一般不会发生变化，各工序对资源需求的累加所得到的总需求会受到资源供应的限制，这也是这类问题中“资源受限”的由来。根据资源是否可以再生，总需求的计算方式有所不同。对于可再生资源k如劳动力、机械设备等，某一时刻t的总需求Rkt为t之前所有时刻资源需求的最大值，即
| ${R_{kt}} = \max \left( {\sum\limits_{i \in {\rm{D}}{{\rm{A}}_u}} {{\rm{d}}{{\rm{r}}_{ik}}} } \right), \quad u = 0, 1, \cdots , t.$ |
| ${R_{kt}} = \sum\limits_{i \in {\rm{A}}{{\rm{A}}_t}} {{r_{ik}}} .$ |
资源约束可以统一表达为总需求Rkt与总供给Skt之间的关系，即对于任意时刻t，有
| ${R_{kt}} \le {S_{kt}}.$ |
1.2 生产力约束生产力约束主要用于确定drik。在大多数MRCPSP中，drik和rik是伴随Di直接给出的，并且可再生资源给出drik，而不可再生资源给出rik。但实际上，Di与劳动力资源的drik和rik之间的关系可使用函数关系表达。例如安装某一层的给水管道，对安装工的需求为20人天，即rik=20。假设工人的生产力不随同时施工的人数发生变化，则Di与drik的组合可能为(5，4)、(10，2)等。本文提出相对生产力pik的概念，可计算如下：
| ${p_{ik}} = \frac{{{r_{ik}}}}{{{D_i}{\rm{d}}{{\rm{r}}_{ik}}}}.$ |
实际生产力会受多因素影响偏离标准值[10]，甚至可能受drik的影响。当drik过高时，可能受作业空间的影响导致生产力降低，而drik过低时可能由于并行程度差使生产力降低。考虑这些情况，可以采用通用的方式表达drik、Di与rik之间的关系：
| $P\left( {{\rm{d}}{{\rm{r}}_{ik}}, {D_i}, {r_{ik}}} \right) = 0.$ |
1.3 工艺选择约束一个工序可能可以使用多种工艺方法完成。例如一面混凝土墙的模板施工，可以使用木模板也可以使用铝模板，二者由于材料不同，因而材料处理方式也不同。不同的工艺主要在流程与材料方面存在区别。一般而言，可以将一个工序进一步分解为若干子工序以代表工艺步骤的概念[11]。但当各子工序与其他工序无关时，子工序的选择对整个项目的进度并无影响。会对项目进度造成影响的是不同工艺对资源选择的差异。
本文认为一个工序i可以在若干资源组合中选择一种。每个资源组合j中，定义了该工序对其中任意资源k的总需求rikj。通过定义二值变量实现选择：
| $\begin{array}{l}{r_{ik}} = \sum\limits_j {{X_{ij}}} {r_{ikj}}, \\\sum\limits_j {{X_{ij}}} = 1.\end{array}$ |
1.4 目标函数MRCPSP的目标函数包括总工期、总成本、资源均衡指数以及一些其他的指标。本文并没有增加新的目标函数，选取了3个典型的目标函数用于提高算例的真实性：
1) 总工期。总工期TD为最大的Fi，即
| ${\rm{TD}} = \max \left( {{F_i}} \right).$ |
| ${\rm{TC}} = \sum\limits_i {\sum\limits_k {{r_{ik}}} } \cdot {\rm{p}}{{\rm{c}}_k} + {\rm{TD}} \cdot {\rm{dc}}.$ |
3) 资源均衡指数。资源均衡指数RLI一般只针对可再生资源，可计算如下：
| ${\rm{RLI}} = \frac{{\sum\limits_i {\left| {\sum\limits_{i \in {\rm{D}}{{\rm{A}}_t}} {{\rm{d}}{{\rm{r}}_{ik}}} - \frac{{\sum\limits_i {{r_{ik}}} }}{{{\rm{TD}}}}} \right|} }}{{{\rm{TD}}}}.$ |
2 约束规划求解的实现与利用CP求解建设工程RCPSP的大部分研究相同，本文使用IBM ILOG CPLEX Optimization Studio求解新问题模型，基于该应用程序提供的.NET接口开发了求解程序。具体来说，使用ILOG. Concert命名空间中的类定义变量、表达式与目标函数，而使用ILOG. CP命名空间中的类定义约束、变量或表达式之间的运算，最后使用ILOG. CP. CP作为求解器。
基本约束中，工序间顺序关系的定义使用区间变量之间的4类约束：EndAtStart()、EndAtEnd()、StartAtEnd()、StartAtStart()。资源约束主要是对全过程累积表达式(cumulative function expression)Rk的约束，具体分为2种情况：1)对于全过程恒定的约束，采用Le()即“小于等于”或Ge()即“大于等于”约束；2)对于过程中会发生变化的约束，采用AlwaysIn()。
本文提出的生产力约束是通过定义生产力函数实现的。根据具体的情况可以采用2种方式：1) drik是Di和rik的显函数时，可尝试直接用Di和rik通过运算定义drik的表达式；2)生产力函数为隐函数时，可定义drik为变量，并根据生产力函数为drik、Di与rik建立约束。后者增加了解空间，因此若条件允许应尽可能采用前者。
关于工艺选择约束，rikj对于具体算例是常数。首先设置二值变量Xij，利用Xij和rikj建立rik的表达式，同时建立工序i的所有Xij总和为1的约束以保证每个工序仅选择一组资源。
3 算例验证算例验证主要包括3个目标：1)证明方法的可行性；2)证明并明确新MRCPSP模型中生产力函数的作用；3)证明并明确新MRCPSP模型中工艺选择的作用。其中目标1在所有算例的求解过程中实现，目标2和3需要设计针对性的算例(算例2和3)，同时需设计一个能够验证在求解过程中可以同时考虑这些关系的算例(算例4)。
为了明确求解效果，各算例选择有代表性的一系列资源而并非所有资源，并假设这些资源在施工过程中具有恒定的价格。
3.1 算例1：基本算例1) 工序网络。
首先，本文建立了一个示例项目，其工序间顺序关系如图 1所示，形成了包含了10个工序的网络。大多数工序间是基本的FS关系，但工序6、7、8与工序10之间存在3 d的最短间隔，工序6、8和工序7之间存在间隔为0的SS关系，即这3个工序要求同时开始。
 |
| 图 1 基本工序网络图 |
| 图选项 |
该工序网络模拟了某个施工区域装配式建筑中竖向构件的施工过程。主要包括4条路径：a)工序1→9：该区域预制混凝土墙的安装、支撑拆除；b)工序2→4→6→10：该区域现浇钢筋混凝土柱的钢筋绑扎、模板施工、混凝土浇筑与模板拆除；c)工序3→5→7→10：该区域现浇钢筋混凝土墙的模板施工、钢筋绑扎、混凝土浇筑与模板拆除；d)工序3→8→10：该区域现浇混凝土填充墙的模板施工、混凝土浇筑与模板拆除。
2) 资源。
设置了8个关键资源，如表 1所示，包括4个劳动力资源和4个材料资源。其中，木模板(N3)在本示例项目中并不存在周转的情况，因此考虑为不可再生资源。而为了使验证过程更有针对性，在实际施工过程中可能会使用的其他施工资源如在预制混凝土构件施工过程中所需要的支撑、塔吊等资源，本文中并不考虑。
表 1 资源列表
| 资源类型 | 资源编号 | 资源名称 | 资源价格 |
| 可再生 | R1 | 普工 | 180 |
| R2 | 钢筋工 | 200 | |
| R3 | 木模板工 | 220 | |
| R4 | 混凝土工 | 200 | |
| 不可再生 | N1 | 预制混凝土墙 | 600 |
| N2 | 钢筋 | 3 000 | |
| N3 | 木模板 | 5 | |
| N4 | 混凝土 | 300 |
表选项
3) 成本。
各个资源的单价列于表 1以计算直接成本。其中，劳动力资源(R1、R2、R3、R4)单价是每人天的成本；混凝土材料(N1、N4)单价是每m3的成本；钢筋材料(N2)单价是每t的成本；模板材料(N3)单价是每m2平均每次周转的成本。间接成本按每天1 000计。
4) 各工序对资源的总需求。
各工序对这些资源的总需求如表 2所示。对于劳动力资源(R1、R2、R3、R4)，总需求单位为人天；对于混凝土材料(N1、N4)，总需求单位为m3；对于钢筋材料(N2)，总需求单位为t；对于模板材料(N3)，总需求单位为m2。对于混凝土柱浇筑(工序6)以及混凝土墙浇筑(工序7和8)可以选择使用普工或混凝土工。其他工序的资源需求是固定的，不考虑工艺选择。
表 2 基本工序资源需求表
| 工序编号 | 资源组合编号 | 资源编号 | 资源总需求 |
| 1 | 1-1 | R1 N1 | 30 20 |
| 2 | 2-1 | R1 R2 N2 | 10 35 10 |
| 3 | 3-1 | R1 R3 N3 | 15 52 1 200 |
| 4 | 4-1 | R1 R3 N3 | 4 18 350 |
| 5 | 5-1 | R2 N2 | 30 15 |
| 6 | 6-1 | R4 N4 | 8 90 |
| 6-2 | R1 N4 | 15 90 | |
| 7 | 7-1 | R4 N4 | 15 160 |
| 7-2 | R1 N4 | 20 160 | |
| 8 | 8-1 | R4 N4 | 12 120 |
| 8-2 | R1 N4 | 16 120 | |
| 9 | 9-1 | R1 | 8 |
| 10 | 10-1 | R1 | 20 |
表选项
5) 生产力函数。
生产力函数采用标准函数(pik恒等于1，即生产力恒为标准生产力)：
| $P({\rm{d}}{{\rm{r}}_{ik}}, {\rm{ }}{D_i}, {\rm{ }}{r_{ik}}) = {\rm{d}}{{\rm{r}}_{ik}}{D_i} - {r_{ik}}.$ |
采用多目标优化，首要目标为总工期最小，次要目标是总成本最小。此后按照资源价格由大到小将可再生资源的均衡指数添加至优化目标中。
7) 资源约束。
为劳动力资源设置基本约束，如表 3所示。
表 3 资源约束(基本设置)
| 资源编号 | R1 | R2 | R3 | R4 | N1 | N2 | N3 | N4 |
| 约束 | 12 | 5 | 5 | 5 | — | — | — | — |
表选项
求解得总工期最短为25 d，此时的最小总成本为285 690。包括工序时间安排、资源模式选择以及资源全过程消耗的求解结果如图 2所示。其关键路径为工序3→5→7→10，是现浇钢筋混凝土墙的施工过程。考虑SS关系，工序6、8也属于关键工序。
 |
| 图 2 (网络版彩图)算例1求解结果 |
| 图选项 |
3.2 算例2：生产力函数变化分析为了展现生产力函数对求解结果的影响，本算例采用了下列生产力函数：
| $P({\rm{d}}{{\rm{r}}_{ik}}, {D_i}, {r_{ik}}) = {D_i}\sqrt {{\rm{d}}{{\rm{r}}_{ik}}} - {r_{ik}}.$ |
除生产力函数之外，其他所有条件相比算例1均不发生变化。求解得总工期最短54 d、此时的最小总成本为365 650，具体如图 3所示。
 |
| 图 3 (网络版彩图)算例2求解结果 |
| 图选项 |
相比算例1的结果，各工序由于生产力的下降，总工期增加了，并且除了由此带来间接成本增加(增加了29 000)，还因单位时间劳动力资源消耗增加使直接成本也有增加(增加了50 960)。同时，各工序的时长也均增加了，但关键路径并没有改变。非关键路径中，工序1→工序9的时间跨度增加了，工序2→工序4→工序6→工序10的调整空间由4 d增加为5 d，工序6不再为关键工序。而工序8仍属于关键工序，其由于2个SS关系被延后。
3.3 算例3：多工艺选择分析为了体现多工艺选择分析的作用，在基本配置的基础上，本算例增加了铝模板施工所需的2个资源，如表 4所示。其中，铝模板工(R5)每人天的成本为220，与木模板工(R3)相当，但由于铝模板的重复使用次数极高，因此考虑铝模板的单价小于木模板，每m2每次周转的成本为4。与R3相同，R5设置了5人上限。同时，为模板施工的工序3和4增加了铝模板工艺资源组合的选择，如表 5所示。相比木模板，铝模板由于施工效率更高[13]，因此劳动力资源总需求更低。
表 4 铝模板资源
| 资源类型 | 资源编号 | 资源名称 | 资源价格 |
| 可再生 | R5 | 铝模板工 | 250 |
| 不可再生 | N5 | 铝模板 | 4 |
表选项
表 5 铝模板资源组合
| 工序编号 | 资源组合编号 | 资源编号 | 资源总需求 |
| 3 | 3-2 | R1 R5 N5 | 15 40 1 200 |
| 4 | 4-2 | R1 R5 N5 | 4 12 350 |
表选项
相比算例1，最短总工期缩短为22 d，此时的最小总成本为276 640，结果具体如图 4所示。总工期缩短的原因是关键路径中的工序3选择了新增的铝模板工艺。由于对R5的总需求比R3少，因此在资源上限相同的情况下，工序3的时长缩短了3 d。而由于N5的单价也相对更低，因此总成本降低的9 050中，除了间接成本降低的3 000，还有直接成本降低的6 050。
 |
| 图 4 (网络版彩图)算例3求解结果 |
| 图选项 |
3.4 算例4：资源约束变更分析为了体现资源约束下工艺选择以及生产力函数的作用，本算例在算例3的基础上变更了部分资源约束：
1) 铝模板(N5)供应限制为1 500，可以满足工序3，但不能继续满足工序4的需求；
2) 普工(R1)的人数限制由10人增加至20人。混凝土工(R4)的人数限制由5人增加至20人。
求解结果为总工期19 d，此时的最小总成本为274 030，具体如图 5所示。相比算例3，主要有5个工序发生了变化：工序4、6、7、8和10。其中由于N5的限制，工序4由算例3中的铝模板工艺改为了木模板，因此工序时长、工序位置、需要的资源类型、资源总需求量和直接成本均发生了变更。虽然因此使直接成本增加了390，但并未对总工期造成影响。总工期相比算例3缩短3 d主要包括2个原因：1)放宽了R1和R4的限制，通过调整工序6的资源选择，并调整工序6、7和8的劳动力资源的日需求量，这3个工序的时长总计被压缩至1 d；2)放宽了R1的限制，工序10的时长由2 d缩短为1 d。因此总工期共缩短3 d。虽然该结果并未考虑工作面的影响，但表明了投入大量生产力资源有机会同时降低总工期和总成本。
 |
| 图 5 (网络版彩图)算例4求解结果 |
| 图选项 |
3.5 结果分析通过对4类算例的求解与结果对比，本文提出的模型的可行性得到了验证，同时也证明了该模型具有如下特征：
1) 通过定义各工序的时长与劳动力资源需求的关系，可影响求解结果中的工序时长，进而影响直接成本并可能影响工序排布；
2) 可实现对工序工艺的选择，体现为工序对各资源的总需求，从而影响工序时长、工序排布、资源配置，进而影响总工期和直接成本；
3) 在有限的资源条件下，可在生产力函数的基础上，通过综合调整工序时长以及对不同类型劳动力和不同工艺所需材料组合的选择，使资源配置合理并得到总工期和总成本的最优解。
4 结论本文提出的MRCPSP模型比传统的MRCPSP模型增加了生产力函数并明确了对工艺选择的表达方式。经验证，该模型通过引入生产力函数，不仅可以在求解过程中考虑工序时长与劳动力资源需求的协调变化，还可考虑生产力可变的情况以尽可能模拟实际施工过程中的情况。同时，通过为各工序的不同工艺定义对应的资源组合，可在求解过程中考虑各工序的工艺选择对各总体优化目标的影响，具有实际意义。在资源限制变更时，该模型求解后可在综合考虑工序生产力函数和工艺选择的同时对求解结果进行合理调整，在实际工程中具有应用价值。
参考文献
| [1] | GIRAN O, TEMUR R, BEKDA? G. Resource constrained project scheduling by harmony search algorithm[J]. KSCE Journal of Civil Engineering, 2017, 21(2): 479-487. DOI:10.1007/s12205-017-1363-6 |
| [2] | KASRAVI M, MAHMOUDI A, FEYLIZADEH M R. A novel algorithm for solving resource-constrained project scheduling problems:A case study[J]. Journal of Advances in Management Research, 2019, 16(2): 194-215. DOI:10.1108/JAMR-03-2018-0033 |
| [3] | BRUCKER P, DREXL A, M?HRING R, et al. Resource-constrained project scheduling:Notation, classification, models, and methods[J]. European Journal of Operational Research, 1999, 112(1): 3-41. DOI:10.1016/s0377-2217(98)00204-5 |
| [4] | BLAZEWICZ J, LENSTRA J K, KAN A H G R. Scheduling subject to resource constraints:Classification and complexity[J]. Discrete Applied Mathematics, 1983, 5(1): 11-24. DOI:10.1016/0166-218x(83)90012-4 |
| [5] | MENESI W, HEGAZY T. Multimode resource-constrained scheduling and leveling for practical-size projects[J]. Journal of Management in Engineering, 2015, 31(6): 04014092. DOI:10.1061/(ASCE)ME.1943-5479.0000338 |
| [6] | LIU S S, WANG C J. Resource-constrained construction project scheduling model for profit maximization considering cash flow[J]. Automation in Construction, 2008, 17(8): 966-974. DOI:10.1016/j.autcon.2008.04.006 |
| [7] | LIU J, LU M. Constraint programming approach to optimizing project schedules under material logistics and crew availability constraints[J]. Journal of Construction Engineering and Management, 2018, 144(7): 0401804. DOI:10.1061/(ASCE)CO.1943-7862.0001507 |
| [8] | MENESI W, GOLZARPOOR B, HEGAZY T. Fast and near-optimum schedule optimization for large-scale projects[J]. Journal of Construction Engineering and Management, 2013, 139(9): 1117-1124. DOI:10.1061/(ASCE)CO.1943-7862.0000722 |
| [9] | ABUWARDA Z, HEGAZY T. Flexible activity relations to support optimum schedule acceleration[J]. Journal of Construction Engineering and Management, 2016, 142(11): 06016004. DOI:10.1061/(ASCE)CO.1943-7862.0001193 |
| [10] | GOLNARAGHI S, ZANGENEHMADAR Z, MOSELHI O, et al. Application of artificial neural network(s) in predicting formwork labour productivity[J]. Advances in Civil Engineering, 2019, 2019: 5972620. DOI:10.1155/2019/5972620 |
| [11] | GARCíA-NIEVES J D, PONZ-TIENDA J L, SALCEDO-BERNAL A, et al. The multimode resource-constrained project scheduling problem for repetitive activities in construction projects[J]. Computer-aided Civil and Infrastructure Engineering, 2018, 33(8): 655-671. DOI:10.1111/mice.12356 |
| [12] | ABUWARDA Z, HEGAZY T. Work-package planning and schedule optimization for projects with evolving constraints[J]. Journal of Computing in Civil Engineering, 2016, 30(6): 04016022. DOI:10.1061/(ASCE)CP.1943-5487.0000587 |
| [13] | 刘雪红, 程海寅, 陆建飞, 等. 铝合金模板体系施工技术及其效益分析[J]. 施工技术, 2012, 41(23): 79-82, 104. LIU X H, CHENG H Y, LU J F, et al. Construction technology of aluminum alloy formwork system and its benefit analysis[J]. Construction Technology, 2012, 41(23): 79-82, 104. (in Chinese) |
