APP下载

基于改进遗传算法的工程施工进度优化

2019-11-05马国丰张灵祉

土木工程与管理学报 2019年5期
关键词:总成本工期染色体

马国丰, 张灵祉

(同济大学 经济与管理学院, 上海 200092)

当前我国建设产业正处于由迅猛发展转向转型升级的关键时期,对于建造工程的进度、质量和成本都提出了更高的要求。为实现这个目标,采用的技术包括赶工法、替代施工方法、活动搭接法等进度管理方法[1]。而前两种技术为缩短工期会产生更高的加班费率和更多施工工具,基本上均会增加完工成本。活动搭接则是通过两种活动平行施工加速工程项目的实施[2]。然而,在不具备完整的上游活动信息时开展下游活动可能导致返工并增加风险[3],而返工将导致不必要的成本并延长工期。如何在优化搭接技术的过程中,理解和分析活动内部的关系,优化进度管理中的搭接技术,制定同时满足进度和成本管理的搭接策略,对于项目方和企业都至关重要,也值得学者思考和研究。

Krishnan等[4]用上游活动进化率和下游活动敏感度两种属性来描述活动,并开发出活动搭接的详细框架。部分学者进一步进行开发,应用于工程活动搭接的进度-成本均衡问题。搭接程度与返工量直接相关[5],Dehghan[6]指出,返工概率会随着节省时间和搭接程度的增加而增大,并提出一个在考虑资源约束条件下可以得到最大搭接程度的进度-成本均衡模型。吴凌霄等[7]提出进度-成本均衡下的调度优化方法。Grèze等[2]将搭接应用于资源约束下的项目进度计划问题。Berthaut等[8]也找到一种处理资源约束下项目进度计划问题中搭接情境下的时间-成本均衡问题的方法。除此之外,Hazini等[9,10]利用活动搭接和仿真等其他技术求解返工概率,并提出一种启发式方法,可以获取用活动搭接和赶工结合实现进度压缩的最大收益。遗传算法是在优化领域最适用的方法之一,而依赖结构矩阵(Dependency Structure Matrix,DSM)是一种展示活动间依赖关系的有效方法,被用于Hossain等[11,12]的研究中来预测设计活动的变化,避免不必要的返工。将两种方法结合应用于进度管理领域的研究,将为学者们提供新的研究思路。

虽然进度管理和搭接设计的进度-成本均衡方面已有很多研究,但仍存在一定的局限性:(1)已有研究都是根据专家经验将一个固定的搭接率应用于所有搭接的活动,而因活动属性和实施条件的不同,实际每组进行搭接的活动之间的搭接率均有所不同,因此传统设定可能导致不可忽视的偏差;(2)大多数研究人员都基于经验公式来计算搭接时间,而没有相关工具可以设计、计算和评估建筑工程项目中具备精确搭接率的搭接策略。最近,Gwak等[13]提出了一种计算方法,可以确定活动间具体搭接时间、考虑关键活动的动态变化、处理有多个上游活动或下游活动时活动的搭接问题,并提供了计算返工量和返工成本的数学公式。

1 引入搭接矩阵的进度-成本均衡模型

1.1 搭接矩阵

图1描述了活动A到活动F六个活动在三种情况下的简化甘特图和关系矩阵。设计结构矩阵(Design Structure Matrix,DSM)是一种描述工程活动信息流的有效技术[14],本图中,根据DSM提取出搭接策略矩阵(Overlapping Strategy Matrix,OSM)。在DSM中,每个数字“1”代表行中的活动依赖于对应列中的活动。但传统“结束-开始”的进度安排通常远超过合同要求的工期。因此需要对存在依赖关系的活动进行搭接来加快进度。为便于说明,假定所有活动都能得到其上游活动的初步信息。所有可以搭接的成对活动在矩阵中均用阴影表示,不论最终搭接与否。在这种情况下,OSM中将数字“1”变为“0”来表示,表明上游活动的信息可预测,下游活动可以在上游初步信息不完整时开展,最终信息会在完工后再比较。

如图1a所示,有三组活动可以进行搭接,因为其中上游活动信息可预测,下游活动在得到其初步信息后立即开始;其他阴影标注的活动组存在相互依赖关系,但其中上游信息不可预测,因此无法搭接。在这种情况下,总工期被大幅压缩,尽管导致大量返工。图1c中,为避免过多的返工,只有一组活动进行了搭接,但这种情况下,工期超过合同约定期限,随之招致大额的惩罚金。图1b呈现了项目经理最需要的搭接策略,通过最合理的搭接量减少返工,同时使工期控制在合同约定期限内。上述分析清晰地阐述了最优搭接策略对于满足合同工期要求的同时控制成本最低的重要性。因此,有必要通过优化方法计算哪些活动应该被搭接,具体的搭接率又应该是多少,从而取得进度和成本相对的均衡。

图1 三种搭接情况

1.2 优化模型

因为工期和成本都需要尽量减小,搭接的进度-成本均衡问题是一个多目标优化问题。研究人员曾提出可解决这个问题的一些目标函数[4,5]。本文在已有研究的基础上进行了改进,从而制定了一个新的目标函数,如式(1)所示。

(1)

式中:C为项目总成本,包括直接成本、间接成本和超期的惩罚金;CD(i)为不考虑搭接时活动i的直接成本;n为活动个数;Pij为返工概率,指上游活动i的变化造成下游活动j返工的概率;Rij为由于上游活动i的变化引起下游活动j的返工时间;CI(j)为返工引起的下游活动j的日间接成本,包括每日工资和其他费用;m为下游活动个数;T为项目总工期,包括活动持续时间、进度压缩值及返工增加的时间;Tcd为项目的合同约定期限;pc为项目完工时间延迟时的惩罚系数;bc为项目提前完工时的奖励系数;同时满足约束:00。

式(1)说明精确搭接策略下的项目总成本由直接成本、返工成本和延期惩罚(可能有)构成。与其他研究有别,惩罚系数的设定是为了避免工期超过约定期限,排除不合适的解。式(1)中,直接成本CD(i)通常针对具体项目,由专家预估每项活动的直接成本。式(2)基于Gwak等[13]的研究,用于评估下游活动返工概率Pij。

(2)

式中:Oij为两个活动之间的搭接率,代表活动j与活动i平行施工的百分比;进化率AE和敏感度AS的值可以由表1得到,AE取值为S表示活动进化率慢,取值为F表示活动进化率快,AS取值为L表示活动敏感度低,取值为H表示活动敏感度高。由于不确定性随着搭接程度增加而增大,返工概率与搭接率也直接相关。同时,在不同情况下,Pij和Oij的相关关系并不总是相同,因此相应的计算公式也会因进化率和敏感度等属性的变化而有所不同。如果活动进化率很低,在上游活动进行过程中,能产生并传达到下游活动的准确信息会很少,导致高风险和返工概率。如果活动敏感度很低,则外部变化对活动造成的影响小,返工概率也会小。综合考虑到搭接率、进化率和敏感度,下游活动的返工概率可以用式(2)表示。公式由实际项目经验和数据模拟生成。

在表1中,搭接率Oij有上界值OM(最大搭接率),和下界值ON(最小搭接率)。搭接长度Lij可以是介于0与最大搭接长度之间的任意长度。根据搭接机制,返工概率Pij和返工时间Rij均为搭接长度Lij的函数,如式(3)所示。根据Dehghan等[1]提供的信息和项目经验,返工函数用式(4)表示。另外,如式(5)所示,Lij根据搭接率Oij和下游活动持续时间Dj相乘得到。

Rij=f(Lij)

(3)

Rij=0.2Lij

(4)

Lij=OijDj

(5)

对应的返工量由返工概率Pij和返工时间Rij相乘得到。另外,惩罚系数pc应该足够大,足以筛除工期超过合同约定期限的策略。

表1 活动属性相关信息

2 进度搭接策略优化算法设计

本文提出的搭接策略优化算法对染色体的表达方式进行了改进,从而实现策略中搭接率的细化。搭接中的进度-成本均衡问题分为两种,第一种是给定项目合同期限Tcd,寻求成本最小的搭接策略;第二种是项目目标成本固定时寻求工期最短的搭接策略。本文的主要目的是针对第一种问题,在已有搭接方法的基础上,得到改进的优化方法,如图2所示,并可以在做出少许改动后应用于第二种问题。

图2 搭接策略优化算法

2.1 输入数据

在算法开始运行之前,需要输入关键数据,如活动持续时间和依赖关系、最小和最大搭接率、活动进化率和敏感度值、返工时间函数、日间接成本、工期延误惩罚和合同约定工期等变量。种群个体数(NIND)为100,确保种群规模足以忽略随机选择导致的误差。最大迭代次数(MAXGEN)为1000,足以通过多次迭代得到精确的最优解。染色体长度(NVAR)为23,变量的二进制位数(PRECI)为20。另外,代沟(GGAP)设定为0.9,杂交率px和变异率pm分别为0.7,0.01。

2.2 改进遗传算法生成初始种群

这一阶段,算法生成一组随机染色体,每个染色体包含的基因数与项目活动间存在依赖关系的数量相同。在以往的研究中,染色体上每个基因都表示一种搭接关系,均作为一个变量用于计算。但在二进制编码体系中,每个基因只能用“1”或“0”来表示,在这种情况下所得结果只能代表“搭接”或“不搭接”。因此,以往的研究在得到“搭接”或“不搭接”后,直接对可以搭接的活动赋予一个固定的搭接率用于进一步计算。为了使整个计算分析过程更为精确,本研究提出了一种创新的方法来对染色体进行表达。新方法中用数10个二进制数来代替从前的一个基因。在二进制编码体系中,数个二进制数可以表达一个实数,代表本研究用数十个二进制数可以输出每个搭接关系的精确搭接率,用于进一步计算搭接长度等其他变量值。为了便于说明,图3从表1中选取了案例中的9个活动来展示染色体构成。在原始方法中,每个基因表示一组活动的搭接关系,而用本文所提出的方法中,每个搭接关系(即阴影所示方格)都用20个基因来表示,用20个二进制数已经足够得到一个具体的搭接率数值,使算法得以计算每个精确搭接率。

图3 每条随机染色体上的基因表达

在计算搭接率和搭接时间后,可以通过上述函数得出相应的返工量和成本。如前文所述,每一条染色体都代表了一种独特的搭接策略,因此,通过目标函数计算,每一条染色体也就对应着一个独特的总成本C和总工期T。随机生成染色体的操作将在染色体总数达到设定值时停止,最终生成100条染色体。

2.3 生成子种群

算法从初始种群中随机选择两个染色体作为母代,在某个单点基因处交换一端的所有基因,通过突变操作避免优化过程受限于局部最优点[6]。研究人员设定了活动总时间限制来确保搭接策略对应的时间不超过约定工期。

2.4 生成最优解

本文设定终止条件为迭代次数,迭代过程在满足终止条件时会自动停止。

3 算例分析

3.1 案例背景

案例来源于一些已有研究并经过加工后曾应用于Gwak[13]的论文中。表1展示了案例中的18项活动及相关参数。原例中活动数据来源于专家经验。原案例优化前对应横道图如图4所示。本文假设该案例中所有上游活动的信息均可以预测且信息可以从上游活动传达到下游活动。从某种程度上,最大搭接率代表了能得到上游活动信息的最早时间点。例如,当一个活动的最大搭接率为0.65时,意味着早期预测的信息最早能在上游活动已完成35%时传达到该活动。本案例中,日间接成本CI(j)设定为63美元/d,合同要求的工期Tcd为110 d。在优化之前,原不含搭接的正常工期为169 d,其中关键路径为1 → 6 → 10 → 12 → 15 → 17 → 18。相应的项目总成本为143967美元,其中直接成本133320美元,间接成本10647美元(63美元/d169 d)。

图4 案例原计划横道图

3.2 案例结果

项目依赖关系可以用如图5所示的OSM矩阵来直观表示。由于本案例中所有上游活动的信息都可以预测,阴影方格中所有元素均为“0”。

图5 案例OSM矩阵

本项目规定工期为110 d,惩罚系数设定为2。惩罚系数的设定将对染色体进行筛除,以保证完工时间不超过合同规定时间。

图6展示了四种搭接情况下的进度安排。第一种代表没有任何搭接和优化的原始进度计划,总工期为169 d,总成本143967美元。第二种情况下,每个活动都在得到上游活动传达的初始信息后立刻开始,工期大幅压缩到80 d,总成本为165006美元。工期实现了52.7%的显著压缩比例,但是总成本增幅过大,不符合实际项目要求。第三种情况为原使用该案例的研究中的优化结果,得到完工时间为101.9 d,相较于第一种情况减少了39.7%,对应总成本为159,425美元。最后一种情况为本文得到的最优搭接策略,遗传算法优化结果如图7所示。只有能够在返工量最少的条件下可以缩短工期的活动才被搭接,并且给定一个精确的搭接率。通过最优搭接策略得到的总工期和总成本分别为108.4 d和139539美元,与第一种情况相比分别实现了35.9%和3.1%的减少,工期没有超过合同规定期限并且稍微降低了成本。表2展示了该案例的最优搭接策略对应各个活动的具体参数值。

图6 四种搭接方法对比

图7 优化遗传算法收敛图

搭接活动搭接率搭接长度/d返工时间/d返工概率返工成本/美元1-50.2186.541.310.10256.691-60.3007.201.440.46388.775-70.2183.920.780.10153.516-80.50012.002.400.411079.866-90.60015.003.000.451619.862-100.80026.395.280.523800.036-100.80026.405.280.523801.217-110.60012.002.400.581295.938-110.60012.002.400.581295.895-120.2858.551.710.10438.699-120.2868.591.720.10442.3510-120.2868.581.720.10441.243-130.50012.002.400.551079.984-140.75013.502.700.501822.069-140.75013.502.700.501822.2612-150.812.82.560.641843.213-160.2176.521.300.10254.7314-160.2186.551.310.10257.5711-170.70016.803.360.482116.6614-170.70016.803.360.482116.7515-170.70016.803.360.482116.8016-180.2173.900.800.10152.0517-180.2193.940.790.10155.09

本文提出的优化方法的优越性主要表现在两个方面:(1)总工期远比优化前的工期短。尽管时长比第二和第三种方法中要长,但仍满足合同要求,因此该进度可以接受。(2)由于优化后减少了不必要的返工,总成本少于其他三种情况下的成本。证明该优化方法对实际工程项目具有一定的意义。

4 结 语

针对目前在进度管理搭接技术的研究中存在的不足,即搭接率的固定设定和参数计算依赖于专家经验等问题,本文在改进遗传算法内染色体的表达的基础上,提出基于改进遗传算法的最优搭接策略分析方法,并以一个小型工程项目为例进行了实证研究,验证了该方法的有效性和可行性。文中数学公式可以输出最优搭接策略中的搭接率、总工期、总成本等数据。可以用该优化模型优化进度计划中的搭接设置,使搭接活动更精确,保证总工期满足合同要求。也可以比较输入不同的信息、属性、合同要求等条件时,对应总工期和总成本的变化。

但是,目前研究中进化率、敏感度、最大搭接率等活动属性都是根据进度管理人员的经验设定,由于专家文化背景和经历的不同,可能产生一定的误差,有待后续进一步研究。本研究中没有考虑到外部条件变更引起的进度变化,在多学科协作的建设环境下,建议后续研究可以用变更传播预测方法进行变更管理,通过科学建模和分析来消除这种不确定性。

猜你喜欢

总成本工期染色体
2020年中国棉花种植成本调查
工期延误的责任划分及处理方法研究
数据驱动下的库存优化模型研究
多一条X染色体,寿命会更长
为什么男性要有一条X染色体?
线性盈亏平衡分析在TBM隧洞工程中的应用
关于煤化工生产企业成本管控的思考
建筑项目管理过程中的工期控制
能忍的人寿命长
高等植物杂交染色体及其杂交基因表达的性状——三论高等植物染色体杂交