基于多目标差分进化算法的预制构件生产重调度研究

于 淼，赵 洁，焦红超

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

装配式建筑在我国发展还不够成熟，预制构件生产管理专业化程度低，生产过程中出现了调度混乱、生产效率低下、成本高等问题[1]，一定程度上阻碍了建筑工业化进程。因此，对预制构件进行科学排产极其重要。目前，众多学者对预制构件生产车间展开了研究，有学者针对生产工序对模型进行了改造。Li等[2]从供应链角度考虑预制构件生产过程的劳动力、库存资源约束，构建了以生产成本最小化为目标的生产调度模型。Wang等[3]通过构建全供应链生产调度模型，分析了新增工序对完工时间的影响规律。Kong等[4]在原有生产调度模型中增加装配环节，指出装配式建筑包含生产—运输—装配3个部分，建立了以最大生产效率为目标的装配式建筑全过程的资源调度模型。

为贴合现实生产条件，一些学者把资源约束引入生产调度模型，Chan等[5]在约束条件中加入养护室处理能力约束。Ko等[6]在Chan等[5]的基础上增加了相邻两个工位之间的缓冲区容量约束，提高了模型实用性。在算法求解方面，遗传算法应用较多。谢思聪等[7]运用遗传算法，解决了招投标和生产两个阶段的预制构件优化问题。程月明等[8]运用非支配排序遗传算法求解了考虑养护窑数量的混凝土预制构件优化模型。Ma等[9]采用非支配排序遗传算法(Non-dominated Sorting Genetic Algorithms，NSGA)对多条生产线优化模型进行了求解，完成了多条生产线优化。

上述研究都是针对考虑资源约束的装配式建筑预制构件的静态生产调度的，忽略了预制构件加工环境的动态性和不确定性。此外，在预制构件生产调度效果评价上，对完工时间和惩罚成本这两个相互冲突的目标的处理上存在欠缺。针对以上研究存在的不足，笔者在综合考虑模板约束和缓冲区约束的条件下对紧急插单情况下装配式建筑预制构件多目标生产调度问题进行研究，运用多目标差分进化算法，优化预制构件生产调度方案，通过合理安排构件生产顺序，保证构件在满足完工时间最短和惩罚成本最少的双目标下顺利交货。

一、预制构件生产调度问题描述

混凝土预制构件生产车间与制造业的生产车间类似，都是经过各种生产环节，生产出所需要的产品[10]。预制构件的生产过程如图1(a)所示。根据生产的工艺特征将其分为并行工序和串行工序，其中，混凝土养护为并行工序，可同时处理多个工件，其余则为串行工序。在预制生产环境中，该条流水线由Nk道工序组成，待生产j个预制构件，每个预制构件均包含Nk道工序，且这j个预制构件必须在所有工序上以相同的顺序进行加工。Sj，Nk为对预制构件(j，Nk)开始进行加工的时间；Pj，Nk为对预制构件(j，Nk)进行处理所需的时间；E(j，Nk)为预制构件加工结束的时间；dj为不施工方向预制构件生产方提出的交货日期。该批预制构件的调度结束后，有一批数量为n*的紧急插单任务出现(见图1(b))，需要立即进行排程，将这批预制构件记为j*={n+1，n+2，，n+n*}。插单对生产计划造成扰动，原先的调度计划失效，需要进行重新调度。

图1 预制构件生产工序与问题描述

预制构件生产应当满足以下要求：①每个工件必须按1，2，，m顺序在所有机器上进行工序处理；②除混凝土浇筑、养护外，其余工序均为抢占式工序；③预制构件的加工时间包括其准备时间，已知且不会发生变化；④除混凝土养护外，工序允许等待。

二、预制构件生产调度模型

预制构件生产调度模型参数如表1所示。

表1 预制构件生产调度模型参数定义及说明

1.优化目标

对预制构件调度结果进行评价时，需要同时兼顾多个目标，确保调度结果符合预制构件生产优化的要求。因此，本研究选用完工时间和惩罚成本作为评价指标，对调度结果进行评价。完工时间为

f1=E(n，Nm)

(1)

惩罚成本通过完工时间大于交货期产生的延迟成本和小于交货期产生的库存成本两部分的和来计算

(2)

式中：Ej为预制构件j的完工时间。

目标函数为

F=min(f1，f2)

(3)

2.约束条件

(1)可中断工序

模具组装、预埋件放置、拆模、构件修补均属于可中断工序，即在8 h内该工序没有完成，可延后到第二天完成。可中断工序的完工时间为

1，2，5，6

(4)

预制构件生产工序累计完成时间为

T=max[E(j-1，Nk)，E(j，Nk-1)]+Pj，Nk

(5)

(2)不可中断工序

①混凝土浇筑。混凝土浇筑过程中涉及水泥的使用，属于不可中断工序，如果在加班时间内可以完成，则选择加班完成，反之，混凝土浇筑工序应推迟到第二天进行。预制构件混凝土浇筑工序完工时间为

E(j，Nk)=

(6)

式中：HA为加班时间(HW>HA)。

②混凝土养护。混凝土养护属于非抢占式工序，不同类型的预制构件可以在同一时间进行养护，因此，混凝土养护开始时间在浇筑工序之后，其完成时间为

T*=E(j，N3)+Pj，Nk

(7)

E(j，Nk)=

(8)

③模板约束。预制构件生产效率受模具数量的影响，因模板数量有限，会出现预制构件模板等待时间。当模具均被占用，只有等先进行拆模工序的预制构件释放模板后，下一个预制构件才能开始模具安装。第j个预制构件使用β模具的开始时间为

S(j，β，N1)≥minXβ{∀y{E(y，β，N5)}}

(9)

式中：β为模具类型；Xβ为模具β的数量。

④缓冲区约束。缓冲区约束指相邻工序之间的空间容量要大于预制构件半成品的需要[11]。若工序Nk与工序Nk+1之间的存储容量为BNk，那么构件j从Nk离开的时间必须晚于构件j-BNk进入Nk+1的时间，此举可保证各工序之间不发生阻塞现象。缓冲区约束表达式为

E(j，Nk)≥S(j-BNK，Nk+1)

(10)

三、算法设计

多目标差分进化算法是一种主要针对多个目标进行优化的算法。利用父代个体向量间差分的原理进行种群个体的迭代更新，得到所求问题的最优解。算法包括交叉、变异和选择3个核心操作，符合进化算法的一般流程[12]。

1.编 码

采用整数序列编码方式，先将工件连续编号，再将工件编号的排列组合作为一个完整的编码序列。例如：工件总数为10，随机编码序列A=[4,6,5,3,8,2,1,9,7,10]，说明每道工序加工的工件顺序为4，6，，10。

2.适应度函数

适应度函数用z1、z2表示，计算式为

z1=f1；z2=f2

(11)

3.种群初始化

设置种群规模、最大迭代次数、交叉概率。随机生成1个初始种群p，对初始种群p的适应度函数值进行计算。

4.交叉变异

对初始种群p进行交叉变异，产生第二代种群q，计算第二代种群q的适应度值。

5.引入支配关系

对p、q进行比较，如果p支配q，挑选p作为新一代种群，如果p与q没有支配关系，则全部作为新一代种群。

6.拥挤距离计算

对步骤(5)产生的新种群按照式(12)进行拥挤距离计算，然后根据计算结果挑选拥挤距离大的个体产生新的种群。

(12)

7.终止准则

若满足G≥100，则输出Pareto最优解集；反之，令迭代次数G=G+1，直到达到最大迭代次数，终止循环。

完整的MODE算法流程如图2所示。

图2 MODE算法流程

四、案例分析

笔者以某企业的预制外墙板生产线为例进行分析，其预制构件生产信息如表2所示，其中，N1为模具组装；N2为预埋件放置；N3为混凝土浇筑；N4为混凝土养护；N5为拆模；N6为构件修补。预制构件各工序加工时间与交付时间、违约费与库存费均通过实地调研和与部分负责人访谈得到(见表2)。在这一批次的8个预制构件生产过程中，使用了A、B、C 3种模具。每天的常规工作时间(HW)为8 h。根据企业要求，加班时长(HA)不能超过4 h，相邻工位缓冲区空间设置为1，即相邻工位能同时容纳1个预制构件。预制构件生产准备工作已经做好，收到一个紧急订单，该订单包含2个预制构件H，其生产信息如表3所示。

1.初始调度方案求解

数值计算过程中，初始种群规模NP=100，交叉概率CR=0.9，最大迭代次数G=100，采用MATLAB R2018b 软件编程，利用多目标差分进化算法实现多目标调度优化。根据算法所设置的数值精度，对模型进行求解，求得Pareto最优解集(见图3)。该初始调度产生3个调度方案(见表4)。

表2 预制构件生产信息

表3 紧急插入订单信息

2.预制构件重调度

紧急订单出现后，需要对初始预制构件和紧急订单中的构件进行重新决策，首先选择初始调度中设备闲置时间最大的方案，对该方案中预制构件和紧急订单中包含的构件进行重调度。新增2个预制构件H各工序占用各工序的处理时间如表5所示。

图3 MODE算法优化得到的Pareto最优解

表4 预制构件生产初始调度计划

表5 新增预制构件生产占用各工序时间 h

(1)重调度生产方案选择

初始调度方案中，各工序空闲时间为从该工序生产的持续时间中抽去所有加工工件在机器上加工处理的时间，则各方案的各工序闲置时间如表6所示。方案1的机器闲置时间为173.4 h，闲置时间最长且大于表5中新增构件H所需的生产时间，因此，选择方案1进行生产重调度。

表6 预制构件生产初始调度各方案闲置时间 h

(2)重调度求解

根据方案1，由于紧急订单到达时，4号预制构件的第一道工序已经完成，进行重调度时其第一道工序加工时间为0，则方案1预制构件生产重调度模型输入信息如表7所示。

表7 预制构件生产重调度模型输入信息

笔者运用多目标差分进化算法对预制构件重调度模型进行求解，得到4个新的调度方案(见图4)。为突出该算法的求解效果，将多目标差分进化算法与启发式算法NEH(Nawaz、Enscore、Ham)进行比较，NEH算法的核心思想是根据工件的加工时间把工件按照从大到小的顺序进行排列。选取序列中最靠前的两个工件进行组合，找到最小的工件排序，重复以上操作，直到全部工件被组合完毕[13]。启发式算法NEH的参数设置参考多目标差分进化算法(MODE)、初始种群迭代次数、交叉概率，优化后得到2个新的调度方案(见图5)。

图4 MODE算法优化得到的重调度Pareto最优解

图5 NEH算法优化得到的重调度Pareto最优解

笔者引入距离和CPU运行时间两个指标对两种算法得到的帕累托最优解的质量进行评价。

①距离指标(GD)是检验算法求得的所有非支配解之间的远近程度的数值[14]。计算式为

(13)

式中：C为非支配解集合中的解的数量；dp为所有非支配解中任一向量距离与其他向量之间的最小欧式距离。GD越小，则非支配解距离非支配解集合越近，算法性能越好[14]。

②CPU运行时间是主要用于检测算法运行效率的指标。运行效率随着运行时间的缩短而提高。

根据两种算法的优化结果计算上述两项指标，评价结果如表8所示。比较运行时间可知，MODE算法比NEH算法时间短，其运行效率优于NEH算法；比较距离可知，MODE算法比NEH算法更接近最优解，其收敛性更好。

表8 多目标优化实验结果对比

3.结果分析

MODE算法优化得到4个调度方案(见表9)，完工时间随着惩罚成本的增加而减少。因此，当企业接到紧急订单时，可以选取完工时间最小的方案进行生产。

表9 MODE算法优化得到的预制构件生产重调度计划

五、结 语

笔者通过对插单扰动下装配式建筑预制构件生产重调度问题进行研究，优化了预制构件生产顺序，达到了降低预制构件生产成本的目的。通过构建多目标的预制构件生产调度模型，选取多目标差分进化算法进行算法设计，求得最优预制构件排产计划，并通过案例分析证明了所构建的求解预制构件生产优化模型操作简单，运用的多目标差分进化算法在获得Pareto最优解上优于启发式算法，进一步丰富了预制构件生产求解思路，可为装配式建筑预制构件生产方提供参考，有利于预制构件生产方针对紧急插单问题，安排合理的排产计划。