周转空间受限的装配式建筑准时(JIT)调度优化

Optimization of Just-in-Time (JIT) Scheduling for Prefabricated Buildings with Limited Turnover Space

摘要: 基于装配式建筑施工现场的调度特点，集成JIT调度优化，研究周转空间受限下的装配式建筑准时调度问题。综合考虑预制率、周转空间、JIT调度及不确定因素，以时间、费用及鲁棒性综合最优为目标函数，建立了有任务紧前关系的静态约束和常规资源及临时堆场动态约束的多目标调度优化模型，设计了嵌入爬山算法的非支配遗传算法求解。选取合适的测试算例证明了算法的有效性，探讨了预制率和临时堆场大小对于调度结果即工期、成本和鲁棒性的影响。实验结果表明，所设计的算法对解决这类复杂问题合理有效。项目的工期、成本、鲁棒值对预制率并不敏感，但增大临时堆场面积可以有效缩短项目工期，缩短项目工期的效果与临时堆场面积反相关。

Abstract: Based on the scheduling characteristics of assembly construction site, integrated JIT scheduling optimization, we study the just-in-time (JIT) scheduling of prefabricated buildings with limited turnover space. Focused on the prefabrication rate, turnover space, JIT scheduling and uncertain factors, a multi-objective optimization model of time, cost and robustness, with static constraints of the task precedence and fluctuating constraints of the conventional resources and temporary storage yards is proposed. Then a non-dominated genetic algorithm embedded with a hill climbing algorithm is developed. To show the performance of the proposed algorithm and to analyze the influence of the prefabrication rate and the size of the temporary storage yard on the scheduling result, numerical experiments are carried out and associated results are compared. The results show that the proposed algorithm is effective for solving the complex problem. The project duration, cost, and robustness value are not sensitive to the prefabrication rate, but increasing the temporary storage yard area can effectively shorten the project construction period, and the effect of shortening the project construction period is inversely related to the temporary storage yard area.

1. 引言

装配式建筑由于兼具高质量、高效率、低污染、低能耗等显著优点 [1]，已成为我国建筑业改革发展的重要方向。装配式建筑是指用预制构件在施工现场装配而成的建筑 [2]，区别于大量使用模板钢筋等进行湿作业的现浇养护施工 [3]，装配施工为质量和气候提供了受控条件，通过改变工作的流程顺序，项目的进度得到有效压缩，材料浪费得到大大降低 [4]。然而，装配式建筑是由分散的、异地的和动态的多组织团队共同实施的 [5]，其建造分布于构件预制、物流运输、现场装配等多维作业空间，具有异地域、非同步的特点 [6]，由此带来的是额外复杂的工作，如转运、卸载、存储和装配。在存储环节，施工现场需要为预制构件预留现场等待空间，这种临时储存必须非常小心，相应的就需要花费额外的精力和成本 [7]。同时，在装配环节，装配作业和现浇作业交叉难度较大 [8]，为了保证建筑的质量和完整性，需要额外的材料将与之部分和现浇部分结合起来，导致装配式建筑工程普遍出现低收益、超期、超预算的局面 [9]。而JIT调度，作为一种先进的管理模式，通过调度计划的控制及时间的管理，要求“及时生产、及时交付”，成为装配式建筑提高场地周转效率、降低综合成本的必然选择。

目前，国外关于装配式建筑的研究主要围绕在产业前景，开发应用，绩效评估，技术应用环境，设计、生产、运输、装配策略五大方面 [10]。而国内的相关研究主要集中在政府政策、生产工艺等社会技术层面 [11] [12]。而关于装配式建筑施工合理调度的研究并不活跃，现有研究的不足主要集中在以下几大方面：1) 目前有关研究忽略了预制率对项目成本及工期的影响，预制率被定义为描述预制构件占目标建筑混凝土总体积的百分比，被认为是反映建筑预制构件水平的一个有效变量，已有研究表明预制率越高，成本越高，预制的程度直接决定了建筑的成本效益 [13]，但已有的这些研究也仅仅停留在已有项目数据的总结归纳上，并未对其影响关系进行进一步的量化建模。2) 装配式建筑的调度问题本质上是资源受限项目的调度问题，已有的研究仅仅考虑了常规资源的限制，未考虑周转空间受限的情况。文献 [14] 明确指出，装配式建筑相较于传统建筑，成本超预算的主要原因一方面来源于材料本身，另一方面主要来源于现场施工成本的增加，包括机械成本(垂直运输)、安装、连接和现场储存。在中心城市，可供建设的用地面积日益紧张，现场储存空间也愈发日益不足，所以探讨周转空间受限的装配式调度问题是非常有必要的。3) 准时制(JIT)理念在管理预制混凝土构件从预制厂到施工现场以及在施工现场内部的装配方面具有巨大的潜力，这样就可以减轻存储空间的限制和工作现场的交通阻塞问题 [15]。但现有的研究多从生产供应商的角度出发，应用JIT理念解决施工生产的优化调度问题 [16] [17]，未针对施工现场的做相关研究。4) 不确定因素一直是装配式建筑的施工的难点。但多数研究局限在装配式建筑施工过程中不确定因素的量化分析上 [18] [19]，仅有文献 [20] 在经典PERT的基础上，充分考虑了风险偏好、资源紧张度、活动复杂度等内部因素及外部环境的不确定性，为保证装配式建筑在不确定环境下的顺利实施，对缓冲时间窗进行了设置。

基于此，本文基于装配式建筑的特点，综合考虑了预制率、周转空间、JIT调度及不确定因素对装配式建筑的调度优化问题进行了研究，以达到工期、成本、鲁棒性三者综合最优的目的，该问题存在以下难点：1) 预制率将一栋建筑的主体结构工程量分为了现浇部分和装配部分，但是不同的施工任务，预制率有所不同，如何引入预制率量化其对工期、成本的影响成为本文的难点之一。2) 空间资源受限的项目调度问题不仅要满足任务时序要求、常规资源的限制，还要满足空间资源的约束。引入周转空间受限的约束之后，如何合理利用临时堆场的容量成为问题的难点之一。目前关于这类资源调度问题的成果不多，广泛存在于工业领域，例如，文献 [21] 认为空间资源往往是制约大型工程项目调度的关键和瓶颈性资源，指出空间资源有限的项目调度问题是NP难的，并提出启发式算法求解。文献 [22] 确立了空间资源项目调度问题的单目标模型，并采用精确的分支定界法求解最优解。但是，文献 [23] 指出分支定界法运算效率极低，不能用于求解复杂的多任务调度问题，并提出了一种多启发式融合粒子群算法，发现该算法在求解时间和效果上均优于传统的遗传算法。3) 另外，任务对常规资源的占用时间取决于任务的工期，但在JIT理念的背景下，承包商为了保证供应商的准时调度，需要给预制构件留有足够的预留等待时间，此时，预制构件对空间资源即临时堆场的占用时间不再等同于任务的持续时间，如何量化时间窗与临时堆场资源约束的逻辑关系是本文的又一大难点。一些有容量限制的车间调度问题对本文有一定的借鉴意义，例如，文献 [24] 研究了工序之间每个缓冲器容量限制的条件下，生成可行的计划调度方案的算法，提出了缓冲器容量流转方案的递归算法和缓冲器容量限制下的调度问题的极大极小代数法解法。文献 [25] 研究的问题具有生产工序间存在有限容量缓冲库，生产工艺路径柔性选择，生产设备需要转换时间，生产调度多目标等特点，针对这些特点构建了混合整数规划模型。4) 最后，为了减少不确定因素对项目实施过程中的干扰，如何设置缓冲时间，吸收或者减低干扰因素对项目所造成的进度之后，也是本文的难点之一。

为了解决以上问题，本文基于装配式建筑的特点，综合考虑了预制率、周转空间、JIT调度及不确定因素，建立了周转空间受限的装配式建筑准时(JIT)调度优化模型。模型中嵌套的多目标函数协调了时间、费用和抗干扰能力之间的关系，进而有效指导了装配式建筑项目的管理实践。问题的模型详见第2节。在算法方面，为了处理模型的复杂特性，本文设计了嵌入爬山操作的混合遗传算法，详见第3节。第4节为算例验证及结果分析。

2. 问题模型

本文研究周转空间受限的装配式建筑的JIT调度问题，以时间、费用及鲁棒性综合最优为目标，确定装配式建筑施工活动的开始时间，探讨不同预制率、周转空间及JIT理念对目标的影响。为了解决该问题，首先定义问题中的若干概念。

2.1. 问题描述

定义1：任务。任务指在施工活动过程中使用资源的最小实体，具有施工时间这一属性。每项施工活动根据预制预制率分为装配任务和现浇任务。装配任务和现浇任务均需要考虑对常规资源的占用，装配任务需要额外考虑对空间资源的占用。为了方便问题的求解，本文将常规资源和空间资源均抽象为离散的数值，由于装配任务占用这两项资源的有效时间不同，用不同的数学符号加以区分。如图1所示。

Figure 1. Construction activities

图1. 施工活动

任务相关的属性表示如下：

i：施工活动

ia：装配任务

ib：现浇任务

a：预制率

$V_{ia}$ ：装配任务的吊装速率m³/d，若 $V_{ia}>L$ ，则 $V_{ia}=L$

$V_{ib}$ ：现浇任务的施工速率m³/d

$Q_i$ ：施工活动总的体量大小m³

$Q_{ia}$ ：装配任务体量大小 $Q_{ia}=Q_i\ast a$

$Q_{ib}$ ：现浇任务体量大小 $Q_{ib}=Q_i\ast \left(1-a\right)$

$T_i$ ：施工活动的开始时间 $T_i=\min \left(T_{ia},T_{ib}\right)$

$T_{ia}$ ：装配任务的开始时间d

$T_{ib}$ ：现浇任务的开始时间d

$Q_{ia}/V_{ia}$ ：装配任务的持续时间d

$Q_{ib}/V_{ib}$ ：现浇任务的持续时间d

$d_i$ ：施工活动的持续时间， $d_i=\max \left(T_{ia}+Q_{ia}/V_{ia}-T_i,T_{ib}+Q_{ib}/V_{ib}-T_i\right)$

针对K种可更新的常规资源，采用K维向量 $r_{ia},r_{ib}$ 来表示。例如在某一装配式建筑施工活动中共考虑三种可更新的常规资源，某一装配任务ia对这三种资源的单位需求量分别为12，15，8，则该装配任务ia对常规资源的单位需求量为 $r_{ia}=\left(12,15,8\right)$ 。空间资源将在定义2阐述。

$R_k$ ：第 $k\left(k=1,2,3,\cdots ,K\right)$ 种资源的总容量

$R_{iak}$ ：装配任务ia对第k种资源总的需求量， $R_{iak}=r_{ia}\ast Q_{ia}$

$R_{ibk}$ ：装配任务ib对第k种资源总的需求量， $R_{ibk}=r_{ib}\ast Q_{ib}$

$c_k$ ：占据单位资源的成本

定义2：周转空间。在建筑施工作业现场，需要在原有建筑物或构筑物所占场地面积之外，合理安排各种机械设备、运输道路所需的空间，以保证施工活动有序进行。针对装配式建筑，由于预制构件相对现浇活动所需的钢筋混凝土等材料堆放要求更高，在场地狭小的情况下，能够划分给预制构件堆放的临时堆场面积受限，预制构件需要根据临时堆场的大小进行动态周转。根据装配式的特性，对本问题考虑的周转空间假定如下：① 现浇活动所需的原材料例如钢筋混凝土等所需的周转空间不受限；② 仅将预制构件所需的临时堆场作为量化周转空间的约束条件；③ 临时堆场一旦被某一项预制活动所需的预制构件所占据，在其完成吊装之前不可以被其他预制活动再次占用。

周转空间的相关属性表示如下：

L：临时堆场总容量m³

$L_{ia}$ ：装配任务ia针对临时堆场的需求量m³

$l{c}_k$ ：占据单位临时堆场的管理成本

LC：临时堆场的固定成本

定义3：时间窗。装配式建筑预制构件体积较大，现场不易储存，JIT调度是装配式建筑提高场地周转效率，降低综合成本的必然选择，除了装卸和堆放大体积的预制构件需要时间及空间之外，对运输到现场的预制构件进行例行检查同样需要时间，所以要求预制构件提前到达的时间即为时间窗。记时间窗为T。由于时间窗的存在，使得预制构件存放在临时堆场的时间与任务本身持续时间不同，且预制构件所需的容量会随时间发生变化。如图2所示。

为了便于量化预制构件对于临时堆场的需求量，从而建立周转空间受限的约束。在临时堆场堆放预制构件这一作业活动可以转化为与装配任务ia相对应的堆放任务id，以任务id所需预制构件在临时堆场内的最大容量记为堆放任务id在持续时间内对临时堆场的需求量。

$T_{id}$ ：id的开始时间， $T_{id}=T_{ia}-T$

$d_{id}$ ：堆放任务的持续时间， $d_{id}=Q_{ia}/V_{ia}-1+T$

$L_{id}=\max L{R}_{ia}=\{\begin{array}{l}{Q}_{ia},Q_{ia}/V_{ia}<T\\ T\ast V_{ia},Q_{ia}/V_{ia}\ge T\end{array}$

Figure 2. Duration of tasks under the time window

图2. 时间窗下任务的持续时间

定义4：缓冲时间。在现实情况中，装配式建筑的施工任务易受到不确定因素干扰，针对装配任务，尽管采用准时制的调度方式，但是供应不及时的现象时有发生；针对现浇任务，恶劣的气候环境，设备设施的稳定性也会对施工时间造成干扰。为了减少不确定因素对项目调度过程的干扰，需要设置一定的缓冲时间，以吸收和降低干扰因素对施工活动所造成的进度滞后影响。

为了度量所添加的缓冲时间的大小，本文利用自由时差的概念，自由时差指的是满足资源约束条件下，不影响紧后施工活动最早开始时间的当前施工活动弹性开始时间，用 ${\Delta }_i$ 表示。

${\Delta }_i=\min \left(T_j-d_i\right)-T_i,i=0,1,\cdots ,n+1,j\in S_i$ ，式中 $S_i$ 表示i紧后活动的集合。

对于施工活动i，只要干扰因素的影响导致其发生延迟的时间不超过自由时差 ${\Delta }_i$ ，此影响便不会波及后续的施工活动，有效提升了项目的鲁棒性。而不同活动添加不同单位的自由时差，对于鲁棒性的提升效果是不同的，这要依据施工活动的重要性而言。一般来说，施工活动延期单位时间，费用损失越大，工期延长越久，则这类施工活动更加重要。为了度量施工活动的重要性，引入不稳定性权重CIW [26]：

$CI{W}_i=w_i+{\displaystyle {\sum }_{j\in S_i^{\ast }}{w}_j},i=0,1,\cdots ,n+1$ ， $S_i^{\ast }$ 代表所有的后续活动的集合， $CI{W}_i$ 越大表示施工活动i发生延迟时越有可能对项目造成重大损失，为该施工活动设置足够的自由时差，能够有效保护可能造成的重大损失的施工活动，从而提高调度计划的鲁棒性。

$w_i$ ：施工活动i延迟单位时间造成的成本损失 $w_i=\alpha Q_{ia}/LR+\beta Q_{ib}$

2.2. 周转空间受限的装配式建筑的准时调度模型

某装配式建筑施工活动包含N个任务 $N=\left\{0,1,2,\cdots ,n\right\}$ ， $\forall i,j\in N$ ，其中第 $0,n+1$ 个任务为虚拟任务，执行该任务不需要时间，除此之外，其他每个任务的执行都需要一定的时间 $d_i$ 。任务从第一个开始执行，记开始时间为 $T_0$ ，依照任务的紧前关系原则依次执行所有任务，直到执行最后虚拟任务，记该任务开始时间为 $T_{n+1}$ ，令虚拟任务的开始时间就是项目完工时间。每个任务的紧前或紧后任务的逻辑关系是确定，若记 $P_j$ 是任务j的紧前任务集合，则对任一任务 $i\in P_j$ ，若任务i没有结束，则任务j不能开始，项目的完整紧前约束关系可用一个有向网络图表示，节点表示任务，两个节点之间的弧线表示任务之间存在的时序约束关系。每项任务都具备不同的预制率a，根据预制率将每项任务分为装配任务 $i_a$ 和现浇任务 $i_b$ ，活动所需时间按预制任务和现浇任务最大完成时间来计算。 $A\left(t\right)$ 是 $\left[t,t+1\right)$ 时刻正在进行的任务集合。资源约束表示为了完成全部施工活动需要K种常规资源和一种空间资源——临时堆场。针对常规资源，第k种资源的总量为 $R_k$ ，完成施工活动i需要的第k种资源量为 $R_{iak}+R_{ibk}$ 。在项目完成前的任何一个时刻，正在进行的施工活动所占用的常规资源总量不得超常规资源总量。而针对空间资源——临时堆场，其资源总量为L，完成堆放任务需要的临时堆场为 $L_{id}$ ，实际占用时间为 $d_{id}$ 。 $D\left(t\right)$ 是 $\left[t,t+1\right)$ 时刻正在进行堆放任务的集合

该问题可以描述为，装配式建筑施工活动在常规资源和临时堆场有限的条件下并行施工可能产生不同的资源冲突情况，此时，只能推后部分任务的开工时间，在符合资源约束的条件下，满足工期最小化、鲁棒性最大划及成本最优化三大优化目标。此问题可以建立如下数学模型：

$\min T=T_{n+1}$ (1)

$\text{maxRobu}=\underset{i=1}{\overset{n}{{\displaystyle \sum }}}\left(CI{W}_i\times {\Delta }_i\right)$ (2)

$\min C={\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{k=1}{\overset{k}{\sum }}{c}_k\times \left(d_i\times {\Delta }_i\right)\times \left(R_{iak}+R_{ibk}\right)}}+{\displaystyle \underset{i=1}{\overset{n}{\sum }}l{c}_k\left(d_{id}+{\Delta }_i+T\right)\times L_{id}+LC}$ (3)

s,t.

$T_j-T_i\ge d_i,i\in P_j$ (4)

$T_i=\min \left(T_{ia},T_{ib}\right)$ (5)

$T_{ia}+\frac{Q_{ia}}{V_{ia}}\le T_i+d_i$ (6)

$T_{ib}+\frac{Q_{ib}}{V_{ib}}\le T_i+d_i$ (7)

$\underset{i\in A\left(t\right)}{{\displaystyle \sum }}{r}_{iak}+r_{ibk}\le R_k,t=0,1,2,\cdots ,n+1;k=1,2,\cdots ,n$ (8)

$\underset{i\in D\left(t\right)}{{\displaystyle \sum }}{L}_{id}\le L$ (9)

${\Delta }_i=\underset{j\in S_i}{\min }\left(T_j-T_i\right)-T_i,i=0,1,\cdots ,n$ (10)

$T_i\ge 0,T_i\in N^0,i=0,1,\cdots ,n$ (11)

上述多目标优化模型中活动的开始时间 $T_i$ 为决策变量。目标函数共三个，其中：式(1)表示使最后一个虚拟活动工期 $T_{n+1}$ 开工时间最小，即达到工期最小化。式(2)表示鲁棒值最大化，以项目中各施工活动的自由时差加权和表示。目标函数式(3)表示成本最小化，成本既包括项目实施过程中，装配任务和现浇任务对常规资源的占据费用，也包括装配任务对临时堆场的占据费用。以所有资源的总费用作为项目成本。约束条件中，式(4)表示任务间的紧前约束关系；式(5)、(6)、(7)表示施工活动根据预制率分解而成的装配任务和现浇任务活动的开始时间和完成时间必须在施工活动开始时间和完成时间的约束内。式(8)表示针对每一种常规资源在 $t=0,1,2,\cdots ,n+1$ 整个项目工期内，装配任务和现浇任务对其的占用量要小于该类常规资源的提供量。式(9)表示在时间窗的存在下，堆放任务对临时堆场资源的占用量要小于临时堆场总容量。式(10)为自由时差的计算式。式(11)为决策变量 $T_i$ 的定义域。

3. 算法的设计及实现

在模型确定以后，通过改变项目中施工活动的调度顺序，确定各个活动的开始时间，就可以改变项目的进度计划方案，每个进度计划方案对应着不同的工期、成本和鲁棒值。为了获得工期短、成本低且鲁棒值大的进度方案，需要改变决策变量，在获得的多目标值之间进行比较、权衡和选择，以达到多目标优化的目的。在多目标优化领域，进化算法已经得到了广泛深入的研究和应用 [27]，其中，非支配遗传算法(NSGA-Ⅱ)是典型的多目标进化算法之一。

虽然非支配遗传算法(NSGA-Ⅱ)在一定程度上能够保留历史信息，适于求解大规模任意目标函数的全局优化问题，但是其较差的局部搜索能力也会导致算法过早的收敛，从而使获得的有效前沿质量较差 [28]。而爬山算法(Hill Climbing)，作为一种逐步寻优的搜索算法，具有很强的局部搜索能力。基于此，本文设计了嵌入爬山算法的非支配遗传算法求解：即首先基于爬山算法针对目标进行深入的局部搜索，然后利用NSGA-Ⅱ进行全局搜索。以此加速算法的收敛过程，求得问题尽可能优的有效解集：既逼近最优有效前沿，又保证解集本身分布均匀。具体算法如图3所示。

具体步骤如下：

Step 1 随机产生种群规模为N的调度方案初始种群S，种群中每个个体表示一个施工活动的调度方案，迭代次数 $gen=1$ ，最大迭代次数为MAXGEN，交叉概率为Pc，变异概率为Pm；

Step 2 令 $t=0$ ，产生初始种群为当前种群，即 $Chrom=S$ ；其中有N个个体， $x_t^j\left(j=1,2,\cdots ,N\right)$ ；

Step 3 对初始种群中的每个个体进行爬山操作，爬山算法的重复次数为M。输出结果进行后续遗传操作；

Step 4 对输出的结果进行非劣排序；

Step 5 选择、交叉、变异，产生新种群Son，用当前排序靠前的非劣解和目标函数值进行替换；

Step 6 令新种群为当前种群，即 $Chrom=Son$ ，迭代次数 $gen=1+gen$ ；

Step 7 重复Step 3~7，直至 $gen>MAXGEN$ ，算法结束，输出结果。

Figure 3. Algorithm flow

图3. 算法流程

3.1. 爬山操作设计

由于爬山操作是一个搜索过程，需要调用评价(适应值)函数来确定移动值，这就要求在计算过程中保存权系数。但是权系数如果直接取固定值，就将多目标优化问题直接转为了单目标优化问题，但这样仅能求出一个非劣解，且决策人没有选择的余地，另外，权系数的值也不好把握。所以，本文针对爬山操作，将需要的权系数取一组权向量，使同一代中各个父本对应不同的权系数。于是，在一组权系数下适应值小的，有可能被抛弃的非劣解，在另一组权系数下其适应值可能会大到得以保留。Step3具体操作如下：

Step 3.1 将种群中的每个个体作为此次爬山操作的初始解 $x_t^j$ ，也把初始解 $x_t^j$ 作为当前最优解。对 $x_t^j\left(j=1,2,\cdots ,N\right)$ ，计算 $f_1\left(x_t^j\right),f_2\left(x_t^j\right),f_3\left(x_t^j\right)$ 三个目标函数值。

Step 3.2 考察群体中所有个体，相对整个群体而言，满足非劣解的个体(设为M个，组成的集合为Q)，其中， $x_t^1,x_t^2,\cdots ,x_t^m$ 以概率1保存到下一代，其对应的权系数保持不变。接着在剩下群体中，重复如下操作继续选择 $N-M$ 个个体作为下一代的父体。

Step3.2.1 若 $t=0$ ，随机产生三个随机数 $r_1,r_2,r_3$ ，令 $k_{iq}=\frac{r_q}{r_1+r_2+r_3}$ , $q=1,2,3$ , $i=1,2,\cdots ,N$

若 $t\ne 0$ ，随机产生三个随机数 $r_1,r_2,r_3$ ，令 $k_{iq}=\frac{r_q}{r_1+r_2+r_3}$ , $q=1,2,3$ , $i=M+1,M+2,\cdots ,N$

Step 3.2.2 计算 $F\left(x_t^j\right)=k_{i1}{f}_1\left(x_t^j\right)+k_{i2}{f}_1\left(x_t^j\right)+k_{i3}c{f}_1\left(x_t^j\right)\left(j=1,2,\cdots ,N\right)$

Step 3.2.3 从群体中选择一个个体作为下一代的父本点，每个个体被选中的概率为 $P_i=F\left(x_t^j\right)/{\displaystyle \sum F\left(x_t^j\right)}$

Step 3.3 使得选定的个体作为初始解集，每个初始解对应的权系数保持不变。选定一个初始解，记录当前最优解 $x_{best}=x_0$ ，令 $P=N\left(x_{best}\right)$ (表示 $x_{best}$ 的邻域)。

Step 3.4 采用2opt法在 $x_{best}$ 的领域内随机产生另一个解 $x_{now}$

Step 3.5 通过对应的权系数对比 $x_{now}$ ， $x_{best}$ 的优劣，若 $x_{now}$ 优于 $x_{best}$ ，则取 $x_{now}$ 作为下一次迭代的初始解。若 $x_{best}$ 仍优于 $x_{now}$ ，则重复步骤4操作直到 $x_{now}$ 优于 $x_{best}$ ，若经过T次操作，仍无法使得 $x_{now}$ 优于 $x_{best}$ ，则取 $x_{best}$ 作为下一次迭代的初始解。

Step3.6 以步骤3.5输出的结果为新的初始解，重复上述步骤3.3，3.4，3.5过程M次，取最后输出结果进行遗传操作。

3.2. 遗传算法设计

1) 编码设计：在本研究问题中，解空间即各项活动的开始时间由活动的有序列表和自由时差列表共同构成。所谓活动的有序列表，是根据施工活动组成的有向网络图，采用一定方法生成的一个可行的调度方案。本文选择SSS (Serial Scheduling Scheme)，将活动分为J个阶段，对应每个阶段，存在不交集的两个活动集合，一个不完全计划 $F_p$ (该集合中所有施工活动已经被安排调度)和一个候选工作集 $L_p$ (施工活动尚未安排开始时间)。在每一个新的调度阶段，选择 $L_p$ 中优先权最大的施工活动(若火哦的那个优先权一致，则选择编号小的工作)加入 $F_p$ 中。不断进行迭代，直至串行调度方案生成完毕。

2) 非劣排序：由于本文研究的是多目标问题，无法直接将目标函数转为个体的适应度，本文采用非劣排序方法来判断个体的优劣。将当代种群中所有的个体按照优劣依次进行排序，排序越靠前，适应度越大，越有机会遗传给下一代被保留。

本文采用如下两个步骤来进行step4的优劣排序：

Step 4.1 比较两个个体X¹和X²对应可行解的三个目标值即工期、成本和鲁棒值。若个体X¹至少有一个目标值比个体X²的好，且个体 的所有目标都不比X²的差，那么称个体X¹支配个体X²，排序在X²前。其他情况则转至Step 4.2

Step 4.2 当两个个体X¹和X²不存在支配关系时，即个体X¹既有目标值优于个体X²，也有目标值劣于X²。此时，采用比较拥挤度方法来进行优劣排序。

Step 4.2.1 将种群中的个体按照三个目标值分别进行排序；

Step 4.2.2 就每个个体在三组序列的不同位置分别计算相应目标值拥挤度：取该个体排序中前后两个个体的差值，除以该序列最大插值，得到该个体该目标的单一拥挤度；

Step 4.2.3 将单个个体在三个序列中不同目标的拥挤度相加得到该个体的拥挤度大小；

Step 4.2.4 按照拥挤度大小对不存在支配关系的个体进行排序，拥挤度越大，个体越优秀，排序越靠前。

3) 选择操作：采用精英保留策略和轮盘赌相结合的方式。首先，根据优劣排序的结果，选择排序靠前的部分个体作为“精英”直接进入下一代，以保证每代之间最优秀的个体都被保留了下来。接着，采用轮盘赌法，父代中选出一定比例的染色体，进行后续的交叉和变异操作产生子代个体。

4) 交叉操作：为了保证交叉后的个体仍旧满足项目的网络关系，本文采用MUCOX (multi-component uniform order-based cross-over)来进行交叉操作，该法适用于遗传算法，在对存在紧前紧后优先关系约束的染色体基因实施遗传操作时，会保证交叉后的染色体基因仍旧满足父代对的优先关系。

5) 变异操作：由于本遗传算法的染色由活动有序列表和自由时差列表两组基因组成。若在交叉操作时，对活动有序列表进行调整，极易扰乱原有的优先逻辑关系。于是，本文选择对自由时差列表进行变异操作，即随机选取某个施工活动，随机增大或者减小其自由时差，从而得到变异个体。

4. 算例验证及结果分析

4.1. 算例及结果

本文以某项目为例，该项目为整体装配式剪力墙结构。以一个标准层的单装配空间为例进行算例分析。该标准层中包含的预制构件有：预制夹心混凝土外墙、预制内隔墙、预制柱、预制叠合梁、预制楼板、预制楼梯、预制阳台、预制空调板等预制构件。

该工程项目的网络计划如图4所示，共考虑9项施工活动，各个施工活动均按照对应的预制预制率分为现浇部分和装配部分，各个施工活动的时间均包含了放线、吊装、支撑、浇筑、养护等细部工作时间。其中，工作准备、标高测度、收尾工作默认时间分别为1.5、2、2.5天。预制构件占用临时堆场资源的时间则要按照预先设定的时间窗T = 2进行推算。各项施工活动的名称及参数情况如表1所示：

Figure 4. Project network plan

图4. 项目网络计划图

Table 1. Relevant parameters of construction activities

表1. 施工活动的相关参数

依据项目资源可调配的实际情况，选取了活动系数较高的3种资源，包括2种常规资源——专业人员(司机、混凝土工、钢筋工、木工等)；专业设备(塔吊、电焊机、切割机等)和1种空间资源——临时堆场。为了明确资源在各个活动种的比例关系，也为了便于模型求解，算例中各类资源都以需单位进行计量，参数的获取主要来自于项目的调研及数据沉淀，各项可支配资源的情况及各类资源的单位成本见表2：

Table 2. Resource availability

表2. 资源可用量

应用第2节设计的多目标模型和第3节设计的混合遗传算法求解上述装配式建筑的调度优化问题。利用Matlab10.0对算法进行编译，在CPU为双核奔腾2.9GHz，内存为4G，操作系统为window10的PC机上仿真运行。对算法种的各种参数设置如下：种群规模 $N=50$ ，最大迭代次数 $MAXGEN=10$ ，交叉概率 $P_c=0.9$ ，变异概率为 $P_m=0.005+0.005\ast gen/MAXGEN$ ，爬山操作种迭代次数设置为10。将算法随机运行8次，将所有代际的非劣解合并共得到42个不同的非劣解，删除密度较大的个体，最终保留30个分布比较均匀的非劣解构成一个Pareto 前沿，如图5所示。

通常，指标的优劣可以通过其收敛性和分布性来判断，某次运算下每代的非劣解如图6所示。为了判断算法的收敛性，我们可以计算每一代的进化率，例如，第n代的进化率为被第n代所占优的第(n−1)代非劣解个数/第n代非劣解个数。8次运算的平均进化率如图7所示。

另外，选择10个非支配解作为代表，每个解对应的工期、成本、鲁棒值见表3。

1) 图5的近似Pareto最优前沿反映了三个目标函数之间的权衡关系：随着工期和成本的减小，鲁棒性也随之减小；随着工期、成本的增大，鲁棒性也随之增大。帕累托曲面上的解相对于其他可行解，工期更小，成本更低，鲁棒性更大，是相对更优的解。所以，三个目标函数的综合优化需要在帕累托曲面上进行。

Figure 5. Approximate pareto optimal frontier

图5. 近似Pareto最优前沿

2) 由图6可知，随着进化代数的增加，每一代产生的位于帕累托曲面上的解的个数不断增多，到了进化的中后期，每一代产生的位于帕累托曲面上的解的数量趋于稳定，且分布性越来越好。在第160代左右，实现对帕累托最优前沿的逼近。从图7的平均进化率也可以看出，随着进化代数的增加，进化率不断减小，到100代左右，平均进化率已经很小，到160代左右，基本实现收敛。

Figure 6. Solutions for different generations

图6. 不同代的解

Figure 7. Average evolution rate per generation

图7. 每代平均进化率

3) 由表3可知，每个进度方案所对应的目标值各有优劣。方案3、方案6的工期最短，为26天，但鲁棒值较小；方案10鲁棒值最大，但是工期和成本都较高；方案6成本最小，大致为32,528元，但鲁棒值也是最小的。由表格可见，没有一个调度方案的三个目标值均优于其他方案，均为非劣解。决策者决策者可以根据不同的需求和倾向在非劣解集中进行权衡，选择项目匹配度最高的方案。

Table 3. Calculation results of scheduling scheme

表3. 调度方案计算结果

4.2. 敏感性分析

为了进一步观察模型种预制率和临时堆场资源对调度结果的影响，本文做了如下敏感性分析。

1) 预制率对调度结果即工期、成本和鲁棒性的影响

表4及图8是预制率对调度结果即工期、成本和鲁棒性各项值的影响，即保证其他参数不变，扩展预制率a，即将每个施工活动对应的预制率乘以相同的扩大系数γ，使得γ在[0, 1.6]之间以步长0.2变动。在每个扩大系数下，得到10个指定迭代次数下的非劣解，取平均值，得到平均最小工期、平均最小成本及平均最大鲁棒值。

Table 4. Sensitivity analysis of prefabrication rate

表4. 预制率敏感性分析

结果表明：① 当a ≤ 1.2时，最小工期、最小成本和最大鲁棒值变化不大，无明显差距，说明项目的工期、成本、鲁棒值对预制率并不敏感。② 从工期变化来看，总工期从35天到56天。当a ≤ 1.2，总工期虽有所减小，但变化不大，这是因为在较小预制率的情况下，装配任务的最大储存需求量不会超过临时堆场的总容量，随着预制率的提高，虽然装配任务会缩短施工活动时间，但是为了不稳定性权重会有所增加，导致缓冲时间有所增大，所以总工期的缩短趋势并不明显。当a = 1.2时，工期有较明显的增长，产生该结果的主要原因是由于0.5的扩展比例使得装配任务的最大储存需求量超过了临时堆场的总容量，不得不推后某些装配任务的实施，造成工期明显延长，成本和鲁棒值也相应增大。由此说明，此时预制率对调度结果的影响主要还是来源于临时堆场的限制，据此推断，项目的工期、成本、鲁棒值对临时堆场敏感度较高，下文会对临时堆场资源做针对性的敏感性分析。③ 从费用变化来看，总费用从35,664到66,638。当a ≤ 1.2临时堆场占用成本逐渐增大，专业人员占用成本逐渐减小，设备资源占用成本却逐渐增大，所以在工期变化不大的情况下费用变化也不明显。但当a > 1.2时，由于工期有较明显的增长，各种资源由于占用时间明显增大，费用也会明显增加。

Figure 8. Influence of prefab rate on scheduling results

图8. 预制率对调度结果的影响

2) 临时堆场大小对调度结果即工期、成本和鲁棒性的影响

表5及图9给出了临时堆场对调度结果即工期、成本和鲁棒性各项值的影响。即在保证其他参数不变的情况下，让临时堆场以步长20在[40, 120]范围内变动。在每个临时堆场资源的水平下，得到10个指定迭代次数下的非劣解，取平均值，得到平均最小工期、平均最小成本及平均最大鲁棒值。

结果表明，工期随着临时堆场总容量的增加而减小，而平均最小成本和平均最大鲁棒值在不同临时堆场资源的情况下，并无较大差距，这说明项目工期对于临时堆场资源的变化十分敏感，成本和鲁棒值对于临时堆场资源的变化不敏感。增大临时堆场面积可以缩短项目工期，但是随着临时堆场面积的增大，缩短项目工期的效果也会变差。

Table 5. Sensitivity analysis of temporary storage yard resources

表5. 临时堆场资源敏感性分析

综上，通过建立以工期、费用及鲁棒性综合最优为目标的多目标模型，应用加入爬山操作的混合遗传算法，获得了项目实例的非劣解集。各个非劣解对应于不同的调度方案，在工期、费用及鲁棒值三个目标值上各有优劣，决策者可以根据不同的需求和倾向在非劣解集中进行权衡与决策。另外，通过对预制率和临时堆场两个不同参数的敏感性分析，我们发现，项目的工期、费用及鲁棒值对预制率并不敏感，而较大的临时堆场却能有效缩短项目工期。

Figure 9. Influence of temporary storage yard on scheduling results

图9. 临时堆场对调度结果的影响

5. 结论

1) 本文所建立的数学模型，在装配式建筑特点的基础上，不仅通过预制率将施工活动分为了吊装任务和现浇任务两部分，而且通过时间窗的设置建立了准时调度与临时储存的动态关系，充分考虑了不确定因素对各个目标值的影响，反映了装配式建筑调度的实际现状。

2) 所提出的嵌入爬山操作的混合遗传算法能克服遗传算法早熟现象，在收敛性和避免局部最优方面有较大改善。实例计算证明，该算法能有效求得多目标函数的非劣解。

3) 探讨预制率和临时堆场资源对调度结果即工期、成本和鲁棒性各项值的影响，得出：① 项目的工期、成本、鲁棒值对预制率并不敏感；② 项目工期对于临时堆场资源的变化较为敏感，增大临时堆场面积可以缩短项目工期，但是随着临时堆场面积的增大，缩短项目工期的效果也会变差。

本研究可以为装配式建筑的调度方案提供决策支持，决策者可以根据自己的需求和倾向选择最优方案。本文所进行的研究未考虑供应环节、运输环节的调度方案，仍有待进一步深究，未来可往供应链调度最优方向拓展。

参考文献