秦旋, 朱倩影, 韩家玄

(华侨大学 土木工程学院, 福建 厦门 361021)

传统建筑业在施工过程中会产生大量建筑垃圾、噪音和扬尘等污染物,这与我国低碳环保的发展理念相悖,亟待向绿色建筑方向转变[1].在此背景下,装配式建筑得到大力推广和发展.目前,预制构件的生产、运输与装配3个阶段的管理在很大程度上仍依赖于过往经验,缺乏联动机制[2],存在调度不合理、运作效率低、成本居高不下等问题[3].因此,从预制构件生产-运输-装配一体化建造出发,优化预制构件全阶段调度,对推动我国装配式建筑发展具有重要意义.

我国装配式建筑起步较晚,只有少数学者将预制构件生产、运输与装配3个阶段作为一个整体过程进行全阶段优化研究.Anvari等[4]首次将预制构件全阶段的优化问题作为扩展型柔性作业车间调度(REFJSS)问题,并采用多目标遗传算法解决REFJSS问题,从而最小化最大完工时间和项目总成本,以及最大化安全性.Khalili等[5]在整个建设周期范围内解决预制构件的调度问题,将预制构件的生产、运输与装配3个阶段作为一个完整过程,建立预制构件模块单元调度模型,并采用混合整数线性规划(MILP)求解该模型.

目前,对于预制构件调度优化问题,大部分学者根据流水车间调度理论进行建模[6-8],并采用启发式算法求解该模型.基于此,本文研究预制构件生产-运输-装配一体化的建造调度优化.

1 全阶段调度优化模型

1.1 预制构件全阶段工作流程

装配式建筑预制构件的生产阶段与运输阶段都属于预制构件的供应链范畴,将生产与运输阶段合并成一个扩展的生产过程.预制构件生产-运输-装配9 道工序流程,如图1所示.

图1 预制构件生产-运输-装配9 道工序流程

1.2 混合流水车间调度问题

混合流水车间调度问题(HFSP)在流水车间调度问题(FSP)的基础上进行扩展[9],FSP工件的每道工序仅对应着一台固定的加工机器,而HFSP工件的所有或部分工序对应着多台并行机器[10].由于HFSP工件某道工序对应的若干台并行机器的属性是完全相同的,因此,每个并行机器加工该道工序所耗费的时间也是一样的.

HFSP需要满足以下4个假设条件:

1) 所有工件的各道工序都可以在对应的任意一台并行机器上加工;

2) 同一加工阶段对应的所有并行机器都是相同的;

3) 某一时刻,一道工序只能在一台并行机器上加工且不能中断;

4) 某一时刻,一台并行机器只能加工一道工序.

混合流水车间调度问题的加工流程,如图2所示.图2中:εk表示第k个工序所对应的并行机器的数量.E={ε1,ε2,…,εk}表示混合流水车间调度问题中各工序上并行机器的数量组合.显然,当εk=1时,HFSP即转化为FSP.与 FSP类似,HFSP的优化目标通常为最小化最大完工时间.

图2 混合流水车间调度问题的加工流程

1.3 预制构件全阶段调度优化模型

Chan等[11]认为预制构件的生产阶段调度问题本质上是属于FSP.将预制构件的生产-运输-装配全阶段等效成一个扩展型的生产阶段,因此,预制构件的全阶段调度问题也可以等效成HFSP.

1.3.1 基本模型 1) 参数设置.预制构件全阶段调度的9道工序对应HFSP工件的工序(Nk,k=1,2,…,9);预制构件全阶段调度的单个或单批预制构件对应HFSP工件,把单个或单批预制构件称为一个作业(Ji,i=1,2,…,n);与HFSP类似,预制构件全阶段调度的每道工序也对应多台并行机器(机械设备与人工资源的组合),设jk,m为工序Nk的各并行机器的编号,k=1,2,…,9;tP,Ji,Nk为作业Ji在工序Nk上的加工处理时间;tP,Ji,Nk,jk为作业Ji在工序Nk上的第jk,m个机器上的加工处理时间,对于∀jk,m,tjk,m≡tP,Ji,Nk,jk,m;tC,Ji,Nk为作业Ji在工序Nk上的完工时间;tC,max为所有作业中的最大完工时间.

2) 基本约束条件.引入0-1决策变量XJi,Nk,jk,m,有

(1)

由于一台并行机器在某一时刻只能加工一道工序,因此有

(2)

同样地,一道工序某一时刻只能在一台并行机器上加工,因此有

(3)

各个加工阶段的机器按照相同的加工顺序加工所有FSP工件,而HFSP工件每道工序都存在若干并行机器,各道工序上不同工件的加工顺序是不相同的,因此,不考虑各个作业之间的顺序约束,仅考虑同一作业内工序之间的顺序约束,即某工序开始时间不得早于其前面工序的结束时间,有

tC,Ji,Nk≥tC,Ji,Nk-1+tP,Ji,Nk.

(4)

在工序N9(安装工序)上,不同的作业满足一定的安装顺序,某一作业的安装开始时间不得早于其前面作业的安装结束时间,由此可得到工序N9上作业执行顺序的约束条件为

tC,Ji,N9≥tC,Ji-1,Nk+tP,Ji-1,Nk.

(5)

最后,由于各个工序阶段对应的并行机器数量并不是充足的(通常会远低于作业的数量),因此,假设第k个工序Nk对应的并行机器的数量上限.特别地,在工序N4(养护工序)上,通常所有作业是可以并行加工的,因此,需考虑养护工序阶段具有足够多的机器.

3) 目标函数.设函数f1(E)表示作业的最优调度排序方案对应的最短完工时间,即

f1(E)=min(max(tC,Ji,N9)).

(6)

设函数f2(E)表示在给定某一种并行机器数量组合E时,全部并行机器所产生的总成本为

f2(E)=UET

.

(7)

式(7)中:U=(μ1,μ2,…,μ9)T.

特别地,工序N4的机器几乎不产生成本,因此,令μ4=0,函数f2(E)可进一步表示为

(8)

全阶段调度模型的最终目标是实现双目标优化,即求解出一种机器数量组合E和一种调度排序方案使得函数f1(E)和函数f2(E)同时达到最小化.双目标优化问题取值为min(f1(x),f2(x)),x∈Ω,x表示问题的可行解,Ω表示可行解的集合.

1.3.2 双目标优化与熵权法 由于函数f1(x)和函数f2(x)分别表示时间和成本,量纲不统一,需要将两个函数的值进行统一量纲处理.采用min-max线性归一化方法将两个函数的原始值映射到[0,1]区间内,由于函数f1(x)和函数f2(x)均为成本型函数(函数值越小双目标优化问题越优),相应的归一化函数为

(9)

式(9)中:归一化后的函数F1(x)和F2(x)相当于函数f1(x)和函数f2(x)的评价指标,函数F1(x)和函数F2(x)值越大,双目标优化问题越优.

优化模型采用线性加权和法将双目标优化问题转化成单目标优化问题.转化后的单目标优化问题的数学表达式为

maxF(x)=w1F1(x)+w2F2(x),x∈Ω.

(10)

式(10)中:归一化后的函数F(x)为所有可行解的评价函数(最终的目的是找到函数F(x)最大的解);w1和w2分别为函数F1(x)和函数F2(x)对应的权重,也分别为函数f1(x)和函数f2(x)的权重,w1,w2>0,w1+w2=1,且权重通过熵权法确定[11-12].

2 改进的双种群遗传算法

遗传算法是一种典型的元启发式算法,通过优胜劣汰的方式选择优化问题的最优解或近似最优解[12-13],是一种高效、并行、随机的全局搜索寻优方法.在求解较为复杂的组合优化问题时,相对一些常规的优化算法,遗传算法能够快速获得较好的优化结果[14-15].

FSP作为典型的非确定性多项式(NP-hard)问题,应用遗传算法求解具有非常好的效果[16-18].预制构件全阶段调度模型是基于HFSP进行建模的,因此,遗传算法也适用于最优调度排序方案的求解.为了提升求解的准确性与效率,对遗传算法做一些改进.改进的遗传算法流程图,如图3 所示.图3中:n为迭代次数.

图3 改进的遗传算法流程图

由图3可知:在改进的遗传算法流程的循环体中,交叉操作放在适应度计算步骤之前,也就是每代种群在计算适应度之前都要经历一次交叉操作,而这个交叉操作会产生一个和原种群同样规模的新种群(或称子代种群);新种群与旧种群合并,形成一个双种群,对双种群的全部个体适应度进行计算、选择和变异等;双种群的进化方式能显著提高遗传算法的搜索效率(这是改进后的遗传算法的最大特点),除了设置双种群,也改进了算法的编码方式和交叉方式.

3 仿真案例分析

3.1 案例背景

将某装配式建筑的某两个标准层(2F,3F)涉及的预制构件类型和尺寸划分成 12 个作业,为了贴合实际工程情况,各个作业在安装阶段都要满足一定的安装顺序(如 2F 构件要先于 3F 构件安装).所有构件的养护都采用蒸汽养护方式,并且假设养护窑的数量足够多,能够满足当前所有构件同时进行养护.构件运输采用相同的专业车辆,每辆车一次只能运送一个作业的构件,构件采用塔吊结合安装班组(假设安装班组只有一个)进行安装.作业的其他各道工序有若干个相同且独立的机器设备或人工班组,或二者的组合.各作业在 9 道工序上的预计加工处理时间,如表1所示.

表1 各作业在 9 道工序上的预计加工处理时间

规定工序N9的并行机器的数量上限为1,工序N7(运输工序)的并行机器数量上限为6,工序N4并行机器数量为L(L是一个足够大的数,且恒有L>12),其他工序的并行机器数量上限为3,则并行机器的数量上限组合E=[3,3,3,L,3,3,6,3,1].假设N1至N9各道工序上每台机器的成本已知,令U=[5.0,7.0,10.0,0,5.0,6.0,0.5,5.0,15.0]为各道工序上总机器成本组合,其中,成本为无量纲.

3.2 全阶段调度优化问题的求解

3.2.1 最优调度排序方案的求解 采用 MATLAB软件进行编程,采用改进的双种群遗传算法求解仿真案例的最优作业调度排序方案.除了已知的加工时间矩阵和机器数量组合E之外,其他参数的设置如下:最大迭代次数为100;种群规模为80;变异概率为0.95;情况1～情况3的并行机器数量组合分别为E1=[1,1,1,L,1,1,1,1,1],E2=[2,2,2,L,2,2,2,2,1],E3=[3,3,3,L,3,3,6,3,1].令L=50,得到各代最优个体适应度曲线和最优作业调度排序方案甘特图,分别如图4,5所示.图4,5中:tC,min为适应度(最短完工时间).

(a) 情景1 (b) 情景2 (c) 情景3

由图4可知:情景1在第1次迭代时就已经得到最小适应度(81.2 h),此后的迭代都收敛于相应的最优值;情景2在第20次迭代时得到最小适应度(55.4 h),此后的循环迭代中每代种群中的最优值都为该值;情景3在第3次迭代时就收敛到了最小适应度(53.8 h),此后的迭代最优值都为该值.

由图5可知:情景1的各道工序(除工序N4外)的并行机器数量都设为1,在这种特殊的机器数量组合下,各作业的调度顺序呈现很强的规律性,同时,这种情况下最优完工时间在所有不同组合情况中是最长的,该调度方案也可作为其他情况的对照方案;相比于情景1,情景2的并行机器数量扩大了一倍,相应的最短完工时间也大大缩短了25.8 h,且最优调度方案是不固定的,可存在多个最优解,没有明显的规律性,在工序N9上的作业加工顺序都严格满足相应约束条件;相比于情景2,情景3的并行机器的数量虽然增加了不少,但最短完工时间缩短了1.4 h,这说明当并行机器的数量足够多时,继续增加并行机器带来的时间收益会越来越小;在规定的机器数量上限以内,存在一个或多个机器数量组合的临界点,同时,也存在某种机器数量组合能使最短完工时间和总机器成本都最小化.

(a) 情景1 (b) 情景2 (c) 情景3

3.2.2 双目标优化问题的求解 双目标优化问题的目的是寻找一种或多种并行机器的数量组合,最大化获取“时间+成本”的综合收益,即最小化最短完工时间和总机器成本.首先,需要确定并行机器数量组合的种类数量,为了精简求解范围,假设工序N7,N8,N9的并行机器数量是固定的,分别为6,3,1,令工序N4的并行机器数量L=50.因此,并行机器数量组合的种类与剩下5道工序的机器数量取值有关,并且该5道工序的机器数量上限皆为3,则并行机器数量组合共有 35=243 种(按 1 至 243 的顺序对并行机器的所有数量组合进行编号).

根据已知的总机器成本组合U=[5.0,7.0,10.0,0,5.0,6.0,0.5,5.0,15.0]及并行机器数量组合E=[a,b,c,50,d,e,6,3,1](a,b,c,d,e=1,2,3),采用MATLAB软件进行编程,求解每种机器数量组合下的函数f1(x)和函数f2(x),最终得到243对值.最短完工时间函数和总机器成本函数的散点图,如图6所示.

图6 最短完工时间函数和总机器成本函数的散点图

由图6可知:离散点在纵轴上分层明显,表明在某一固定总成本下,不同的机器数量组合带来的时间收益可能会大相径庭;几乎每一个函数f1(x)的值都对应着许多个函数f2(x)的值,并且函数f2(x)的值跨度较大,这表明在时间目标固定时,可以通过改变并行机器数量组合降低成本;越靠近左下角的离散点越优.

利用min-max公式,对所求的243对值进行归一化处理,得到相应的评价因子指标函数F(x)值(F1(x)值,F2(x)值).根据F(x)值,利用熵权法,采用MATLAB软件进行编程,求解得到的F1(x)指标权重为w1=0.832,F2(x)指标权重为w2=0.168,指标权重w1,w2也是双目标优化中目标函数f1(x)和f2(x)的权重.

最短完工时间函数,总机器成本函数与评价因子指标函数三维散点图,如图7所示.由图7可知:越靠近左上角的离散点越优.根据权重值w1,w2及函数F1(x),F2(x)值,利用线性加权和公式F(x)=w1F1(x)+w2F2(x),最终可以求得评价因子指标函数F(x)值.

图7 最短完工时间函数和总机器成本函数与评价因子指标函数三维散点图

243种机器数量组合与相应评价因子指标函数二维散点图,如图8所示.由图8可知:越靠上的点(函数F(x)值越大),其对应的并行机器数量组合越优.

图8 243种机器数量组合与相应评价因子指标函数二维散点图

评价因子指标函数对应的主要指标值,如表2所示.由表2可知:并行机器数量组合E=[2,3,2,50,1,1,6,3,1]的评价因子指标函数F(x)的值最大,也是双目标优化问题的最优解,函数f1(x)的值为

表2 评价因子指标函数对应的主要指标值

54,函数f2(x)值为95.

最优机器数量组合下的最优调度方案甘特图,如图9所示.

图9 最优机器数量组合下的最优调度方案甘特图

4 结论

根据装配式建筑的整个建造过程,分析研究预制构件在生产、运输与装配阶段的具体工作流程,对各个阶段的工作流程进行简化,将预制构件全阶段的工作流程简化为9道工序.将预制构件调度优化作为一个扩展型的生产车间调度优化问题.在HFSP理论的基础上,对预制构件全阶段调度问题进行建模,对完工时间和并行机器的总机器成本进行优化.采用改进的遗传算法对模型求解,改进后的遗传算法更符合模型要求,并提高了搜索最优解的效率.

对预制构件生产-运输-装配全阶段调度进行优化,打破以往研究中只考虑某一个阶段的局限性,促进装配式建筑更加经济化、合理化、科学化.但也存在一些不足,如模型的约束多是基于多种理想化的假设,没有充分考虑实际工程情况,以及在模型多目标优化时没有优化其他成本.