基于混合遗传禁忌算法的预制构件调度研究

陈竑翰 熊福力 王冬源 杜瑶 储梦伶

摘要：合理的调度方案可以显著改善预制构件生产效率，降低能耗并提高客户满意度。针对预制构件生产调度优化问题，传统的遗传算法往往优化效率较低。因此提出了一种新型的混合遗传禁忌算法，其中考虑了不同的编码方式以及初始种群的生成方式对算法的影响，首先通过遗传算法找到一个较好的可行解作为禁忌搜索算法的初始解，而后使用禁忌搜索算法在这个初始解的邻域内进行局部搜索寻优。最后设计实验验证了单层随机数编码方式优于多层随机数编码方式。并在基准时间下运行算法，实验结果表明，在工件数较少时禁忌搜索算法效果较好，而在工件数较多的情况下混合算法更优。

Abstract： A reasonable scheduling scheme can significantly improve the production efficiency of prefabricated components， reduce energy consumption and increase customer satisfaction. In order to optimize the production scheduling of prefabricated components， traditional genetic algorithms often have lower optimization efficiency. Therefore， a new type of hybrid genetic tabu algorithm is proposed， which takes into account the effects of different coding methods and initial population generation methods on the algorithm. First， a better feasible solution is found through the genetic algorithm as the initial solution of the tabu search algorithm. A tabu search algorithm is used to perform local search optimization in the neighborhood of this initial solution. Finally， design experiments verify that single-layer random number encoding is better than multi-layer random number encoding. The algorithm is run at the benchmark time. The experimental results show that the tabu search algorithm works well when the number of artifacts is small， and the hybrid algorithm is better when the number of artifacts is large.

關键词：预制构件;遗传算法;禁忌搜索算法;混合算法

Key words： precast component;genetic algorithm;tabu search algorithm;hybrid algorithm

中图分类号：TU756                                      文献标识码：A                                  文章编号：1006-4311（2020）17-0247-04

0  引言

装配式建筑是指在工厂预制，现场装配而成的建筑[1]，与传统现浇式施工和砌体结构相比，装配式建筑可以预先在预制场中进行生产，减少了环境污染和材料耗费。装配式建筑需求量不断增加，然而，目前我国装配式建筑并没有得到广泛的推广，主要有技术不完善和生产调度混乱两方面原因。在过去几十年中，不断有学者对预制构件的调度模型进行改进，Chan和Hu[2]提出了预制构件生产的流水车间排序模型（FSSM），将目标改为最小化延迟和提前的惩罚值。Leu等人[3]考虑了起重机和工厂工人的限制，以最小完工时间为目标。Li等人[4]提出了生产成本最低的调度模型，将生产资源约束整合到模型中。Wang等人[5]在原有的六道工序基础上，考虑了模具制造、预制件存储和运输三个过程。目前的研究已经发现预制构件的生产调度优化属于NP难题[6]，因此在解决预制构件的调度问题时，研究人员大多采用启发式算法，包括Gupta[7]、Palmer[8]等方法。Chan等人[9]通过将遗传算法与Palmer等算法进行比较，验证了遗传算法在流水车间排序模型上的优势。遗传算法虽然可以较好的解决预制构件的调度问题，但在应用上仍然存在局部搜索能力差的问题。本文提出了一种混合算法。最后将两种算法与混合算法的性能进行比较，验证了混合算法在预制构件调度优化问题上的优势。

1  预制构件调度模型

1.1 目标函数

在文中，考虑预制供应链环境下的预制过程主要由九个步骤组成：（S1）模具制造;（S2）模具组装;（S3）钢筋预埋;（S4）混凝土浇筑;（S5）蒸汽养护;（S6）脱模;（S7）整理精修;（S8）存储;（S9）运输。本文采用准时交付的目标，无论工件提前交付还是延期交付都会有相应的罚金，目标函数为最小化总罚金，如公式（1）所示。

（1）

其中，Cj为第j个工件的完工时间，dj为第j个工件的交付时间。？琢j为第j个工件的延期惩罚系数，？茁j为第j个工件的提前惩罚系数。

1.2 可中断工作完工时间

在预制构件的生产过程中，若在当天的工作时间内不能完成工件在该工作站的加工，可以暂时中断工作，并在下一个工作日的工作时间继续加工。完工时间的计算如式（2）-式（4）所示。

（2）

（3）

（4）

其中，HW是一个工作日的工作时间，HN是一个工作日的非工作时间，T是累积完工时间，D是工作天数，24D则代表一整个工作日，floor为一个向下取整函数。

1.3 不可中断工作完工时间

若某些工作在当天加班时间内也不能完成，则须等到下一段工作时间开始时再开始加工。完工时间的计算如式（5）所示。

（5）

其中，HA是允许的加班时间。

1.4 并行处理工作完工时间

并行处理的工作可以对多个工件可以同时进行加工，完工时间计算如式（6）-式（7）所示。

（6）

（7）

2  混合算法的设计

遗传算法（genetic algorithm，GA）是一种著名的启发式算法。其基本思想是通过编码技术模拟染色体，并通过群体中不同染色体交叉、变异的过程，淘汰弱势染色体，使群体不断进化，最终找到最优个体。其优点是具有很强的全局搜索能力，不容易陷入局部最优，缺点是在搜索过程中有可能忽视局部最优解。且容易到达收敛早熟，使搜索效果下降。禁忌搜索（Tabu Search，TS）最初是由Glover [10]提出的，是对局部搜索方法的一种扩展。其最大的特点是可以禁止重复性的工作，避免陷入局部最优解。优点是局部搜索能力较强，缺点是较为依赖初始解。本文通过结合两种算法的优点，并在GA的初始种群中加入NEH算法，提出了一种混合遗传禁忌算法。

2.1 用于預制构件调度的GA设计

2.1.1 编码方式

无论在使用遗传算法或者禁忌搜索算法来解决预制构件调度问题时，首先要进行的工作就是对工件的施工顺序进行编码。本文使用[0，1]之间的随机数编码来表示预制构件在各工作站的施工顺序，随机数越小优先级越高。编码工作根据各工作站工件顺序是否相同又分为单层编码和多层编码。

多层随机数编码使用一个矩阵对施工顺序进行编码。矩阵的一行代表一个工作站的施工顺序，有多少工作站矩阵就有多少行，矩阵的列数代表预制构件的数量，如图1所示。工作站的流水顺序为：工作站1→工作站2→工作站3→工作站4。其中，工作站1的施工顺序为：（2，5，1，3，6，4）;工作站2的施工顺序为（4，1，6，2，5，3）;工作站3的施工顺序为（1，5，6，4，3，2）;工作站4的施工顺序为（4，2，1，6，5，3）。在单层随机数编码中，由于工件在各个工作站上的施工顺序相同，所以用向量对各工作站的施工顺序进行编码。图2展示了6个预制构件的单层随机数编码方式。其中，所有工作站的施工顺序均为（3，4，5，1，2，6）。单层随机数编码和多层随机数编码各有利弊且搜索效果不同，需要设计实验并根据实验结果选择更适合预制构件调度的编码方式，本文后续小节使用遗传算法进行编码方式的选择与论证。

2.1.2 初始种群的生成

使用GA进行寻优的第一步是生成初始种群，传统的GA大多采用直接生成随机数作为初始种群。为了提高GA搜索效率，本文对初始种群生成方法进行改进。

①NEH算法预搜索。

在过去的研究中，NEH启发式算法被广泛认为是解决流水车间问题的一种较好的算法。NEH算法最大的优点是搜索时间较短，在本文中将NEH算法应用于预制构件的调度问题，用来生成GA的初始种群。使用NEH算法进行预搜索的实验结果如表1所示。

②工件紧急密度定义。

为了找到一些合理的解生成GA的初始种群，本文定义了工件的紧急密度，如式（8）所示。

（8）

式中，ED（？滋）是第？滋个工件的紧急程度，Tp（？滋）是第？滋个工件在各工序的加工时间之和，Td（？滋）是第？滋个工件的交付时间。紧急密度ED（？滋）越大，工件的加工优先级越高，排序越靠前。？棕1和？棕2分别是交付时间和加工时间的权重系数，？棕1越大说明加工时间对紧急程度的影响越大，？棕2越大说明交付时间对紧急程度的影响越大。

③初始种群生成方法。

本文中，GA的初始种群生成方法为：一个个体是NEH预搜索的解;九个个体是由定义的工件紧急程度得到的排序，？棕1从0.1到0.9，？棕2从0.9到0.1;其余个体由随机数生成，保证初始种群多样性。

2.1.3 种群的更新

生成初始种群后，在遗传过程中为了让种群不断向目标方向进化，每一代都需要对种群进行更新。种群的更新一般可以分为个体选择、染色体交叉、染色体变异三项操作。

在本文中使用轮盘赌方法作为选择算子。确定选择算子后，要对选中的两个个体进行染色体交叉操作。本文使用双点交叉随机产生两个点位，并交换两个点位之间的基因。交叉操作后，紧接着进行变异操作。本文使用的变异算子先随机选出两个基因，将后面的基因插入到前面基因的前方。

2.1.4 适应度计算

在预制构件调度问题中，可以用惩罚值来描述个体在自然界中的适应度。惩罚值越小，个体的适应度越高。本文中适应度使用目标函数的倒数。

2.2 用于预制构件调度的TS算法设计

本文用于预制构件调度的TS算法步骤如下：

①初始化。选择禁忌对象，设置禁忌长度，并清空禁忌表。