基于改进Jaya算法的柔性作业车间调度问题

连裕翔，张超勇+，孟磊磊，薛燕社，詹欣隆，吕 畅

(1.华中科技大学 数字制造装备与技术国家重点实验室，湖北 武汉 430074；2.聊城大学 计算机学院，山东 聊城 252059)

0 引言

自改革开放以来，我国制造业蒸蒸日上，同时也暴露了许多资源协调利用、信息管理方面的缺陷，显示出我国与国外在制造业水平之间的巨大差距，随着中国制造2025的提出，这些问题更加突出，为提高制造企业的精细化、自动化科学管理能力，以在激烈的全球竞争中立于不败之地，必须最大限度地利用现有资源，提高资源利用率，提升产品质量并缩短加工周期，在该过程中，生产调度显得十分重要。在制造企业生产中，科学合理的调度可以提高制造过程的生产率和生产设备利用率，缩短产品的生产周期，减少资源浪费。经典的作业车间调度问题(Job shop Scheduling Problem, JSP)是一种复杂的NP-hard组合优化问题，其中每个工件的工艺路线不同，每个工序在指定的机器上加工，每个机器只能处理一种操作类型。然而，在实际制造企业的生产过程中，一道工序的加工往往有多个机器可以选择，而且不同机器加工同一道工序的时间一般不同，该类问题属于扩展的JSP，即柔性作业车间调度问题(Flexible Job shop Scheduling Problem, FJSP)。与JSP相比，FJSP减少了加工机器选择约束，提高了工件加工的柔性，增大了搜索空间，是比JSP更复杂的NP-hard问题。

BRUCKER等[1]于1990年首先提出FJSP，并采用多项式图形算法解决该问题。目前，求解FJSP的方法主要分为精确算法和近似算法两类。精确算法包括数学建模、分支定界和整数规划法等，例如，GOMES等[2]提出一种用于FJSP的新的整数线性规划模型，并采用商业混合整数线性规划(Mixed Integer Linear Programming, MILP)软件解决该问题；ROSHANAEI等[3]为FJSP开发了两种新颖的MILP模型。精确算法虽然能够得到实例的最优解，但是无法在短时间得到中、大规模FJSP实例的解，因此研究者开始越来越关注近似算法，特别是元启发式算法，来求解FJSP。

元启发式算法分为群体智能算法和局部搜索算法，群体智能算法包括蚁群优化(Ant Colony Optimization, ACO)算法、粒子群优化(Particle Swarm Optimization, PSO)算法和人工蜂群(Artificial Bee Colony, ABC)算法等；局部搜索算法包括禁忌搜索(Tabu Search, TS)、模拟退火(Simulated Annealing, SA)、可变邻域搜索(Variable Neighborhood Search,VNS)等。WANG[4]提出一个有效的ACO算法解决FJSP，其中包括改进的信息素引导搜索和更新机制，以实现最优的全局搜索；LI等[5]为多目标FJSP提出基于Pareto的ABC算法；GAO等[6]提出一种具有新工作插入的FJSP两阶段ABC算法；NOUIRI等[7]研究了考虑机器故障约束的FJSP，提出两阶段PSO解决以制造期和稳定性为优化目标的问题；ZHANG等[8]提出一种改进的FJSP遗传算法，并取得良好的效果；DRISS等[9]提出一种遗传算法，该算法采用新的染色体表示形式以及一些不同的FJSP交叉和突变策略；LI等[10]提出一种混合算法求解FJSP，采用GA进行全局搜索，TS进行局部搜索，对基准案例获取了新解；NOURI[11]提出一种完整的多智能体模型，该模型集成了基于邻域的遗传算法和局部搜索技术，以提高解决方案的质量；赵诗奎[12]提出一种新的邻域结构，在同机器工序移动N7邻域的基础上扩大邻域，采用遗传算法作为全局搜索，通过基准实例验证算法的有效性。通过上述研究可以看出，群体智能算法通常具有强大的全局搜索能力，但是局部搜索能力有限；相反，局部搜索算法具有很强的单点搜索能力。因此，融合群体智能算法与局部搜索算法各自优势的混合优化算法，通常具有更强的搜索能力。

Jaya算法由RAO[13]于2016年提出，是一种连续优化问题的解决方法，与经典的遗传算法、PSO算法相同，都属于群体智能算法。该算法通过公式使解远离差解、靠近优秀解来获取新解，在过去几年已应用于各种优化问题，如微电网调度问题[14]、置换流水车间调度问题[15]、城市交通信号控制问题[16]和柔性流水车间调度问题[17]。GAO等[18]采用Jaya算法求解考虑工件插入的动态FJSP，并与其他启发式方法进行比较，实验结果证明了该算法的优越性；Rylan等[19]提出一种基于Jaya的混合算法求解FJSP最小化最大完工时间问题，创造性地提出一种针对FJSP的Jaya算法离散化方法，并对FJSP基准案例获得了较好解。Jaya算法的优点是无需调整算法参数，只需根据具体问题设计相应的迭代操作，被认为是求解组合优化问题的一种鲁棒、有效的算法。同遗传、PSO等经典群体智能算法一样，Jaya算法的局部搜索能力较弱，需要引入针对问题特性的局部搜索算法。

本文针对FJSP的特点，融合Jaya算法与TS算法，提出一种改进Jaya算法求解FJSP。在提出的改进Jaya算法中，设计了一种改进的离散Jaya算法操作机制来迭代候选解解集，并基于相似度和适应度的解评价方法来提高Jaya算法的搜索能力；同时，设计了一种结合N7邻域结构[20]和M.G.邻域结构[21]的TS算法，以提高混合算法在全局和局部搜索的能力。采用所提算法求解著名的FJSP基准实例，验证了算法的优越性。

1 FJSP描述

传统FJSP描述为：n个工件J={J1,J2,…,Jn}在m台机器M={M1,M2,…,Mm}上加工；不同工件Ji包含ni道工序{Oi,1,Oi,2,…,Oi,ni}，一个工件上所有工序按照一定的加工顺序进行加工；每道工序有可选加工机器集合Mi,j，Mi,j={Mi,j,1,Mi,j,2,…,Mi,j,k}，Mi,j⊆M；调度的目标是确定全部工序的加工次序和所选用的机器，使最大完工时间等指标最优。本文以最大完工时间Cmax(makespan)最小为指标，设Ci为工件Ji的完工时间，则Cmax最小的目标函数为

Cmax=min{max(Ci)},i=1,2,…,n。

(1)

加工过程需要满足如下约束条件：①每个机器同一时间只能加工一个工序；②每个工件同一时刻只能在一台机器上加工；③每个工件具有相同的优先级；④每道工序一旦开始就不能中断；⑤同一工件的工序存在先后约束，不同工件的工序不存在先后约束；⑥每一个工件在零时刻都可以加工。

由以上约束可以看出，作为JSP中衍生出来的拓展问题，FJSP既集成了JSP的部分特点，也具有自己本身的特点。其中FJSP与JSP相似，都需要确定工件在各个机器上的加工顺序，即工序排序问题；与JSP不同的是，FJSP存在机器柔性，允许一道工序选择多个机器进行加工，同时其存在循环排列的特性，一个工件的多道工序可以被同一台机器加工多次。传统的JSP已经被证明为NP-hard问题，FJSP在JSP的基础上增加了机器柔性，减少了工序与机器之间的约束，大大提升了求解的空间。一个工件数(n)为3和机器数(M)为4的FJSP实例如表1所示。

表1 3×4的FJSP问题实例

2 改进Jaya算法求解FJSP

2.1 传统Jaya算法

传统Jaya算法是RAO等[13]提出的一种元启发式算法，其基于持续改进的原理，将个体向优秀个体靠拢的同时不断远离差的个体，从而提高解的质量。传统Jaya算法通过方程式(2)迭代进化获取新解，不像其他进化算法需要许多参数，该算法只需针对特定问题调整迭代过程的参数(如rbest，rworst)，避免了因调整参数过多而使测试不易实施的问题。与其他元启发式算法相比，Jaya算法更容易理解和实现。

rworst,i,j,t(Xworst,j,t-|Xi,j,t|)。

(2)

式中：i表示种群中的第i个个体，i=1,…,n；j表示个体的第j维变量，j=1,…,m；t表示当前迭代的代数；X，X′分别为第t代第i个个体在第j维上更新前和经过Jaya公式迭代计算后的值；rbest，rworst是[0,1]之间的随机数，通过调整这两个参数大小，调整算法逼近最优解的能力；Xbest,j,t，Xworst,j,t分别为第t代最优最差个体在第j维上的值；rbest,i,j,t(Xbest,j,t-|Xi,j,t|)将当前个体朝当代最优解的方向进化，-rworst,i,j,t(Xworst,j,t-|Xi,j,t|)将当前个体朝远离当代最差解的方向进化。如果采用式(2)生成的新个体的适应度比原始个体优秀，则用新个体代替原始个体，否则不替换，然后对下一个个体进行Jaya迭代，直到遍历完所有个体。然而FJSP是一个离散问题，不能直接采用传统Jaya的迭代方式，如果将Jaya算法应用于求解FJSP，则必须对其进行离散化操作。

本文提出改进Jaya算法求解FJSP：①为了将传统Jaya算法应用于FJSP，本文采用文献[23]提出的离散化方法；②根据文献[23]出的离散化公式，结合FJSP的编码特点(两层编码)，提出4种Jaya迭代过程；③针对最小完工时间容易出现局部最优的问题，结合Jaya靠近最好解、远离差解的思想，提出一种相似度接受准则；④针对FJSP中具有机器柔性的特点，即一个工序的移动可以在所处机器上完成，也可以在多个机器上完成，将在JSP中效果优异的N7邻域结构与已证明在FJSP表现优秀的M.G.邻域结构结合[20-21]，并采用TS算法求解。改进Jaya算法包括编码与解码、种群初始化、Jaya解集生成与解的选择、TS算法和改进算法框架等。

2.2 编码与解码

编码是解的基因表达，编码的优劣直接影响算法解的质量。FJSP编码需要确定给定加工工序的排序，并给工序分配相应的加工机器，因此编码包括工序编码和机器编码两部分。

一个3工件在4台机床加工的编码如图1所示。工序编码和机器编码的长度为各工件加工步之和。加工序列表示为(O2,1,O3,1,O1,1,O2,2,O1,2,O1,3,O3,2,O3,3)，Oi,j表示第i个工件的第j道工序。对于机器序列，按照工件1、工件2、工件3的顺序，可以解释为工序O1,1,O1,2,O1,3对应机器M1,M1,M4，工序O2,1,O2,2对应机器M3,M1，工序O3,1,O3,2,O3,3对应机器M2,M2,M4。

解码方法为：首先按照工序序列顺序，将工序一个个添加到对应的机器分组上；然后，再次遍历工序序列，根据工件最大开始时间(即前工序结束时间与机器前工序结束时间之间的最大值)将工件分配到机器上；最后，采用插入式贪婪解码获取主动调度解。

2.3 种群初始化

种群初始化对算法解的质量有重要影响，一个优秀的种群初始化算法对种群多样性、种群子代解有积极的影响。因此，在混合算法初始解的机器选择上，80%的个体采用KACEM等[22]于2002年提出的根据全局加工时间最短选择机器的方法，20%个体的机器采用随机选择的方式产生；工序序列采用完全随机的方式生成。

2.4 Jaya迭代

传统Jaya算法适用于解决连续优化问题，而FJSP是一种典型的离散优化问题。因此，本文在文献[23]的离散化Jaya迭代方程基础上，提出一种扩展的离散Jaya算法求解FJSP。文献[23]的离散化Jaya迭代方程为

i=1,2,…,Npop;

(3)

从式(3)可知，r2Xbest,t使当前解靠近最优解，r3Xworst,t使当前解远离最差解，r4Xrandom,t可以提升迭代过程中寻优的可能。因此本文在式(3)的基础上，充分利用r2Xbest,t，r3Xworst,t，r4Xrandom,t对迭代个体的影响，提出一种应用于FJSP的离散Jaya迭代方式。该迭代方式包括4个迭代过程，迭代过程生成的解组合成为候选解解集，通过一定筛选排序，从解集中获取最优秀的解X′。该迭代方法可以在保证可行性的同时实现Jaya迭代中的“靠近”与“远离”。

根据式(3)，解集Seti由以下4种方式生成：

(1)根据文献[19]，删除当前解中与差解相同的序列，用最好解替换，如图2和图3所示。具体步骤如下：

步骤1找出Xi,t与Xworst,t中工序序列相同的点，以及Xi,t与Xworst,t中机器序列相同的序列。

步骤2删除Xi,t中工序序列相同的点和机器序列相同的点，保存在Xi,t,new中。

步骤3对于Xi,t,new中空缺的点，用与Xbest,t相对应的点进行替换。

步骤4将Xi,t,new放入Set{}，得到Set{…Xi,t,new}。

(2)删除好解与差解相同的序列，用当前解替换，如图4和图5所示。具体步骤如下：

步骤1找出Xbest,t与Xworst,t中工序序列相同的序列，以及Xbest,t与Xworst,t中机器序列相同的序列。

步骤2删除工序序列相同的序列和机器序列相同的序列，其余保存在Xi,t,new。

步骤3对于Xi,t,new中空缺的序列，用与Xi,t相对应的序列进行替换。

步骤4将Xi,t,new放入Set{}，得到Set{…Xi,t,new}。

(3)将好解与当前解进行交叉操作：

采用改进的优先操作交叉(Improved Precedence Operation Crossover, IPOX)进行工序交换，如图6所示，具体步骤如下：

步骤1将工件集J={J1,J2,…,Jn}随机分成两个集合B1和B2。

步骤2将Xbest,t中工序编码属于集合B1的序列替换到Xi,t,new的工序序列上。

步骤3将Xi,t中工序编码属于集合B2的序列按顺序依次替换到Xi,t,new工序序列的空白处。

采用多父辈交叉(Multi-Parent Crossover,MPX)操作进行机器交换，如图7所示，具体步骤如下：

步骤1产生一系列由0和1组成的随机数数组R，数组长度与编码长度相同。

步骤2选出Xbest,t和Xi,t中与数组R元素1位置相同的元素，将其互换，获得Xi,t的机器序列即为Xi,t,new的机器序列。

(4)将当前解与其他解(非最好解和最差解)进行交叉操作，与方式(3)类似。

在解集生成方式(1)和方式(2)中，会遇到两种极端情况，即两个个体完全相似和两个个体完全不相似，这两种情况会生成一个重复的个体，这个解可能是Xi,t，也可能是Xbest,t或Xworst,t。如果不及时处理所生成的重复解，则有可能使种群出现大量重复解，从而陷入局部最优。对于完全相似的情况，本文采用丢弃策略，采用重新初始化策略生成一个新的个体；对于完全不相似的情况，本文采用方式(3)，在保证不陷入局部最优的同时丰富种群多样性。

2.5 接受准则

Jaya算法具有自身的局限性，当采用某种单一目标时(如最小化完工时间)，虽然能引导个体靠近目前最优个体，但是该最优个体不一定是全局最优，从而陷入局部最优。因此本文采用一种新的个体选择方式保证种群的多样性，以提高算法的搜索能力。本文的选择策略结合最大相似度和最小加工时间两种方法，即90%的概率选择最小加工时间，10%的概率选择最大相似度。相似度计算方法如下：

考虑到Jaya迭代方程的目的是获取一个靠近优解、远离差解的新解，如何评价“靠近”与“远离”尤为重要。此前研究大多采用优化的目标值，即通过目标值与最优解的靠近程度来评价靠近与远离的程度，这种方法虽然可以在适应值上靠近优解，但是适应值相近并不代表解的形式靠近优解，或是携带优秀解的成分，因此本文引入一种新的评价靠近程度的方法，即相似度。阐述相似度计算之前，先介绍如何计算两个解的距离。本文将两个解X1与X2之间的距离用海明距离(Hamming distance)表示，即D(X1,X2)，

(4)

xd(i,j)=

(5)

式中x1(i,j)和x2(i,j)分别表示X1和X2在第j台机器上第i个加工的工件号。

为了达到靠近优解、远离差解的目的，提出相似度计算公式

DSimilar=D(Xi,Xworst)-D(Xi,Xbest)。

(6)

式中：D(Xi,Xbest)表示Xi与Xbest的距离，D(Xi,Xworst)表示Xi与Xworst的距离，D(Xi,Xbest)越小越好，D(Xi,Xworst)越大越好。本文的相似度计算过程如图8所示。

2.6 局部搜索算法

为了进一步提高算法的求解能力，本算法采用TS算法对个体进行局部搜索。TS算法是求解调度问题非常有效的一种局部搜索方法，其通过对已经搜索过的邻域解进行一定时长禁忌来减少对无效解的搜索，并通过特赦准则跳出局部最优。TS算法主要包括禁忌对象、禁忌表、禁忌长度、特赦准则、终止准则、邻域结构，其中邻域结构的优劣直接影响TS算法的搜索能力。

为了令TS算法更充分地发挥作用，本文结合FJSP具有机器柔性的特点将搜索分为变机器邻域和同机器邻域两部分，TS算法中对这两种邻域分别采用不同的邻域结构和禁忌表。针对变机器邻域，采用文献[21]提出的邻域结构与快速评价策略，该邻域结构可以极大缩少解的空间，且具有连通性。变机器邻域搜索步骤如下：

步骤1计算每个工序的最早开始时间StartTime(O)和最短尾时间TailTime(O)。

步骤2选取关键工序v，并将工序v的加工时间置为0。

步骤3重新计算每个工序的最早开始时间_StartTime(O)和最短尾时间_TailTime(O)。

步骤4从v的可选机器集合M(J,O)中选择其他机器k，设Qk为机器k上所有加工工序的集合，并计算Qk上的两个集合Rk和Lk：

Rk={x∈Qk|StartTime(x)+px≥

StartTime(PJ(v))+pPJ(v)}；

(7)

Lk={x∈Qk|TailTime(x)+px≥

TailTime(SJ(v))+pSJ(v)}。

(8)

式中：PJ(v)为工序v的工序紧前工序；SJ(v)为工序v的工序紧后工序。

本文变机器采用的邻域即为以上最优插入的集合，快速评价策略在文献[21]中有详细说明。禁忌对象采用(v,k)表示，其中v为被移动的工序，k为工序被移动之前的加工机器。针对同机器邻域，采用文献[20]提出的N7邻域和快速评价策略，禁忌对象采用工序序列(u,…,w,…,v)及其在机器上的位置(pu,…,pw,…,pv)，在给定的禁忌长度内禁止，具体请参见文献[20]。

禁忌长度的设置与迭代代数有关，基本长度为10，禁忌长度TabuLength=10+rand((iterMax-iter)/NM)，其中NM为工件数与机器数之积。从禁忌长度的公式可以看出，随着迭代次数的增大，禁忌表的长度变小，跳出局部最优的能力得到提高。当得到的新解优于当前最优解时满足特赦准则，如果不满足特赦准则，则在未被禁忌的解中选择最优解。当所有解均被禁忌时，采用文献[21]的选择策略。当TS算法迭代次数到达最大迭代次数时，算法终止。本文设计的TS算法流程如图9所示。

2.7 混合Jaya算法流程

本文针对FJSP的特点，提出一种融合TS算法的改进Jaya算法(Improved Jaya Algorithm and Tabu Search, IJA-TS)，其中Jaya算法负责全局搜索，TS算法对部分优秀个体进行局部搜索。混合算法流程图如图10所示。混合算法步骤如下：

步骤1设置种群参数、终止条件、工件数量、机器数量、加工时间等。

步骤2对种群进行初始化。

步骤3计算种群每个个体的适应值，将适应值最高的个体标记为Xbest，将适应值最低的个体标记为Xworst。

步骤4用改进的Jaya迭代公式求解，为每个个体生成相应的迭代候选解解集Seti。

步骤5如果解集中存在Xnew适应值比Xi大，则将Xnew替换到Xi+1，转步骤9，否则执行步骤6。

步骤6生成一个0～1的随机数Random，如果Random≤0.9，则执行步骤7，否则转步骤8。

步骤7将解集Seti中适应值最大的Xnew替换到Xi+1，转步骤9。

步骤8计算解集Seti中的相似度，将相似度最大的Xnew替换到Xi+1，然后执行步骤9。

步骤9对种群中前10%的个体进行禁忌搜索。

步骤10判断是否到达终止条件，是则执行步骤11，否则转步骤4。

步骤11输出结果。

3 实验结果与分析

本文所提改进Jaya算法采用VS2017 C++语言编程，运行环境为Intel I7四代CPU，主频2.6 GHz，内存16 G，操作系统为Window 8.1专业版。为了验证所提创新点，本文进行两组试验：①验证接受准则的有效性；②验证局部搜索的有效性。为了验证所提算法的性能，本文选择BRdata[24]，DPdata[25]，BCdata[26]基准问题对算法进行测试。为了显示所提算法的优越性，本文选取其他各类具有代表性的算法进行比较，包括提出禁忌搜索求解FJSP的M.G.的TS[21]以及混合算法中的HA[10]，hA-INS[12]，CROTS[27]。本文算法是对文献[19]Jaya算法迭代方程的改进，因此与该文献的结果进行比较。为了衡量算法性能，采用相对百分比偏差RE的平均值MRE描述算法能力，RE=(Cmax-LB)/LB×100%，其中LB是实例的下界。

3.1 接受准则有效性验证

为了验证所提接受准则的有效性，本文将对无局部搜索的改进Jaya算法与无局部搜索、最小完工时间接受准则的改进Jaya算法进行比较。这两个算法采用相同的算法框架，差别在于接受准则，IJA-WTS表示本文所提的接受准则接受新解(无局部搜索)，IJS-WTS-MA表示采用最小加工时间接受新解(无局部搜索)。设置种群为50，迭代代数为500，每个案例求解10次，将两个算法应用在BRdata中，得到结果如表2所示。表中：AVG为10次所得解的平均值；MRE为相对百分比偏差RE的平均值。

表2 接受准则的比较

由表2中各个案例的均值可见，采用所提接受准则的IJA-WTS结果优于采用最小完工时间接受准则IJA-WTS-MA的结果，IJA-WTS的MRE=0.049，IJA-WTS-MA的MRE=0.054，验证了所提接受准则的有效性。原因是最小加工时间接受准则容易过早陷入局部最优，而将相似度接受准则与最小加工时间接受准则混合能够增加种群的多样性，帮助算法跳出局部最优。

3.2 局部搜索有效性验证

为了验证所提局部搜索的有效性，本文对改进Jaya算法(IJA-TS)与无局部搜索改进Jaya算法(IJA-WTS)进行比较。这两个算法均采用相同的算法框架，差别在于有无局部搜索。算法设置种群为50，迭代代数为500，每个案例求解10次，将两个算法应用在BRdata中，得到结果如表3所示。

表3 有无局部搜索的比较

续表3

从表3可见，有局部搜索与无局部搜索对算法的影响非常大，添加了局部搜索后，所提算法的求解质量与结果有了很大提升，其中IJA-WTS仅有4个案例的均值达到下界，IJA-TS有8个均值达到下界。因为本文的局部搜索采用了变机器邻域中比较有效的M.G.邻域，在同机器邻域中采用在JSP应用十分有效的N7邻域，充分发挥了TS算法的局部寻优能力。

3.3 算法性能测试与分析

3.3.1 参数设置

改进Jaya算法中的参数比较少，主要有迭代种群、禁忌搜索迭代代数、禁忌基准长度。根据多次实验，本文设置迭代种群为50，禁忌搜索迭代代数为1 000，禁忌基准长度为10，每个算例求解10次，迭代次数为500代。

3.3.2 计算结果与分析

本文对BRdata[24]，DPdata[25]，BCdata[26]算例的计算结果分别如表4～表6所示。HA，hA-INS，IJA，CROTS分别为文献[10，12，19，27]的混合算法，TS为文献[21]的TS算法；Cmax为算例求解10次得到的最大完工时间的最优值；AVG为算例求解10次得到的平均值；CPUtime为迭代过程中运行500代的平均时间(如果获得下界值则为获得下界值的时间)；表中“*”表示获得实例的最优解。表7所示为不同算法针对不同测试实例的MRE值。因为不同文献中算法测试时的硬件环境、算法停止条件等不同，有些文章并未给出算法时间，所以本文不对求解时间进行对比。

表4 BRdata基准实例集测试结果比较

表5 DPdata基准实例集测试结果比较

续表5

表6 BCdata基准实例集测试结果比较

表7 各算法计算不同实例集的MRE比较

由表4～表6可见，针对BRdata和BCdata实例，本文算法可以求得所有实例的当前最好解，明显优于其他算法。与当前最新文献的IJA算法相比，在BRdata实例中，本文算法获得9个实例的下界，IJA算法只获得8个实例的下界；针对DPdata实例，本文算法有9个实例的结果好于IJA算法；针对BCdata算例，本文算法的结果与IJA算法持平。由表5可见，本文算法测试3个基准问题实例集的MRE值最小，为0.54，HA算法的MRE=0.63，TS算法的MRE=0.74，IJA算法的MRE=0.67，这是因为本文算法对Jaya的迭代过程进行改进，添加了迭代候选解解集，增加了迭代过程产生较优解的可能，改进了评价近优解的方法，提高了种群多样性，从而能够避免陷入局部最优，使Jaya算法迭代效果更好。所提算法与M.G.和HA算法比较，在BRdata，DPdata，BCdata 3个基准实例集中，本文算法获得的结果均优于或等于M.G.和HA算法。图11～图13所示分别为实例Mk06，Mk10，Seti5×××最好解的甘特图。

4 结束语

本文针对FJSP提出一种融合TS算法的改进Jaya算法，并给出改进Jaya算法的框架。Jaya算法具有简单、快速的特点，但容易陷入局部最优，本文基于离散Jaya算法公式，扩展Jaya迭代解的生成方式，设计了Jaya迭代候选解集，以及一种相似度和最大完工时间结合的评价方式，在保证种群多样性的同时进一步提了高Jaya算法的求解能力；在TS算法中，对同机器采用张超勇的邻域结构[20]，对变机器采用M.G.的邻域结构[21]，以进一步提高算法的局部搜索能力，使混合算法在分散搜索和集中搜索之间达到平衡。通过用基准问题实例测试所提算法，并与其他算法的结果比较，证明了混合算法的有效性和优越性。

未来研究可以通过扩展Jaya算法迭代获取新解的方式，改进评价“靠近”与“远离”的方法，融合更有效的邻域搜索，来进一步提高算法的求解性能，同时解决其他扩展类型调度问题。