改进遗传—和声搜索算法求解海工装备制造车间调度问题

李敬花，闫恒山，杨博歆+，周青骅

(1.哈尔滨工程大学 机电工程学院，黑龙江 哈尔滨 150001；2.哈尔滨工程大学 船舶工程学院，黑龙江 哈尔滨 150001)

0 引言

海洋平台从零部件加工到组立、搭载，涉及数以万计的中间产品和相关装备，以我国第七代钻井平台“蓝鲸1号”为例，其钢板原料重达42 000 t，拥有27 354台设备及40 000多根管路，建造和进度管理难度较大[1]。制造车间是海工装备和中间产品的主要加工场所，车间调度的准确性直接影响到中间产品生产节拍甚至平台的完工交付时间，若建造进度与预期方案不符，将会给企业带来严重损失[2]。在实际应用层面，我国海工企业在车间调度环节大量依靠人工进行决策调度，效率和准确性低；在理论研究层面，目前鲜有学者对海工装备制造车间调度问题进行研究。因此，有必要对海工装备制造车间调度方法进行研究，采用智能化方法代替或辅助调度人员进行决策，提高车间调度准确性。虽然海工装备中间产品种类及加工工艺比较复杂，但是以各种型材和管件为代表的工件采取流水线加工形式，工艺流程明确且每道工序中存在若干台并行加工设备，属于混合流水车间调度问题(Hybrid Flow Shop Problem, HFSP)，本文主要研究此类构件的加工调度问题。

目前，针对HFSP的研究主要集中在机械、线缆、石化、玩具加工等行业。如陈超等[3]构建了带有阻塞重型机械加工车间HFSP模型，并运用遗传算法(Genetic Algorithm, GA)解决了某电信通信塔制造厂实例问题；汪和平等[4]采用改进初始解的NSGA-Ⅲ对建筑工程项目预制构件的生产调度问题进行了优化；王春等[5]针对以某玩具厂工模车间调度问题，引入虚拟工序和虚拟工时概念，并使用混合调度策略进行了实例验证；贾叶玲等[6]设计了一种改进遗传算法，解决了某船类零件制造企业混合流水车间环境下的成套订单问题；鲁佳俊等[7]提出一种基于果蝇优化算法的求解框架，解决了船舶管加工车间多目标生产调度问题。总体而言，目前缺少关于海工装备制造车间调度问题的研究，其原因主要有两方面：①海工装备制造属于大型结构与设备制造行业，自动化和标准化程度低，应用场景有限；②与常规的HFSP相比，海工装备制造车间调度问题具有约束条件较多且复杂度大的特点，具体表现为：

(1)采取准时制生产方式(Just In Time, JIT)，加工和完工时间具有不确定性；

(2)工件在相邻工序之间的转移时间不可忽略；

(3)重点考虑实际完工时间与计划完工时间的吻合程度而非最早完工时间；

(4)每台设备对不同工件加工速度不同，属于不相关并行机；

(5)部分工件需要在特定的设备上完成加工。

文献研究表明，目前多数针对HFSP的研究只是部分考虑了上述约束条件。如FATTAHI等[8]在研究中考虑了工件装配时间影响，但其将加工时间预设为确定值，并未考虑工期不确定性因素；ÖZTOP等[9]在建立HFSP模型时考虑了能源消耗和环境影响，LU等[10]考虑了车间噪声污染因素，提出一种嵌入了节能/降噪策略的HFSP模型，但是两者均未考虑工件转移时间影响；WANG等[11]研究了考虑设备动态调整操作的HFSP，但其假定加工设备是完全柔性的，并未考虑特定加工设备约束;袁庆欣等[12]研究了带有限缓冲区的HFSP，并考虑了工件运输时间约束；XING等[13]研究了考虑能耗和设备维护的HFSP，但两者均以最小化最大完工时间为工期优化目标，未考虑提前和拖期影响;NABLI[14]等研究了存在特定设备约束的两阶段HFSP，但并未考虑其他因素影响。与常规问题不同，海工装备制造车间调度需要综合考虑上述所有约束条件进行建模和求解，属于FHFSP-UPM&SM(fuzzy hybrid flow shop problem with unrelated parallel machine and specific machine)问题，其复杂度和求解难度更大。

HFSP是一类NP-hard组合优化问题，遗传算法(GA)因其具有的交叉、变异等离散组合操作而广泛应用于车间调度问题的求解。遗传算法虽然并行搜索能力好、健壮性强，但也存在局部搜索能力不强、容易陷入局部最优的缺陷，因此现有研究大多将其与其他方法相结合以提高求解效果。如ZHAO等[15]设计了一种基于并行顺序移动和可变变异概率的改进遗传算法，用于求解HFSP，提高了算法收敛速度；于蒙等[16]将粒子群算法与GA结合，形成GA-PSO混合算法，提高了算法搜索效率；轩华等[17]针对可重入HFSP，在标准GA基础上使用NEH启发式算法产生工件初始加工顺序，提高了解的质量。

和声搜索(Harmony Search, HS)模拟了乐队中乐师凭借记忆反复调整乐器音调，最终使音调达到稳定谐和状态的过程，其利用个体局部信息和群体全局信息指导算法进行搜索，通用性好且与其他算法结合可以有效改善算法整体的收敛性[18]。由于其操作简单，被应用到多个领域当中[19]。在车间调度领域，包云等[20]提出一种融入了和声搜索的混合遗传算法，用于求解阻塞流水车间调度问题；吴龙成等[21]针对硫化车间调度过程中机台利用率及生产效率低的问题，提出一种改进离散和声搜索算法，对最大完工时间进行了优化；向双玲等[22]对新和声产生方式进行了改进，提出了改进和声搜索算法并应用到柔性作业车间问题求解过程中。由于本文采用矩阵编码方式比常规的实数串编码更为复杂，若在GA基础上融入其他方法，如粒子群算法、变邻域搜索等，会大幅增加算法复杂度，因此使用和声搜索算法以避免由算法整体复杂度过大而导致的求解效率低下问题。

综上，本文主要工作以及创新点包括：

(1)模型方面 同时考虑模糊时间、工件转移时间、不相关并行机、特定加工设备等多个约束，以交货期与完工时间吻合度为优化目标构建了海工装备制造车间调度模型。

(2)算法改进方面 使用NSlope启发式算法代替随机方法进行种群初始化，以改善初始种群质量；采用基于线性排序和精英保留策略的选择算子来克服轮盘赌策略容易早熟的弊端；采用基于工件索引的循环交叉和基于工序的多点交叉两种算子进行基因交换，并引入禁忌搜索策略以保证种群基因的充分交流；基于自适应变异概率，使用多点替换变异和单点逆转变异两种算子使算法后期跳出局部最优，最终形成改进遗传—和声搜索算法，用于海工装备制造车间调度问题求解。

1 带有模糊时间和特定设备约束的HFSP 模型建立

1.1 模型假设

(1)所有设备在零时刻均处于可用状态；

(2)任一工件必须遍历所有工序；

(3)同一台设备的两个相邻待加工工件之间不存在等待时间；

(4)不考虑阻塞，工件完工后可立即离开当前设备；

(5)不考虑设备损坏、工件插入等干扰事件，视为静态调度过程。

1.2 附加条件及约束

1.2.1 模糊加工/转移/交货时间

海工装备中间产品的加工时间、转移时间以及交货期都不是确定值，因此本文采用三角模糊数(Triangular Fuzzy Number, TFN)对上述3种时间参数进行描述。另外，为了对加工时间和转移时间进行运算，需要定义TFN的运算规则。现假设有一对TFN:p1=(a1,b1,c1)、p2=(a2,b2,c2)用来表示模糊完工时间，则a,b,c分别表示最早完工时间、期望完工时间以及最晚完工时间，其运算规则及作用如表1所示。

表1 三角模糊数运算规则及其作用

1.2.2 不相关并行机与特定加工设备约束

根据HFSP每道工序并行机类型的差异，可分为同速并型机(Identical Parallel Machine, IPM)、异速并行机(uniform parallel machine)和不相关并行机(Unrelated Parallel Machine, UPM)三种[23]。本文问题模型中的加工设备均为不相关并行机，即同一台设备对不同工件的加工时间均不同，因此工件选择不同的加工设备均会对调度结果产生影响，相比另外两类问题，解空间和寻优难度更大。

在经典的HFSP中，工件在某道工序内可以任意选择加工设备，而在海工装备中间产品制造过程中，会存在部分对加工精度、质量等有特殊要求的工件，此类工件须使用特定设备(Specific Machine, SM)进行加工，因此需要在模型建立阶段引入相应的特定加工设备约束条件，使模型符合实际加工要求。尽管特定加工设备约束会使问题的解空间减小，但算法每一步寻优操作产生的结果都必须满足该条件，因此对算法设计和约束处理提出了更高的要求。

1.3 FHFSP-UPM&SM模型

模型相关参数含义及说明如表2所示。

表2 模型参数定义及说明

由于海工装备制造车间调度的目的是使中间产品完工时间和计划交货时间吻合度最高，本文以模糊加工时间对模糊交货期的“一致指数(Agreement Index, AI)”[24]作为优化目标。FHFSP-UPM&SM数学模型如下：

(1)

s.t.

(2)

j=1,2,…,w,k∈kj;

(3)

lk=1,2,…,hk;

(4)

j=1,2,…,w;

(5)

i1,i2=1,2,…,n,j=1,2,…,w且i1≠i2,

k∈kj,r=l+1,A=+∞;

(6)

j=1,2,…,w-1,r=j+1;

(7)

(8)

2 改进遗传—和声搜索算法

基于遗传算法以及和声搜索算法的优点，本文将两者结合，利用遗传算法进行全局寻优，利用和声搜索进行局部强化寻优。改进遗传—和声搜索算法(Improved GA Harmony Search algorithm, IGA-HS)算法整体流程如图2所示。

IGA-HS算法具体步骤如下：

步骤1设置参数。包括种群规模、交叉概率、变异概率、和声搜索相关参数、停止准则等。

步骤2使用NSlope算法生成初始种群。

步骤3计算个体适应度值，根据适应度值对个体进行升序排列，并对个体逐一编号。

步骤4选择操作。根据线性排序策略选出下一代种群。

步骤5交叉操作。根据交叉概率以及禁忌搜索策略，分别执行循环行交叉和多点列交叉。

步骤6变异操作。根据变异概率选择种群中的个体，并随机选择工序和机器，分别进行重新生成和列表逆转操作。

步骤7和声搜索。对当前种群进行若干次和声搜索操作，用适应度值更高的个体替换种群中的最劣个体。

步骤8判断是否满足算法停止准则，若是则停止，输出结果；否则，转步骤3。

下面给出算法详细设计过程。

2.1 编码解码方式

车间调度问题通常采用实数串编码、矩阵编码等形式。实数串编码虽然易于理解，但是其将加工信息分解为若干实数串，导致信息密度较低且操作繁琐。为了精确操控工件和加工机器的对应关系，本文采用矩阵编码形式。其中，矩阵行表示工件编号，列表示加工设备，用矩阵元素是否为空来表示工件是否在某一设备上加工，矩阵元素大小表示其在该设备上的加工顺位。以3道工序，每道工序3台设备，共5个工件的加工过程为例，个体编码如图3所示。

由上述规则可知，在第一道工序中，工件2和工件5使用1号设备加工，工件5加工顺位排在工件2之后；工件1和工件3使用2号设备加工，工件3加工顺位排在工件1之后；工件4使用3号设备加工。当矩阵元素相等时，可按照工件序号大小排序，由此可得到工件加工计划。

2.2 种群初始化方法

使用GA求解车间调度问题时，种群初始化操作主要有两种方式：随机生成和启发式方法[25]。目前，在车间调度算法研究中常用NEH(Nawaz, Enscore, Ham)算法来产生初始种群，以提高初始解的质量，本文使用Slope算法[26]进行种群初始化操作。Slope算法是解决置换流水作业问题的一种重要的启发式算法，该算法通过计算工件的倾斜值来为工件排序，主要原理为：若某工件在上游设备上的加工时间较短，而在下游设备上的加工时间较长，则其加工顺序应当靠前，反之加工顺序靠后。因此，当工件在上游设备上的加工时间较短而在下游设备上的加工时间较长，其倾斜值应该较大，反之倾斜值较小。本文基于上述原理，考虑交货时间因素，提出一种新的Slope算法(New Slope, NSlope)用来生成初始种群，具体步骤如下：

步骤1设定种群规模N。

步骤2从每道工序中随机选择一台设备，形成加工设备序列。根据序列中的m′台加工设备，计算工件的倾斜值来为工件降序排序，产生初始工件序列，一个工件i的倾斜值Ai定义为：

(9)

步骤3在第一道工序中，按照初始工件序列依次为工件随机选择加工设备；对于后续工序，按照工件到达的先后顺序为各个工件随机安排加工设备，最后为存在特定加工设备约束的工件选择设备，直到生成完整个体。

步骤4判断种群规模是否达到N，若是则结束；否则重复步骤2和步骤3，直到产生完整的初始种群NP。

2.3 基于线性排序和精英保留策略的选择算子改进

传统的轮盘赌选择策略存在个体适应度为零时不会被选择到下一代的缺陷，且当个体适应度值较大时容易被多次重复选择，进而导致种群多样性降低、算法快速早熟。因此，本文采用基于线性排序策略的选择算子来改善上述缺陷。具体选择方法为：首先根据适应度值进行升序排序，然后赋予个体相应的序号，最佳个体序号为N，其被选概率为Pmax；最差个体序号为1，被选概率为Pmin，则个体i被选概率

Pi=Pmin+(Pmax-Pmin)(i-1/N-1)。

(10)

另外，为防止种群中的精英个体在后续遗传操作中被破坏，采取精英保留策略对每代适应度值最大的个体进行保留，不参与后续遗传操作。

2.4 基于禁忌搜索策略的交叉算子改进

本文采用的矩阵编码存在行、列两个维度，因此需要分别进行行交叉和列交叉操作。

(1)基于工件索引的循环交叉(CX)

具体步骤为：

步骤1对于两个交叉个体工件索引A和B，A保持不变，将B乱序排列。

步骤2在A中随机选择一个起始点位，然后找到B中对应点位上的索引编号，再回到A中找到相同编号的索引的位置。

步骤3重复步骤2中的点位寻找方式，直到形成一个闭环，环中所有位置即为选中的交叉点位，最后将对应点位的基因互换。

操作方法如图4所示：

(2)基于工序的多点列交叉(MPX)

由于单列交叉在操作前后可能会出现同道工序内多台设备加工同一工件或者加工设备缺失的情况，需要频繁进行约束操作。因此本文采用多列交叉形式，对某道工序对应的所有列进行整体交叉，在保证交叉操作的同时减少约束处理步骤，提高算法执行效率，如图5所示。

同时，为了避免个体重复交叉以提高搜索效率，这里引入禁忌表。首先将种群中的个体进行编号，假设有两个个体A、B，A的禁忌表为listA，在完成交叉操作后将B的个体编号计入禁忌表listA=[B]，短期内使A与B不再进行交叉操作，禁忌表的长度可视种群规模而定，如NP/4。

2.5 变异算子改进

针对本文所使用的矩阵编码，算法在执行过程中随机采用以下两种变异算子，分别为：

(1)多点替换

多点变异操作首先随机选定一个工序，然后找出所有此工序对应的列并重新生成该工序内的工件和加工设备组合，替换原有工序，如图6所示。

(2)单点逆转

单点逆转变异操作包括行变异和列变异。首先确定变异位置，将该行(列)非空值按照编号顺序依次取出存入一个列表，并将列表内元素顺序逆序排列，最后按现有顺序依次放回矩阵对应位置，单点逆转操作如图7所示。

为了使算法后期能够跳出局部最优，采用一种自适应变异概率。首先设定最大变异概率Pmax及最小变异概率Pmin，并使变异概率随着遗传代数gen的变化逐渐递增，则个体i的变异概率Pi计算公式如下：

Pi=Pmin+(Pmax-Pmin)(gen/GEN+1)。

(11)

式中GEN为遗传总代数。

2.6 和声搜索

为增强算法的局部搜索能力，避免算法过早收敛，在选择、交叉、变异操作后进行和声搜索，对种群进行局部更新，和声搜索的具体步骤如下：

步骤1确定参数，包括记忆库选择概率(Harmony Memory Considering Rate, HMCR)、调整概率(Pitch Adjusting Size, PAR)和最大搜索次数Tmax。

步骤2以当前种群为和声记忆库，产生0～1间的随机数rand_1，若rand_1

步骤3产生0～1间的随机数rand_2，若rand_2

步骤4比较新个体适应度值fitness_new和种群中最差个体的适应度值fitness_bad，若fitness_new>fitness_bad，则用新个体代替种群最差个体，执行步骤5。随着遗传代数的增加，种群内个体会逐渐趋于一致。当所有个体都相同时，fitness_new可能会恒小于fitness_bad，进而陷入死循环。为避免这种情况，设置最大执行次数Lmax，当fitness_new连续Lmax次不大于fitness_bad时，直接用新个体代替种群最差个体，否则返回步骤2。

步骤5判断是否达到最大搜索次数Tmax，若是则结束，否则返回步骤2。

3 数值实验与分析

为验证所提算法的实用性及性能，依次进行以下3组数值实验：

(1)NSlope初始化方法测试 分别采用随机方法与NSlope启发式方法生成初始种群，并比较两种方法产生的初始种群的质量，进而验证NSlope启发式方法的有效性。

(2)算法性能对比测试 选用相同的车间调度测试算例，将IGA-HS算法与改进遗传变邻域搜索算法、混合粒子群遗传算法以及改进候鸟优化算法进行比较，进而评价IGA-HS算法的性能。

(3)车间实例数据测试 采用IGA-HS以及另外三种对照方法对车间实例数据进行调度，为评价IGA-HS算法的实用性提供依据。

3.1 实验1：NSlope初始化方法测试

为测试NSlope启发式算法对初始种群质量的影响，进行种群初始化对比实验。实验1以NADERIA等[27]提出的“n20k4m3422”为基准，生成不相关并行机算例进行实验，另外设置交货期窗口以保证与本文FHFSP-UPM&SM模型的一致性。其中n表示工件数量，k表示表示工序数量，m表示每道工序的加工设备数量，“n20k4m3244”表示该问题为20个工件，共4道工序，每道工序的设备数依次为3、2、4、4。将NSlope启发式算法和随机方法两种初始化方法进行对比，进行20次种群生成实验，结果如表3所示。

表3 NSlope启发式算法对比实验结果

表3中：R表示随机方法，N表示NSlope启发式方法；ave表示种群加权AI平均值，best表示种群加权AI最佳值的平均值。由实验1结果可知，在20次实验中，R_ave的平均值为0.022，N_ave的平均值为0.032，则NSlope启发式算法产生的初始解平均值的整体质量更高；R_best的平均值为0.275，N_best的平均值为0.331，则NSlope启发式算法产生的初始解最佳值的整体质量更高。因此，相比随机策略，NSlope启发式算法在初始种群初始化方面更有优势。

3.2 实验2：算法性能对比测试

表6 基于n20k4算例的4种算法测试结果

在表6的10组算例中，IGA-HS求得了5组最好解，3项指标在10组算例下的平均值分别为：0.19、27.5%、27.9%；IGA-VNS求得了2组最好解，3项指标在10组算例下的平均值分别为：0.14、33.4%、35.5%；IPSO-GA求得了1组最好解，3项指标在10组算例下的平均值分别为：0.12、40.5%、35.2%，MBO求得了2组最好解，3项指标在10组算例下的平均值分别为：0.14、41.0%、29.6%。因此,在该组算例下，IGA-HS算法的性能表现优于其余3种算法。

表7 基于n20k8算例的4种算法测试结果

在表7的10组算例中，IGA-HS求得了7组最好解，3项指标在10组算例下的平均值分别为：0.20、26.5%、28.8%；IGA-VNS求得了2组最好解，3项指标在10组算例下的平均值分别为：0.14、26.8%、41.2%；IPSO-GA求得了0组最好解，3项指标在10组算例下的平均值分别为：0.09、36.3%、42.1%，MBO求得了1组最好解，3项指标在10组算例下的平均值分别为：0.12、36.7%、33.2%。因此,在该组算例下，IGA-HS算法的性能表现优于其余3种算法。

表8 基于n50k4算例的4种算法测试结果

续表8

在表8的10组算例中，IGA-HS求得了10组最好解，3项指标在10组算例下的平均值分别为：0.15、32.5%、30.4%；IGA-VNS求得了0组最好解，3项指标在10组算例下的平均值分别为：0.07、30.4%、53.1%；IPSO-GA求得了0组最好解，3项指标在10组算例下的平均值分别为：0.07、58.3%、20.2%；MBO求得了0组最好解，3项指标在10组算例下的平均值分别为：0.08、44.5%、33.5%。因此,在该组算例下，IGA-HS算法的性能表现高于其余3种算法。

若用工序数与工件数的乘积表示3组算例的复杂程度，则4种方法求得的加权AI、提前率adv与延误率del之和随算例复杂程度的变化情况如图8所示。由图8可知，4种方法得到的加权AI(实线部分)总体上呈现递减趋势，提前率adv与延误率del之和(虚线部分)总体上呈现递增趋势，表明随着算例复杂程度的增加，算法求解效果有不同程度的降低；GA-VNS、IPS-GA和MBO曲线较为接近，三者求解效果相当；而IGA-HS对应曲线与另外3种方法有明显区分且结果更优，因此求解效果最好。

3.3 实验3：车间实例数据测试

为进一步测试算法对实际调度案例的求解效果，实验3使用某海工企业管件加工车间实例数据进行测试，共包含10个工件，5道工序，16台加工设备。工件在不同设备上的加工时间信息如表4所示(单位：min)，表中空缺部分表示该工件存在特定加工设备约束。工件在相邻工序之间的转移时间如图9所示，圆内包含3个数字，分别对应三角模糊数的3个分量，表示工件从行所在设备向列所在设备转移时所消耗的时间(单位：min)，转移方向用箭头标出。

表4 工件加工时间表

续表4

对照方法仍然采用实验2中的3种方法，分别运行20次，统计加权AI、提前数、延误数3项指标的最佳值、最差值和平均值。IGA-HS主要参数设置如表5所示，实验结果如表6所示。

表5 算法主要参数设置

表6 实例数据测试结果

续表6

由实验结果可知，IGA-HS产生的加权AI值在最佳、最差和平均值3项指标上的表现优于另外3种对照方法。将4种方法的20次寻优曲线进行平均，结果如图10所示。

由寻优曲线变化情况可知，在初始阶段IGA-HS生成的解的质量更高，这是因为IGA-HS使用NSlope算法生成初始解，可以避免产生大量劣质个体；IGA-VNS与IPS-GA寻优曲线在160代左右不再继续递增，曲线平稳后适应度值接近，因此两者表现相当；MBO在前期收敛速度较快，但是在50代后，其曲线递增趋势明显减缓，达到平稳后的适应度值低于另外3种方法，因此表现最差；在160代以后，IGA-HS的适应度值则仍保持递增趋势，并在180代左右出现明显递增，原因是IGA-HS使用自适应变异概率，结合HS进行局部强化搜索，增强了算法跳出局部最优解的能力，因此能够搜索到适应度更高的解。如图11所示为实例数据调度方案的模糊甘特图。

综上可知，本文提出的IGA-HS算法在求解海工装备制造车间调度问题上具有良好的效果，IGA-HS算法的整体求解效果优于另外3种对照算法。首先，NSlope启发式算法产生了高质量的初始种群；其次，对选择、交叉、变异算子的改进提高了算法的收敛性质；最后，使用和声搜索算法进行局部强化搜索，使IGA-HS具备良好的局部搜索能力，提高了算法的整体性能。

4 结束语

本文主要研究了带有工件转移时间、特定加工设备约束、模糊加工时间和模糊交货期的海工装备制造车间调度问题。以最大加权平均一致指数为目标函数，建立了FHFSP-UPM&SM模型，并设计了一种改进遗传和声搜索算法。算法初始阶段采用NSlope启发式算法生成具有较高质量的初始种群；算法选择阶段采用线性排序策略和精英保留策略，用以改善算法收敛性质，提高算法搜索效率；算法交叉阶段针对矩阵编码的两个维度，采用两种交叉算子提高交叉性能，禁忌搜索策略能够保证个体交叉更为充分；算法变异阶段设计了两种变异算子，结合自适应变异概率，增强了算法跳出局部最优的能力。通过数值实验对算法性能进行了测试，验证了本文所提方法在求解海工装备制造车间调度问题上的有效性。

在后续研究过程中，拟考虑将工件转移时间视作广义的物流配送时间，将物流配送问题与车间调度问题相结合，进一步提高研究的实用性。