基于混合多目标遗传算法的柔性作业车间调度问题研究*

宋昌兴，阮景奎，王 宸

(湖北汽车工业学院 机械工程学院，湖北 十堰 442002)

0 引 言

车间生产调度是一种有效的调度方法与优化技术，企业在生产加工制造过程中对生产计划的合理编排，对提升企业生产效率、资源利用率、降低成本等起着关键作用。柔性作业车间调度问题(fle-xible job scheduling problem，FJSP)相比传统的作业车间调度问题引入了新的决策内容，包括对两个子问题的求解：一是为每道工序选择合适的机器，二是确定工序在机器上的起止加工时间，是更复杂的NP-hard问题[1]。

经过近30年的探索，FJSP的研究取得了丰硕的成果。以遗传算法[2]、粒子群算法[3]、禁忌搜索算法[4]、模拟退火算法[5]等为代表的元启发式算法，在实际调度问题中都得到了成功的应用。

随着研究的深入，更加符合生产实际的多目标柔性作业车间调度(multi-objective FJSP，MO-FJSP)成为目前亟待解决的问题，近年来许多新算法的不断涌现，也为解决MO-FJSP提供了更多的选择方案。孟冠军等[6]提出了混合人工蜂群算法，在雇佣蜂、跟随蜂、侦查蜂3个阶段分别采用了不同的搜索方式，并引入禁忌搜索算法提升了获得最优解的概率;王英彦等[7]提出了改进的人工免疫算法，采用了模拟退火算法的Metropolis准则，在保证了种群多样性的同时加快搜索效率；王思涵等[8]提出了改进的鲸鱼群算法，采用了协同搜索机制扩大鲸鱼个体的搜索范围，同时引入了变邻域搜索算法，提高了种群全局及局部搜索能力；曹磊等[9]提出了变邻域杂草优化算法，建立了具有Dejong学习效应的调度模型，在迭代后期引入了N1、N2、N3 3种邻域结构的变邻域搜索算法，并通过实验对算法的有效性进行了验证。

近年来的研究表明，针对单一算法的不足，混合算法将两种及以上算法的特性进行互补，相比单一算法具有更优的适应性和鲁棒性，是研究和解决MO-FJSP的重要方向。

本文将在非支配排序遗传算法的基础上引入和声搜索算法(harmony search，HS)，提出一种混合多目标遗传算法(HMO-NSGA-II)，并通过实验证明所提算法的可行性、有效性和实用性。

1 多目标柔性作业车间调度问题

1.1 问题描述

FJSP可描述为：有n个工序顺序已知的工件J={J1,J2,…,Jn}和m台不同机器M={M1,M2,…,Mm}，其中工件Ji的每道工序Oij可在相应的可选机器集Mij中任意选择1台机器进行加工，且选择不同机器对应的加工时间可能不同。

在实际生产调度过程中，常会对多个不同的目标进行优化，如最大完工时间、生产成本、总拖期时间、机器总负荷、瓶颈机器负荷等。MO-FJSP的求解即在满足时间、资源等约束条件下，采用最优化方法合理解决机器分配和工序排列2个子问题，分配各工序在机器上加工的起止时间，并实现对多个给定性能指标的优化，最终得到1组非劣调度方案。

1.2 数学模型

本文选择以下3个具有实际应用价值的目标，以降低机器生产负荷、缩短加工产品完工时间，从而提高生产效率。

(1)最大完工时间最短：

f1=min(max(Ci))

(1)

(2)最大瓶颈机器负荷最小：

(2)

(3)最大机器负荷最小：

(3)

式中：Ci—工件Ji的完工时间；n—工件总数；ni—工件i的总工序数；m—机器总数；Pijk—工件i的第j道工序在机器k上的加工时间；Xijk—判断工件i的第j道工序是否在机器k上加工，是则取1，否则取0。

1.3 约束条件

一般的，在调度过程中MO-FJSP模型应满足以下约束条件[10，11]：

(1)所有设备在t0时刻均可用；

(2)不同工件的加工优先级相同，一旦开始加工便不可中断；

(3)同工件的不同工序之间，需满足工艺先后顺序约束，即：

Sij+PijkXijk≤Si(j+1)

(4)

(4)同时刻，同一台机器只能加工某工件的某一道工序，即：

Sij+Pijk≤Shl+L(1-yijhlk)

(5)

Cij≤Si(j+1)+L(1-yiji(j+1)k)

(6)

(5)同时刻，同一个工件的同一工序能且只能被一台机器加工，即：

(7)

式中：Sij—工件i的第j道工序开始加工的时间；Pijk—工件i的第j道工序在机器k上的加工时间；Xijk—判断工件i的第j道工序是否在机器k上加工，是则取1，否则取0；Si(j+1)—工件i的第j+1道工序开始加工的时间；Shl—工件h的第l道工序开始加工的时间；L—足够大的正数；yijhlk—判断在同机器k上，工件i的第j道工序较工件h的第l道工序是否先加工，若是值为1，否则为0；Cij为工件i的第j道工序停止加工的时间；yiji(j+1)k—在同机器k上，工件i的第j道工序较工件i的第j+1道工序是否先加工，若是值为1，否则为0。

2 混合多目标遗传算法设计

NSGA-II在求解MO-FJSP上应用广泛，但由于交叉、变异操作以及精英策略等自身的局限性，在求解收敛速度以及保持种群多样性等方面存在缺陷。和声搜索算法实现原理简单，易于与其他算法结合，在新解的产生上能够全面利用存在的解向量，有效保证了种群的多样性，但比较依赖好的初始解。

因此，本文以NSGA-II为主体，把每代经过自适应交叉变异以及改进的精英保留策略等操作所得到的种群精英库，作为和声搜索算法的和声记忆库，并通过改进的和声搜索算法提高精英库种群质量，加快引导种群向pareto最优前沿收敛。

2.1 编码与解码

针对求解MO-FJSP，本文采用基于机器、工序双层编码的方式，以对应机器分配和工序排列2个子问题。以一个4×5的部分柔性作业车间调度问题(partial FJSP，P-FJSP)为例，工件1有3道工序，工件2-4分别有2道工序，各工件每道工序对应的可选机器集Mij为5台机器中的部分机器。编码的长度等于各加工工件工序总数之和，工序编码部分为所有工序的一种排列，数字代表工件号，出现的次数代表相应工序，接着为每道工序从可选机器集中分配加工机器组成机器编码。

基于机器、工序的双层编码过程如图1所示。

图1 基于机器、工序的双层编码过程

解码采用插入式贪婪解码方法，将个体编码转换为调度甘特图。

加工起始时间计算如下式所示：

ta=max(Ci(j-1),TSkr)

(8)

ta+Pijk≤TEkr

(9)

tb=max(Ci(j-1),LMk)

(10)

式中：ta—工序的加工起始时间；Ci(j-1)—工件i的第j-1道工序停止加工的时间；TSkr—机器k上第r个空闲时间段的开始时间；Pijk—工件i的第j道工序在机器k上的加工时间；TEkr—机器k上第r个空闲时间段的结束时间；tb—工序的加工起始时间；LMk—机器k上最后一道工序的结束时间。

具体步骤流程如下：

(1)找到当前同机器上所有加工空闲时间段[TSkr,TEkr]；

(2)根据式(8)计算各工序Oij的加工起始时间ta；

(3)根据式(9)判断当前工序能否在同机器上向前插入空闲间隙，若能则按起始时间ta进行加工，若不能则根据式(10)按tb进行加工。

2.2 种群初始化

为提高种群初始解的质量，本文采用全局选择与快速选择相结合的方式，快速得到较好的初始解：

(1)通过全局选择将工序尽可能安排到当前累积加工负荷最小的加工机器上，以保证加工机器负荷平衡；

(2)通过快速选择，为各工序按概率随机分配或分配到加工该工序用时最短的机器上，以扩大搜索范围保证初始种群的多样性。

对应两种方式的种群产生比例分别设置为0.4、0.6。

2.3 交叉与变异

2.3.1 混合交叉方案

工序编码部分采用张超勇等[12]提出的IPOX交叉。为适应2.1节中的编码策略，在交叉过程中机器编码也做出相应的变换。

基于工序编码的IPOX交叉如图2所示。

图2 基于工序编码的IPOX交叉

机器编码部分采用改进的MPX交叉。首先从工件集J中随机选取若干个工件如：{J2,J3}并记录其出现的位置；接着分别将父代机器编码MF1、MF2中非记录位置基因放入子代机器编码MC1、MC2；最后交换MF1、MF2中记录位置的同工序机器基因并依次插入子代对应位置。

基于机器编码的改进MPX交叉如图3所示。

图3 基于机器编码的改进MPX交叉

2.3.2 混合变异方案

工序编码部分采用插入变异。随机选取2个位置点S1、S2，假设S1

基于工序编码的插入变异如图4所示。

图4 基于工序编码的插入变异

机器编码部分采用贪婪组合变异策略。随机产生一个位置点，一是在该道工序的可选机器集中随机选出一台不重复的机器，替换当前机器基因；二是在其可选集中选择当前负荷最小的机器，替换当前机器基因，两种方式比例设置为0.5、0.5。

基于机器编码的贪婪组合变异如图5所示。

图5 基于机器编码的贪婪组合变异

2.3.3 交叉、变异算子的自适应改进。

交叉、变异操作分别影响算法的全局、局部搜索性能。在种群进化前期，优秀解距离pareto最优前沿较远，为保证群体的参与性，笔者采用较大的交叉概率Pc，以提高全局搜索能力，加快种群进化过程；在种群进化中后期，种群中优秀解的数量居多，为防止算法陷入局部最优，笔者采用较大的变异概率Pm，以提高局部搜索能力。

交叉概率范围设置为(0.4，0.8)，变异概率范围设置为(0.01，0.2)，自适应算子计算公式如下：

(11)

Pm(i)=minPm+

(12)

式中：Pc(i)—第i代的交叉概率；Pm(i)—第i代的变异概率；gen—总迭代数；maxPc—最大交叉概率；minPc—最小交叉概率；maxPm—最大变异概率；minPm—最小变异概率。

2.4 精英策略

针对传统精英策略保持种群多样性能力差、易于收敛于局部最优等问题，本文对其进行了改进：

(1)对各等级非支配层上的个体进行拥挤度排序；

(2)为了保留尽可能多的精英解，将位于1级非支配层上的所有个体直接选入子代中，若其数量超过子代种群数量N的0.15倍，则按照拥挤度排序选择前0.15N个个体进入子代；

(3)对其他等级非支配层上的个体，分别按在种群大小为Np的合并种群中所占的比例，选取Ni个个体进入子代。

其中，每级非支配层个体数量选择函数如下：

(13)

式中：i—非支配层等级；Fi—第i级非支配层；Ni—从第i级非支配层Fi中选取的个体数量；|Fi|—第i级非支配层上的个体数；Np—合并种群的大小；N—子代种群的大小。

2.5 改进的和声搜索算法

标准和声搜索算法的核心在于新和声的产生以及和声记忆库的更新。为了更好地与HMO-NSGA-II相融合，本文做出了以下改进：

(1)将种群精英库与和声记忆库相结合，以解决HS依赖较好初始解的弊端，并采用改进的精英策略完成和声记忆库的更新；

(2)在新和声的产生上采用优秀片段保留以及基于关键路径的变邻域搜索策略。

对应标准HS中对音调高低进行升降微调的2种方式，具体方法如下：

(1)从和声记忆库中随机抽出一个和声，即：

(14)

式中：l—保留的优秀基因片段长度；lhs—和声的长度，即总工序数；index—该和声在和声记忆库中的非支配排序序号；HMS—和声记忆库的大小。

按该和声的优秀度选择保留优秀基因片段的长度l，对于剩余位置基因按1.3节中的约束条件随机补充。

(2)变邻域搜索采用2种邻域结构。对于工序的调整采用张国辉等[13]提出的改进的N5邻域结构，即分别交换关键块首块、尾块中块尾、块首的两相邻工序，其他关键块只交换块首及块尾的两相邻工序，若两相邻工序为同工件则不交换；对于机器的调整，在关键路径中随机选择一道工序，将其当前使用机器替换为可选集中加工时间最短的机器。

2.6 步骤流程

(1)设置迭代次数、交叉变异概率等初始化参数，采用2.2节中的方法生成包含N个个体的初始种群P0作为第一代父种群Pt，并对其进行非支配排序及拥挤度计算；

(2)通过二元锦标赛机制，随机选择Pt中的个体进行2.3节中的自适应混合交叉、变异操作，得到子代种群Qt；

(3)合并父代种群Pt和子代种群Qt得到新种群Rt，大小为Np。然后对Rt进行非支配排序并计算每个个体拥挤度大小，得到各级pareto非支配层F1,F2,…Fn；

(4)采用2.4节中改进的精英策略保留各级非支配层中的优秀个体，形成大小为N的新父代种群Pt′；

(5)将种群精英库作为HS的和声记忆库，用精英库父代种群Pt′初始化和声记忆库HM，和声记忆库大小HMS为N；

(6)产生一组随机数r1、r2，其中r1∈[1,HMS]、r2∈(0,1)；

(7)从和声记忆库HM中选择第r1条和声，并判断r2是否小于和声微调概率PAR，若成立则采用2.5节(1)中的和声优秀片段保留策略对选择的和声进行微调，否则采用2.5节(2)中的基于关键路径的变邻域搜索策略进行微调，得到新和声Xnew；

(9)判断迭代次数j是否达到最大，若是则跳转至下一步，否则迭代次数加一跳转至(6)进行下一轮循环；

(10)判断迭代次数i是否达到最大，若是则结束迭代得到一组非劣调度方案，否则迭代次数加一跳转至(2)进行下一轮循环。

HMO-NSGA-II流程框架如图6所示。

图6 HMO-NSGA-II流程框架

3 实验及结果分析

为验证本文提出的HMO-NSGA-II在MO-FJSP求解上的可行性、有效性和实用性，笔者选择通用国际标准算例和实际生产案例进行测试，其中，标准算例包括Kacem测试集[14](8x8(P-FJSP)、10x10(T-FJSP)、15x10(T-FJSP))和BRdata数据集[15](MK01-MK10)。

算法采用MATLAB R2018a编程，运行环境为：CPU Intel i7-4558U主频2.80 GHz，内存4 GB，Windows 7操作系统的个人笔记本电脑。

测试目标函数选用1.2节中的式(1～3)，HMO-NSGA-II参数设置为：总迭代次数，种群大小，交叉概率范围(0.4，0.8)，变异概率范围(0.01，0.2)，和声搜索算法迭代次数，和声记忆库微调概率。

具体步骤为：

(1)在BRdata数据集下，本文将NSGA-II与HMO-NSGA-II各运行20次后的非劣解按最大完工时间最小进行对比。

HMO-NSGA-II与NSGA-II对比结果如表1所示。

表1 HMO-NSGA-II与NSGA-II对比结果

从表1可以看出：相对于Brandimarte方法而言，两种算法都取得了较好的测试结果，但随着问题规模的增大，NSGA-II较HMO-NSGA-II求得非劣解的质量有所下降；在MK01问题上两者所得的值相同，但HMO-NSGA-II的均值及标准差均低于NSGA-II；在MK02-MK10问题上HMO-NSGA-II所得的非劣解均优于NSGA-II，且20次运算结果波动不大，在求解质量上表现出很好的稳定性。其中，以MK01问题为例，两算法某次运行结果的迭代过程及非劣解分布对比分析如下。

HMO-NSGA-II与NSGA-II求解MK01问题过程对比如图7所示。

图7 HMO-NSGA-II与NSGA-II求解MK01问题过程对比

从图7可以看出：在得到相同解的情况下HMO-NSGA-II能够稳定、快速的找到最优解，具有很好的收敛性；HMO-NSGA-II最终得到13个非支配解，NSGA-II最终得到8个非支配解，HMO-NSGAII得到的非支配解个数多、分布范围广且均匀，体现出较好的全局、局部搜索性能。

(2)在Kacem测试集下，本文将HMO-NSGA-II与孟冠军提出的混合人工蜂群算法(ABC+TS)、曹磊提出的变邻域杂草优化算法(IWO+VNS)、Kacem提出的局部逼近与控制遗传算法的混合算法(AL+CGA)、喻明让提出的离散粒子群算法(PDPSO)[16]的运行结果进行了对比。

各算法运行结果对比如表2所示。

从表2可以看出：在Kacem8×8问题上曹磊提出的IWO+VNS得到了更多的非劣解，但均未达到最优值；对于其余问题，与其他算法相比HMO-NSGA-II在求解精度上都可以达到最优值标准，在求得的非支配解个数上均不劣于其他算法。

表2 各算法运行结果对比

Kacem15×10问题调度甘特图如图8所示。

图8 Kacem15×10问题调度甘特图

(3)为进一步验证HMO-NSGA-II算法求解实际问题的实用性，本文选择某汽车线束生产企业的实际调度案例进行测试。汽车线束生产工艺流程包括下线、压接、内联、分装、总装等，以某个具有6条支路的线束产品为例，对应工艺流程中6条分装支路相当于6个工件，其中工件J1、J3、J4分别包含工序序号为1、2、3、4的4道工序，工件J2、J5、J6分别包含工序序号为1、2、4的3道工序，该产品产量为50根。

线束产品加工生产数据如表3所示。

表3 线束产品加工生产数据

根据表3中的实际生产数据，本文采用NSGA-II和HMO-NSGA-II进行调度求解，并将求解结果与传统的人工调度方法进行对比。

各调度方法求解实际问题的结果对比如表4所示。

表4 各调度方法求解实际问题的结果对比

从表4可以看出：人工调度方法较两种智能调度算法对人的依赖程度大，并且调度与生产加工所用时间长，调度效果比较差；HMO-NSGA-II相对于NSGA-II虽调度用时稍长，但在生产加工用时和非劣解个数的性能指标上优势明显，该汽车线束企业可根据实际情况，从所得非劣解集中选择合适的解用于指导生产。

汽车线束实际调度方案甘特图如图9所示。

图9 汽车线束实际调度方案甘特图

综上所述，本文提出的HMO-NSGA-II与单一算法相比求解精度高、收敛速度快，具有很好的全局、局部搜索能力；在测试选取的不同规模基准实例与实际生产案例上都取得了最优的结果，具有很好的适应性和鲁棒性。由此可以证明，HMO-NSGA-II用于求解MO-FJSP是可行、有效的，具有很好的实用价值。

4 结束语

(1)本文对NSGA-II的种群初始化、交叉变异方式、精英保留策略等进行了改进，有效保证了种群多样性，提高了算法的全局、局部搜索能力；

(2)以NSGA-II为主和声搜索算法为辅，充分结合两种算法的优点提出了混合多目标遗传算法HMO-NSGA-II，提高了求解质量并通过测试国际标准算例Kacem测试集、BRdata数据集和实际生产案例，验证了算法求解MO-FJSP的可行性和有效性，具有很好的实用价值；

(3)接下来，笔者将深入研究MO-FJSP自身特征领域，在不同目标需求下继续探索混合多目标遗传算法的改进策略，以不断完善、提高算法的求解质量和效率。