基于遗传算法的装配式建筑项目资源均衡

张梦婷，于 淼，孔凡文

(沈阳建筑大学 管理学院，辽宁 沈阳 110168)

装配式建筑构件标准化生产模式，为施工节省了时间，现场装配技术降低了粉尘、噪音等对环境的污染，具有节能环保、劳动力利用率高的优点。但就目前来看，装配式建筑在我国发展缓慢，主要原因是装配式建筑在成本方面与传统现浇相比并无明显优势，且装配式建筑项目存在生产、运输、装配三个作业空间，多空间作业的特点使装配式建筑项目在施工各环节配合上出现问题。多空间施工时相互制约、资源调度性质各不相同的矛盾造成装配式建筑项目普遍出现收益低、工期延误、预算超支的现象[1]。将资源合理分配使用，提高资源使用效率，可加快装配式建筑的推广。因此，本文研究装配式建筑项目的资源调度问题具有重要的现实意义。

资源调度问题是工程项目管理中的一个重要内容。关于资源调度的研究可以分为两类：一类是资源配置，即在资源供给量限制的条件下，通过合理安排各工序开始时间，使工程项目施工时间最短；另一类是资源均衡，即在项目工期已知且不影响相关施工工艺的前提下，通过调整确定各工序的最佳开始时间来均衡资源用量[2]。本文针对资源调度的第二类情形，对装配式项目调度的资源均衡问题进行深入研究。当前，建设工程项目的资源均衡问题研究主要从项目具体特点出发，进行有效的目标模型构建，然而针对装配式建设项目特点的资源调度研究仍较少。Damci等[3]选用钢结构工业建筑项目实例，构建9种不同资源优化函数，分析在不同目标的情况下资源均衡效果的好坏。对于资源均衡问题的优化目标函数来说，还可以将成本、质量或多目标组合作为优化对象。资源成本在项目的总成本中占有很大比重，最小化资源使用成本是项目调度的重要目标之一[4～6]。工程建设质量安全越来越受到重视[7]，质量目标也逐渐被作为一种目标函数被研究。Icmeli-Tukel等[8,9]将最小化预计的返工时间和增加成本用来评价项目质量好坏。由于项目复杂性的特点，将多个目标组合作为优化对象也成为研究的重点。

此外，有效的求解方法一直是资源均衡问题的研究热点。对于求解算法，资源均衡问题可分为三大类：精确算法、启发式算法和智能优化算法。精确算法一般适用于项目简单、工作任务少的问题，常用的方法包括整数规划、动态规划、分支定界等[10]；启发式算法在项目资源均衡过程中通常是建立一个初始进度计划，按照某种优先规则[11～13](如最大自由时差、资源使用量、工序执行紧迫性)，依次调整工序开始时间，使调整后得到的结果有所改进；多数情况下，采用启发式算法求得的解质量都不太令人满意，因此智能优化算法成为目前资源均衡问题研究的主要算法，这种方法能在预计时间内求得大规模问题比较满意的解甚至是最优解[14]。常用的智能优化算法包括遗传算法、模拟退火、粒子群算法、神经网络、蚁群算法等[15～20]。综上，本文以装配式建筑项目作为研究背景，从研究问题的目标函数与求解方法角度介绍施工项目资源均衡；结合装配式建筑项目的实际特点，建立最小化资源方差的资源均衡问题优化模型；在此基础上提出求解该模型的遗传算法，用以有效求解装配式建筑项目的资源均衡问题。

1 问题描述与模型构建

1.1 问题描述

装配式建筑项目资源均衡问题中，资源主要可以分为可更新资源和不可更新资源。可更新资源是指总量虽然有限，但当某项工作完成需要进行下一项工作时，资源可变更为初始的总量，例如设备、人工资源等；对于不可更新资源，资源量会随着施工的进行而不断减少，如使用的原材料、资金等。本文研究的装配式建筑项目资源均衡问题，仅考虑人工资源，用R(ik,jk)表示，指项目k中工序(i,j)的人工资源用量。同时，提出如下假设：(1)项目之间存在时间约束及项目优先级，需要以装配空间作业工期为主并限制生产与运输空间作业时间，装配空间作业工期即为项目总工期；(2)每个工序作业持续时间不变，工序的紧前、紧后关系确定不变，单个工序作业连续不可中断；(3)每个工序的资源需求量在项目开始施工前确定，执行过程中数量保持不变。

基于以上分析假设，引入资源方差作为评价资源均衡配置的目标。通过在项目首尾添加辅助工序，将三个单独项目转化为一个整体，再使用关键路径法(Critical Path Method，CPM)确定项目的关键路线和关键工序，选出非关键工序，非关键工序的实际开始时间是决策变量，通过改变非关键工序实际开始时间来调整各单位时间内资源使用情况。若目标函数方差值σ2越小，则说明资源使用量分布越平衡，避免资源闲置或超出资源给定量。本文提出的装配式建筑项目资源均衡问题目标函数如式(1)所示。

(1)

1.2 模型构建

为了使装配式建筑项目资源均衡问题求解具有可操作性，需要在生产、运输、装配空间的三个子项目的双代号网络图首尾各添加一个辅助工序，将多个空间作业转化为单一作业空间，从而将装配式建筑工程多项目的资源均衡问题转化为单项目资源均衡优化问题。需要说明的是，添加的辅助工序均在关键路线上，有一定的持续时间，但无资源消耗，起始辅助工序、结束辅助工序各自共用一个节点。

对于装配式建筑工程项目，可以分为生产作业、运输作业和装配作业，因此共有3个项目，A={1,2,3}为项目集；项目的工序集合为B={i1,i2,…,ini}。单个项目开始时间为Si，单个项目工期为Ti，添加在首尾的辅助工序分别为is和ie。则经过组合转化后的整体项目开始时间S、项目总工期T分别为：

S=min{Si},1≤i≤3

(2)

T=max{Si+Ti}-S,1≤i≤3

(3)

为求得既定目标，使资源更加均衡，需要对某些工序的开始时间进行调整。在此之前，需要计算辅助工序的持续时间以保证项目的开始时间和工期在调整过程中不发生改变。项目i的辅助工序is和ie的持续时间dis，die分别为：

dis=Si-S

(4)

die=S+T-(Si+Ti)

(5)

上式辅助工序持续时间的计算，确保了所有辅助工序均为关键工序，在进行均衡操作时关键工序的开始时间不做改动。

1.3 约束条件

自由时差是介于最早开始时间和最晚开始时间之间，它的大小决定该道工序在时间上可以变动的范围：

S(ik,jk)=TL(ik,jk)-TE(ik,jk)，i=1,2,…,n,j=1,2,…,n

(6)

TE(ik,jk)≤TS(ik,jk)≤TE(ik,jk)+S(ik,jk)

(7)

式中：S(ik,jk)为项目k中的工序(i,j)的自由时差；TE(ik,jk)为项目k中的工序(i,j)的最早开始时间；TL(ik,jk)为项目k中的工序(i,j)的最晚开始时间；TS(ik,jk)为项目k中的工序(i,j)的实际开工时间。

在网络计划图中，若某项工序存在紧前工作(可能一个或多个)，那么该工序的开始时间为所有紧前工作完毕，产生的约束如式(8)所示。

max{TS(vk,ik)+T(vk,ik)}≤TS(ik,jk)≤

TL(ik,jk)

(8)

式中：(vk,ik)为项目k中的工序(i,j)的紧前工序集合；T(vk,ik)为项目k中的工序(v,i)的工期。

(9)

T=max{TK}

(10)

(11)

式中：TK为项目K在实施阶段的总工期；T为整个项目的工期；R(t)为在第t天所有子项目的资源消耗之和；Rt(ik,jk)为t时刻项目K的工序(i,j)的资源消耗。。

另外，对于工序(i,j)的工作时间t需要介于实际开工时间和实际完工时间之间，如果满足这个约束，资源消耗可以表示为R(ik,jk)，否则，资源消耗为0，即

(12)

式中：R(ik,jk)表示项目K中工序(i,j)的单位时间内所消耗资源；Tf(ik,jk)表示项目K中工序(i,j)的实际完工时间。

2 资源均衡模型求解设计

资源均衡问题已被证明为NP-hard问题[14]。对于这类NP-hard问题，遗传算法作为一种高效的智能优化算法，通过选择、交叉、变异等操作来解决这类优化问题。遗传算法对求解问题的约束空间没有限制，运行时能在较短时间内求得满意解，并且一定程度上扩大了求解NP-hard问题的规模。鉴于遗传算法在求解资源均衡问题上快速高效的优势，本文采用遗传算法来解决问题，通过对装配式建筑实际作业特点的分析，设计适合此类项目资源均衡的算法。遗传算法具体流程如图1所示。

图1 遗传算法流程

2.1 编码方案

由于装配式建筑项目工序较多，双代号网络图中关键路线的关键工序自由时差和总时差均为0，即关键工序开始时间和结束时间不作改动，仅本文选取非关键工序的实际开工时间TS(ik,jk)作为变量，进行实数编码。假设非关键工序有λ个，那么编码串的长度就为λ。仅对非关键工序的实际开始时间编码，保证关键线路上的工序不受影响，可以减少决策变量，缩短资源均衡问题的寻优时间。

2.2 初始化种群

生成初始种群。非关键工序的实际开始时表示为：TE(ik,jk)≤TS(ik,jk)≤TL(ik,jk)，即位于最早开始时间与最晚开始时间这一范围内随机产生。

2.3 适应度函数

计算适应度值。装配式建筑项目资源均衡的目标是为了使资源消耗方差最小，因此，针对这一优化目标，将优化目标函数的倒数设计为适应度函数，表示为：

(13)

式中：F为个体适应度值，表示个体对应的资源消耗方差越小，个体的适应度值越高，则个体越好，实际意义为施工进度计划安排越合理，资源配置越均衡。

2.4 选择

选择操作是在一定概率下，从当前种群中选出优秀的个体，重新构建一个新的群体，然后再繁衍到下一代个体。选中某一优秀个体的比率与适应度值的大小紧密相关，个体适应度数值越大，被选中的概率就越大；反之则越小。以式(13)计算出来的适应度值为基础，利用轮盘赌从群体中选择个体。在一个群体中选择每个个体的概率pi与适应值成正比。

(14)

式中：Fi为个体i的适应度值；种群个体数量为N。

2.5 交叉

在交叉操作中，从种群中随机选择两条染色体进行交配和重组，父链的优良基因被保留下来并传给子链，形成新的优良染色体。本文染色体为实数编码，交叉操作采用实单点交叉的方法，第k个染色体ak和第l个染色体al在j位的交叉操作方法为：

(15)

式中：b为[0,1]区间的随机数。

2.6 变异

(16)

式中：基因aij的上界是amax；基因aij的下界是amin；f(g)=r1(1-g/Gmax)2，其中，r1作为一个随机数，g是当前迭代数，Gmax是进化的最大次数；r是区间[0,1]上的随机数。

3 实例分析

某住宅小区采用装配建造方式进行施工，本文选取标准层施工过程作为研究对象，研究生产调度过程中的人工资源[1]。装配式建筑项目共有现场装配、构件生产、物流运输三个施工空间，分别为子项目1，2，3。其中现场装配空间作业包括构件吊装、节点浇筑等15道工序；对于构件生产空间，该标准层施工涉及预制外墙、预制内墙、叠合板、楼梯阳台等预制构件的生产，共计12道工序；预制构件的运输计划根据现场装配施工进度计划安排，构件运输主要涉及4项工作，即构件装车、构件运输、构件卸车和返程。

图2～4为子项目1，2，3的双代号网络图，各工序名称、人工资源消耗、工序工期见表1。本项目共有35个工序，通过添加辅助工序后多项目转化为单项目，根据图2～4及表1中所给出的工序工期、人工资源消耗数据，采用CPM法确定关键路线和关键工序，计算各工序的最早开始时间、最晚开始时间以及自由时差，并找出非关键工序。本案例共有12道工序为非关键工序，分别为：B1，C1，D1，E1，E2，F2，G2，H2，I2，J2，K2，L2，并在表1中用*标注。本案例装配式建筑项目的总工期为29 d。

图2 子项目1

表1 项目参数

图3 子项目2

图4 子项目3

结合上述目标函数、约束条件及项目参数信息，得到该项目具体数学模型：

(17)

(18)

式(17)为目标函数，求方差值最小；式(18)为各非关键工序实际开工时间的约束条件，介于各非关键工序最早开始时间与最晚开始时间之间。为使下一步计算更加方便，转化式(18)的染色体结构，将决策变量非关键工序实际开工时间的约束条件转变为：

(19)

适应度函数为：

(20)

式中：xi(i=1,2,…,12)为整数，xi≥0；fit为个体适应度值。

优化开始前，首先需要对遗传算法参数进行设置：种群规模为100，进化代数为50，交叉概率为0.9，变异概率为0.01。运用MATLAB 2016a对遗传算法编程，通过多次迭代，得到非关键工序的最佳开始时间TS(B1)=0；TS(C1)=4；TS(D1)=7；TS(E1)=9；TS(E2)=0；TS(F2)=14；TS(G2)=19；TS(H2)=0；TS(I2)=11；TS(J2)=17；TS(K2)=6；TS(L2)=16。表2为资源均衡结果比较表，图5，6为资源分布图。

表2 资源均衡结果比较

图5 初始化资源分布

图6 遗传算法资源分布

图5，6可以看出，资源峰值由初始情况下每工作日需要26单位降至22单位，日资源使用量更多集中在人工资源的平均使用量；从表2可以看出，遗传算法优化后的方差σ2值由20.41降为6.21，比初始网络计划下的σ2值降低了大约70%，表明资源分布更均衡，也说明该方法可以有效解决实际装配式建筑工程应用问题。

遗传算法进化过程如图7所示。从图7的收敛过程可以看出，优化后的适应度得到明显改进，大约30代以后已经保持收敛达到最优解。

图7 遗传算法进化过程

4 结 语

本文通过对装配式建筑项目资源均衡问题进行研究，使资源分布更加均衡，从而可以有效降低资源消耗占装配式建筑项目成本的比重。具体的，通过添加辅助工作联系多作业空间，建立以资源方差最小为优化目标，符合装配式建筑项目特点的资源均衡模型，选取遗传算法进行算法设计，求得各非关键工序的最佳开工时间。通过实际案例分析证明，建立的求解该问题的资源均衡模型操作简单，对装配式建筑工程具有一定的实践参考价值，丰富了资源调度问题相关理论，拓宽了资源调度的应用范围。未来的研究中，将进一步考虑施工过程的多资源、不确定性等复杂条件下资源调度问题。