熊福力，储梦伶

(西安建筑科技大学 信息与控制工程学院，陕西 西安 710055)

0 引言

近5年来，中国等多个国家出台了一系列政策，推动预制构件产业化发展，提高其占全部建筑的比例。北京市住房和城乡建设委员会发布了《2020年生态环境保护工作计划和措施》来继续稳步推进装配式建筑工作，力争2020年实现装配式建筑占新建建筑面积比例30%以上。与现浇施工相比，预制构件因具有耐用性、美学多功能性、节能环保的独特优势[1]而广受欢迎。

预制构件的生产过程属于流水生产过程，到目前为止，关于预制生产调度已有不少研究成果。LEU等[2]考虑了起重机和工人影响因素下的调度；KO等[3]在处理时间和系统故障引起的干扰等不确定因素下，研究了预制构件生产调度；KHALILI等[4]针对预制构件资源优化问题，在考虑预制构件配置策略和组件分组策略的基础上建立了该类问题的混合整数线性规划模型；CHAN等[5]建立了一个流水车间排序模型，并采用遗传算法(Genetic Algorithm, GA)对模型进行优化。然而，以上文献均在假定交货期固定的条件下研究预制构件生产调度问题，而在实际生产中，制造商往往需要根据企业的生产能力与客户协商制定交货期，并通过拒绝部分订单来减少拖期惩罚以获取最大利润，因此需要综合考虑交货期配置和生产调度。

为了按期交付产品，制造商需要为客户指定有效的调度方案并配置合理的工期，否则将会因生产调度不当导致预制构件延迟交付，增加总工期和总成本并造成客户流失。合理的优化和调度方法是增加收益、降低成本、提高客户满意度和节约时间的关键。LI等[6]在新工件到达时，通过重调度确定交货期；KIM等[7]采用离散时间仿真方式实时响应交货期变化，考虑交货期不确定下的调度新规则，并建立了动态生产调度模型；SHABTAY[8]以最小化提前惩罚和拖期惩罚为目标，研究了一类交货期可控的单机调度问题；CHEN等[9]研究了一个同时包含工件处理调度和交付调度的单机调度问题；BACKER[10]对离散和间歇过程的提前—拖期调度问题进行研究，但未考虑订单接受问题；GUERRERO等[11]最早提出订单接受与调度(Order Acceptance and Scheduling, OAS)问题。在此基础上，WANG等[12]开发了两种启发式调度方法，在两台功能完全相同的处理机上实现了利润最大化；NOBIBON等[13]研究了计划订单和潜在订单，以及订单的调度问题。无论在传统流水车间生产环境还是预制构件生产环境下，有关订单接受、调度与交货期配置问题的综合优化尚未有文献报导。预制构件的工况具有可中断和不可中断、串行和并行工序并存等特点[2-5]，比传统的流水车间生产更加复杂，在实际预制构件生产过程中，迫切需要对交货期配置、订单接受和调度进行同时优化，然而三者集成优化的难度非常具有挑战性。

鉴于预制构件生产调度问题的复杂性，通常采用智能优化算法解决该类问题。在预制构件调度方面，学者们采用GA[14-18]、禁忌搜索[19-21]、粒子群优化算法[22]、精确算法[23-25]等求解流水车间调度问题。虽然迭代贪婪算法(Iterated Greedy algorithm, IG)易于实现且在求解置换流水车间调度问题上具有较大优势，但是研究仍然不够深入；RUZI等[26]设计了IG解决置换流水车间调度问题；RIBAS等[27]针对阻塞流水车间调度问题提出一种IG，在计算时间和求解质量上取得了较好的效果。大多数IG研究是从改进原始标准IG中的破坏—构造机制入手,达到提升IG求解质量和求解效率的目的,而对IG中邻域搜索方式的研究相对较少。

本文针对预制构件的实际生产过程，建立了交货期配置、订单接受与调度集成(Integrated Due date assignment, Order acceptance and Scheduling in Precast Production Environments, IDOS_PPE)优化模型。在交货期可变的情况下固定工件排序，通过统计和深入分析实际生产数据，挖掘问题知识用于引导算法搜索方向，探讨问题的解决方案，获取最优交货期策略，通过集成变邻域结构提出一种用于求解IDOS_PPE问题的高效IG来优化预制生产总收益，以期为预制构件制造企业提供启示。

1 IDOS_PPE优化模型

1.1 问题描述

IDOS_PPE问题可被描述如下:在预制流水车间环境中，需要被安排的待加工工件集合J={j1,j2,…,jJ}；每个待加工工件j需在6道工序S={S1,S2,…,S6}上处理且每种类型工件的各道工序处理时间pj,s均已知；工序之间遵循工艺约束,每个工件按照预制构件的生产流程依次经过6道工序进行生产，即各工件依次经过模具组装、预埋件安装、浇筑、蒸汽养护、拆模和精加工；要求同时优化订单交货期、订单选择和生产调度，使净利润最大。需要指出的是，与传统流水车间调度问题相比，IDOS_PPE问题具有如下特点：

(1)研究对象层面

与传统流水线不同的是，预制构件生产流水线具有串并行混合生产的特点，例如在蒸汽养护阶段，多个蒸汽养护室可以同时并行处理多个工件，而其他5个生产阶段则为串行生产阶段，同一时刻只能处理一个工件。同时从预制构件生产实际出发，考虑8小时工作制和4小时加班制，每天都有12 h非工作时间，这个时间段内需要工人参与的生产过程将无法进行，而传统的流水生产[26-27]通常假设一天24 h均可利用；预制构件生产流程中既包括可中断工序又包括不可中断工序，如图1所示。例如在浇筑阶段，一旦开工就不允许中断，因此在浇筑阶段安排生产时，应该考虑在工人下班之前能否完成，如果无法完成，则安排在下一个工作日开工；在模具组装、预埋件安装、拆模和精加工等生产阶段，如果加班后还无法完成，则允许中断，未完成的工作将推迟到下一个工作日，而传统的流水生产过程通常假设各个阶段的生产过程不可间断。综上所述，本文研究对象考虑了可利用时间与不可利用时间、串并行混合、可中断与不可中断混合等生产特点，比传统的流水车间更加复杂。

(2)决策问题层面

传统的流水车间调度问题通常假定订单和交货期固定，对流水线的工件生产做出调度决策。在预制构件生产竞争日益激烈的环境下，为避免过高的惩罚费用并追求利润最大化，预制构件制造商通常并不盲目接受所有订单，而是根据预制构件企业生产能力和顾客需求选择可以获得更多利润的订单；同时在顾客容许的范围内确定交货期，进而安排订单生产调度。因此，该问题是比传统流水车间调度问题更复杂的多层次离散集成优化问题，需要对订单选择、交货期配置和生产调度进行综合决策。

1.2 参数及变量说明

(1)模型标引及参数

J为订单数量；

j为订单索引，j∈J:={1,…,J}；

[k]为位置索引，k∈K:={1,2,…,J}，表示在一个生产序列中的第k个位置；

s为工序索引，s∈S:={1,2,…,6}；

pj,s为订单j在第s道工序的处理时间；

Qj为订单j的毛利润；

HW为工作日正常工作时间，HW=8 h；

HA为工作日允许加班时间，HA=4 h；

HN为工作日非工作时间；

deadlinej为订单j的截止日期；

wj为订单j的单位时间拖期惩罚系数；

γj为客户满意度系数；

πj为序列中的第j个订单；

Π为订单调度方案，π∈П:={π1,π2,…,πj}。

(2)决策变量

yj为二进制变量，如果订单j被接受则为1，否则为0。

xj,[k]为二进制变量，如果订单j被接受并分配给生产序列中的第k个位置则为1，否则为0；

Cj为订单j六道工序的完工时间，Cj:=Cj,6；

Cj,s为订单j在第s道工序的完工时间；

C[k],s为订单j在生产序列第k个位置第s道工序的完工时间；

Tj为订单j的拖期；

A[k],s为订单在生产序列第k个位置第s道工序的累计时间；

D[k],s为订单在生产序列第k个位置第s道工序的累计工作天数。

1.3 数学模型

大多数企业在预制构件生产调度环节希望尽可能多地获得利润,因此以最大化净利润为优化目标建立调度优化模型。本文所建模型基于如下假设:①订单在机器上的设定时间忽略不计；②工位和模具之间的缓冲区是无限的；③生产中没有优先权，先处理到达订单；④不考虑机器故障、工人缺勤等紧急情况；⑤来自同一个客户的订单分解为多个生产订单，一个生产订单抽象为一个工件。

(1)

yj∈{0，1},xj,[k]∈{0，1}；

(2)

C[k],s≥0,D[k],s≥0,A[k],s≥0；

(3)

(4)

(5)

(6)

(7)

D[k],s=⌊A[k],s/24⌋,∀s；

(8)

s∈{1,2,3,5,6},k∈K{1};

(9)

s∈{1,2,5,6},k∈K；

(10)

(11)

(12)

C[k],s=

s=4,k∈K。

(13)

其中：式(1)为目标函数，TNR为总净利润，NRj为订单j的净利润；式(2)定义两类决策变量；式(3)为各变量的取值范围；式(4)约束订单j最优交货期的取值范围；式(5)计算完工时间大于交货期时的拖期；式(6)约束每个被接受的订单都分配至序列中的一个位置；式(7)约束任一订单的加工必须且仅能在该工序对应的机器上完成一次；式(8)计算工作天数。

预制构件6道工序的完成时间可由式(9)～式(13)得到。其中式(9)为传统流水车间订单加工的累计完成时间，即订单某道工序的完工时间等于其开始时间与处理时间之和；式(10)为在传统流水车间基础上，预制构件八小时工作制且不可加班约束条件下，第1,2,5,6道工序的完工时间。

浇筑(第3道工序)为不可间断工序且需顺序执行，因此若不能在包括加班的时间段内完成，则需推迟到下一个工作日进行。式(11)是在传统流水车间基础上，考虑预制构件八小时工作制且可加班的条件下，第3道工序的完工时间。

蒸汽养护为不可间断工序且可多个订单并行加工，需12 h不间断处理，因此存在两种情况：①养护过程可在包括加班的时间段内完成；②养护过程在夜间完成，其完成时间视为下一个工作日的开始时间。式(12)为传统流水车间的完成时间；式(13)为在传统流水车间基础上，考虑预制构件八小时工作制且可加班的条件下，第4道工序的完工时间。

本文首先给出固定调度排序下的最优交货期配置性质和最优交货期配置策略，然后给出集成交货期配置策略的混合迭代贪婪算法(Hybrid Iterated Greedy algorithm, HIG)。最后通过与枚举法的计算结果对比，分析了基于问题特征提出的知识结构对集成算法的影响，进而验证了最优配置策略的有效性。

2 交货期配置策略

针对该问题，在给定调度序列的情况下可以得到如下性质：

算法1固定排序情况订单接受与交货期指派伪代码。

输入：算例数据和算法参数。

1 Set Π←(π1,π2,…,πj,…,πJ)

2 Set ΠA=Φ,ΠR=Φ

3 for all j:=1 to J do

4 Compute the completion time of order πj

5 If Cπj

6 accept order πj,ΠA:=ΠA∪{πj}

7 else

8 reject order πj,ΠR:=ΠR∪{πj}

9 recompute Cπj+1,…,CπJ

10 end if

11 end for

12 for all orders πj∈ΠA

13 If γπj=0, then

18 else

21 end if

22 end for

3 混合迭代贪婪算法

因为有关IDOS_PPE的研究至今未见报道，而传统的预制构件生产调度[2-5]或流水车间调度的研究一般仅限于对机器上的工件排序进行单一决策，所以其调度算法很难直接应用于IDOS_PPE问题，需要根据问题特点设计特定算法。本章通过集成启发式初始化方法、最优交货期配置策略、多种邻域结构和破坏—构造机制，提出一种有效的混合IG搜索框架，其算法伪代码如算法2所示。该算法框架的特点在于可以根据给定调度，结合最优交货期性质，快速给出最优交货期，从而提高目标函数的评价效率，同时通过集成启发式、邻域搜索和破坏—构造机制有效改进问题求解质量。基于该框架，结合不同的邻域搜索方式，提出4种HIG(HIG_VNA，HIG_LS1，HIG_LS2，HIG_LS3)。因为传统预制构件生产调度问题通常采用GA[2-5]求解，所以在验证知识结构(性质1～性质3)有效性的基础上，还设计了基于集成问题知识的混合GA框架。基于该框架，结合不同的邻域搜索方式，提出两种混合GA与HIG进行对比，详见4.2.2节。下面具体介绍编码方式、初始化、局部搜索和破坏—构造等重要算法组成。

算法2IG算法伪代码。

输入：算例数据和算法参数。

输出：最佳解Π*和对应的目标函数值TNR(Π*)。

1 Π0←GenerateInitialSolutionby NEH-based heuristic;

2 Π*←LS(Π0)

3 repeat

4 Πp←Destruction(Π*)

5 Π′←Construction(Πp)

6 Π′←LS(Π′)

7 Π*←AcceptanceCriterion(Π*,Π′)

8 until termination condition is met

9 return Π*,TNR(Π*)

3.1 编码方式

将HIG中J个订单的调度序列Π设置为一个1×J向量，按照订单的排列顺序从左至右进行生产加工，对于订单被拒而导致的订单数量小于J的序列,用0填充以满足向量的完整性。

3.2 初始化

采用构造启发式算法进行初始化，得到质量较好解。首先将一批订单中每个订单6道工序的总时间按非递增顺序排列，选择两个时间最少的订单作为集合Π1，剩余订单组成集合Π2。将Π2中的每个订单插入使TNR最大的Π1中，保存并更新当前最好解。

3.3 局部搜索

为提高算法的全局搜索能力，防止算法陷入局部最优，设计了4种邻域搜索方法，进而给出4种混合迭代搜索算法。

(1)LS1(基于Swap_all操作) 从调度序列Π=(π1,π2,…,πj,…,πk,…,πJ)中按顺序依次交换(π1,π2),(π1,π3),…,(π1,πJ),…,(π2,π3),…,(π2,πJ),…,(πJ-1,πJ)，保留并更新当前最好解。

(2)LS2(基于Insert操作) 即在序列Π*中每次随机选择一个之前未被选择的订单插入剩余订单的所有位置，保留并更新当前最好解。

(3)LS3(基于Swap_double和Insert操作) 通过调整两种邻域结构的比例，按照一定概率对Swap_double和Insert两种邻域结构进行选择。其中Swap_double操作，即从一个完整序列Π=(π1,π2,…,πj,…,πk,…,πJ)中随机选择两个不同位置的订单πj和πk进行交换，形成新序列Π*=(π1,π2,…,πk,…,πj,…,πJ)。

(4)变邻域上升搜索策略(Variable Neighborhood Ascend, VNA)k=1表示运用Swap_all操作，k=2表示运用Insert操作，伪代码如下：

算法3VNA。

输入：当前解Π,当前最佳解Π*。

输出：最佳解Π*和对应的目标值TNR(Π*)。

1 k=1

2 while k≤2 do

3 Π′:=LSk(Π)% LSk：using local search strategy k

4 If TNR(Π′)>TNR(Π)do

5 Π:=Π′

6 k:=1

7 else if

8 k:=k+1

9 end if

10 If TNR(Π)>TNR(Π*)do

11 Π*:=Π

12 break

13 end if

14 end while

15 return Π*,TNR(Π*)

3.4 破坏—构造阶段

在IG中，采用破坏与重新构造策略对最优解进行扰动，防止其陷入局部最优。从序列Π*中随机选择d个订单并从Π*中删除，然后按已选择的顺序将其添加到Πd中，最后将Πd中的每个订单逐步插入Π*，保留并更新当前最好解。

4 实验设计与结果分析

4.1 实验设计

所有实验均在Intel Core i7-9700，1.80 GHz CPU，8.00 G RAM，Win10 64位操作系统和MATLAB 2016a编程环境下编译运行。因为目前没有标准测试算例测试PPFSP(precast permutation flow shop scheduling problem),所以以Brandimarte[28]预制构件车间调度问题标准算例中的10种不同类型订单为基础，选取小、中、大规模订单，每种规模订单随机生成10组算例，算例中各道工序的生产数据如表1所示。

表1 各类型预制构件6道工序的实际生产数据[28]

通过田口方法调节算法参数，得到优化后的参数，如表2所示。

表2 算法参数说明

枚举法是在订单最优交货期不确定的情况下，通过逐个计算所有可选择的交货期来寻找最优NR。图2所示为γ在不同取值下通过枚举法计算得到的3种不同类型订单的目标值随交货期变化的趋势，其中横轴表示交货期，纵轴表示目标值。当γ过小时，如图2a～图2c所示，订单交货期越大，TNR越大，然而由于忽略了顾客满意度，不利于工厂长远发展；当γ过大时，如图2e和图2f所示，部分订单在交货期下均为零或负值，不符合实际生产要求。因此，最终选择γ=3。

4.2 结果分析

4.2.1 知识结构对算法的影响

为进一步说明所提知识结构(性质1～性质3)的有效性，将通过知识结构(性质1～性质3)配置交货期和采用枚举法计算交货期两种方法在充分的迭代次数下，从最大值、平均值和运算时间进行对比，结果如表3所示。两种对比算法(基于枚举法的HIG和基于问题特定知识的HIG)在相同规模算例下，计算结果的平均值与最大值的平均偏差率均小于0.16%，验证了用知识结构(性质1～性质3)设计求解规则的方法是可行且有效的。在算法效率方面，融入知识结构(性质1～性质3)的HIG算法在J= 20，30，50，70时，运行时间分别提高8.55%，9.88%，14.33%，16.10%。随着订单规模的增大，与基于枚举法的混合HIG相比，基于问题知识结构(性质1～性质3)的HIG在求解时间上的优势更为明显。因此，该知识结构能有效降低工厂因计算而产生的时间浪费，提高工厂的整体运行效率。

表3 基于知识结构和枚举法的HIG比较

续表3

4.2.2 算法性能对比分析

求解预制构件流水车间调度问题最常用的智能算法是GA[16-19]，由于传统GA具有全局搜索性强、收敛速度慢且易早熟的特点，针对每一代搜索到的最佳个体进行局部搜索，提出HGA_LS2和HGA_VNA算法作为HIG的对比算法。为进一步说明变邻域上升搜索策略VNA的优越性，对6种算法(HIG_VNA，HGA_LS1，HGA_LS2，HIG_LS3，HGA_LS2HGA_VNA)进行比较。由图3可知，由于并行结构的优越性和特殊性，所有算法均快速收敛。其中，HIG_LS1算法的收敛速度最快，但求解质量较差，算法易陷入局部最优；HIG_VNA算法的收敛速度仅次于HIG_LS1。在所有算例中,无论解的质量还是算法的收敛精度和稳定性，6种算法中HIG_VNA算法解的质量在各规模算例中均为最好。

为比较HIG_VNA算法的性能，对不同规模的90个算例进行测试，分别用6种算法求解。为公平比较，对每个订单规模为J的测试算例独立运行10次，停止准则设置为最大运行时间(J·6/10) s。表4所示为各算法在不同规模算例下最大值和平均值的相对偏差率，图4所示为6种算法的平均偏差率ARPD，图5所示为不同规模算例下的平均值与标准差的误差棒。本文采用平均相对偏差率ARPD评估算法整体性能：

表4 各算法在不同规模算例下最大值和平均值的相对偏差率

续表4

l=1，…，L；

(14)

(15)

在6种算法中，HIG_VNA在所有算例上的最大值和平均值均最为优异，HIG_LS2次之，HIG_LS3表现最差，由此表明HIG_VNA在求解预制构件OAS问题时具有相对较好的性能。与HIG_Insert相比，HIG_VNA在J=20,30,50,70算例上，平均值的ARPD分别平均提升0.3%，1.16%，1.12%，1.20%，由此可知VNA变邻域结构在求解中大规模问题上的优势更加明显。与HGA_VNA相比，HIG_VNA在J=20,30,50,70算例上，最大值的ARPD分别平均提升0.93%，1.27%，2.01%，1.40%，由此可知HIG更适于求解预制构件工期配置、OAS的集成优化问题。综上所述，因为HIG的破坏—构造机制保留了全局搜索能力，独特的变邻域结构VNA进一步提高了算法的局部寻优能力，所以HIG_VNA算法具有优秀的寻优能力。

由图4可见，对于所有算例，HIG_VNA的标准差比HGA_VNA更小，说明HIG_VNA具有更好的鲁棒性，算法性更稳定。在J=20算例中，HGA_VNA的3个算例、HGA_LS2的4个算例，HIG_LS2的7个算例找到了当前最好解，HIG_VNA找到全部当前最好解，主要原因是小规模算例中各算法搜到全局最优解的概率较大。

5 结束语

为克服预制构件工期紧张和生产能力不足的问题，本文以最大化总净利润为目标，针对IDOS_PPE问题建立了混合整数非线性数学规划模型。鉴于该问题的复杂性，首先给出固定调度排序下交货期的最优配置，在此基础上，通过集成问题特定知识、快速启发式方法、VNA变邻域结构和破坏—构造机制，提出一种有效的混合迭代贪婪搜索框架用以同时确定最优交货期、可接受的订单和调度排序。计算结果显示，该算法在各种订单规模下均显示出较好的求解速度和求解质量，可为预制构件生产企业决策者提供很好的参考。

未来研究可考虑动态环境(如机器故障、紧急订单等突发事件)下的预制构件OAS问题。随着目前生产制造的全球化，为提高生产竞争力，很多预制构件由原来的单工厂制造模式转向分布式多工厂制造模式，在本文算法框架基础上研究分布式预制构件OAS问题将是很有意义的课题。