改进迭代局部搜索算法求解多AGV柔性作业车间调度问题

2022-08-11胡晓阳姚锡凡曾中荣

计算机集成制造系统 2022年7期

胡晓阳，姚锡凡+，黄鹏，曾中荣

(1.华南理工大学机械与汽车工程学院，广东广州 510640； 2.广东世创金属科技股份有限公司，广东佛山 528300)

0 引言

在新一轮工业革命背景下，多样化、个性化的客户需求使得市场动态多变，促使企业发展符合客户需求的制造模式，多品种变(中小)批量的生产模式逐渐成为主流[1]。生产模式的转变促使制造车间提高柔性，以适应复杂多变的产品需求，同时也提高了生产系统的复杂程度，即物流任务多、流程变化大，并存在混流、频繁转产换线问题，自动导引小车(Automated Guided Vehicle, AGV)的自动化、高柔性、高效率和并行作业性可以很好地满足其中的物流需求，因此越来越多的生产车间采用AGV进行物料运输，多AGV组成的物流系统正成为车间物流自动化、柔性化配送的常态[2]。生产调度是执行生产计划、合理配置资源的关键环节，传统车间调度问题多以加工机器资源为中心，虽有一些研究考虑了运输任务的调度问题，但大多是分开考虑，存在进一步的优化空间。在调度过程中，当物料的运输时间与加工时间相比很短时，运输时间可以忽略，而在多AGV的自动化生产系统中，AGV物料运输任务的调度也是重要内容，同时许多应用场景中的运输时间占比高，变得越来越不可被忽略，因此有必要同时考虑加工工件的机器资源和运送工件的AGV资源，在给定加工任务的情况下，将二者进行集成调度，构建一个高度灵活且高效的智能化生产系统。本文正是研究多AGV与机器集成的柔性作业车间调度问题。

柔性作业车间调度问题(Flexible Job shop Scheduling Problem, FJSP)主要解决为多个工件的每个加工任务分配加工机器，并对每个机器上安排的所有工序任务排序这两个问题。FJSP属于离散组合优化问题，是NP-Hard问题，传统优化方法难以在多项式时间内取得最优解。在一个由多AGV负责自动化物料运输的柔性制造车间中，还需要确定每一次物料转移所使用的AGV和时间节点，在该种柔性制造车间中同时考虑求解机器分配、工序顺序排序、AGV分配、AGV调度4个子问题可以对最大完工时间进行全局优化，优化求解得到的调度方案中，包含了各工件各工序的加工时间节点和对应的工位，以及每一次物料运输任务所使用的AGV和时间节点。在FJSP上考虑运输时间和运输资源的约束，引入多个AGV，称之为多AGV柔性作业车间调度问题(Flexible Job shop Scheduling Problem with Multi-AGVs, FJSP-MA)，由于考虑工序之间运输任务的AGV分配及调度问题，其解空间结构更复杂，也属于NP-Hard问题。求解车间调度这一类NP-Hard问题主要有精确数学最优化方法和启发式方法两种方法。前者包括混合整数规划方法、分枝定界法、割平面法等，虽然这类方法能保证找到问题的最优解，但是计算复杂度高、数学模型较为复杂，尤其是大规模的问题难以建模，计算时间长。后者包含基于规则的分配调度方法和智能优化算法，力求在可接受的计算时间内求解出近似最优解，因为实际问题计算复杂度高，所以大量研究采用智能优化算法及其混合算法来对AGV与机器进行集成调度。LACOMME等[3]基于析取图建立了AGV与作业车间集成调度模型，以最大完工时间为优化目标，并采用改进文化基因算法求解；ZHENG等[4]针对多AGV与作业车间的调度问题建立了混合整数规划模型，采用CPLEX需要6.3小时才能求得6个工件20个工序的问题的精确解，于是他们提出一种结合12种邻域结构的禁忌搜索算法来求解；SAIDI-MEHRABAD等[5]在建立模型时考虑AGV无冲突路径选择，提出一种两阶段蚁群算法来求解集成多AGV的作业车间调度问题，其中第一阶段对运输任务分配AGV，第二阶段选择无冲突的AGV路径，并且研究了AGV数量对最大完工时间的影响；刘二辉等[6]提出一种改进花授粉算法来求解共融AGV作业车间调度问题，基于主成分分析法提出新的变异算子增强算法探索能力，引入交叉算子提高全局搜索能力；HAM[7]提出一种新的约束规划方法来求解多AGV作业车间调度问题，并提出一个中等规模的标准数据集。上述文献以遗传算法和群智能算法等基于种群的方法来求解多AGV的作业车间调度问题，而且都没有考虑机器柔性。

考虑机器柔性，ZHANG等[8]建立了带运输资源约束和可变加工时间的FJSP的整数规划模型，同时优化最大完工时间和工件在缓冲区的等待时间，提出一种遗传算法与禁忌搜索算法的混合方法，其中遗传算法分配机器和AGV资源，禁忌搜索进行局部搜索以改善解的质量，后续作者利用移动瓶颈过程[9]来改进此项工作，获得了更优解。NOURI等[10]针对柔性作业车间环境下的移动机器人与机器的集成调度问题，提出一种元启发式算法对该问题进行求解，该算法基于自主协作的多智能体模型，在第一阶段，采用GA使种群进化到适应度值高的解空间中，种群中的个体根据其相似度进行聚类，第二阶段采用并行禁忌搜索算法局部搜索进一步改善各类中的个体。文献[11-14]分别采用遗传算法、离散粒子群算法、离散鲸鱼算法求解柔性作业车间下机器与AGV的集成调度问题，其中文献[11]和文献[14]在算法中融合Dijkstra算法与时间窗原理来规划出AGV的无冲突路径，文献[12]同时优化了最大完工时间、机器利用率和AGV利用率3个目标，文献[13]研究了AGV数量对系统完工时间的影响；HAM[15]则对该问题提出了两种不同约束规划建模方法，可以高效求解小规模问题的最优解，同时也验证了公开测试案例中结果的最优性。HOMAYOUNI等[16]只对工序排序部分编码，提出一种多起点有偏随机键遗传算法来求解该问题，用一系列贪心启发式规则来完成机器选择任务和AGV的分配任务，同时测试了不同组合规则的求解效果。进一步地，文献[17]对工序排序、机器分配、AGV分配3个任务进行三段式编码，并提出一种延迟接受爬山算法来求解，在公开数据集上对该算法进行了测试，该算法是一种局部搜索算法，作者还重点提出了该问题的中等规模和大规模测试案例。

总之，在已有的AGV与机器集成调度的研究中，少数研究考虑了机器柔性，在求解方法上大部分研究是采用遗传算法、群体智能算法等基于种群机制的元启发式算法，易出现早熟收敛，算法的多个参数不易调试，且基本只在小规模问题上进行测试。迭代局部搜索是一种简单的基于轨迹的元启发式算法，已被证明在离散组合优化问题的求解上非常有效[18]，但是在机器和运输小车集成调度问题上少有相关的研究。本文针对FJSP-MA，以最大完工时间为目标建立单目标优化数学模型，提出一种改进迭代局部搜索算法，其中初始解利用启发式规则生成，设计了多种邻域结构用于随机邻域局部搜索，同时设置了精英解记忆库，算法搜索过程中不断更新记忆库，有效平衡算法的集中性和多样性，利用领域知识设计扰动策略提升算法的多样性。通过一种贪心启发式规则来对各运输任务分配最合适的AGV。

1 多AGV与机器集成的柔性作业车间调度问题描述及数学建模

1.1 问题描述

多AGV与机器集成的柔性作业车间调度问题是传统FJSP的拓展，可描述为：有n个工件(J1,J2,…,Jn)，要在m台机器(M1,M2,…,Mm)上加工，中间物料运输过程由v台AGV小车完成；每个工件包含一道或多道工序；工序顺序是预先确定的；考虑了机器柔性，即工件的某一道工序可在多台机器上加工；每道工序有对应的加工机器集和对应的加工时间，不同机器上的加工时间通常不同。由于同一工件的不同工序通常在不同的机器上处理，需要在机器与机器之间、机器与装卸货站点之间运送工件。AGV的每一个运输任务可分为空载行程和负载行程，空载行程时AGV需要从当前位置行驶到目标工位取工件，负载行程则是AGV取得工件后从所在工位运送到加工机器所在位置。一个实例场景如图1所示。

已知车间机器和装卸货点布局、机器与机器之间的运输时间、AGV数量、所有工序可选择进行加工的机器和对应的加工时间。最终目标是为每道工序选择最合适的机器，为每道工序的运输任务选择最合适的AGV，确定每台机器上各道工序的最佳加工顺序及开工时间，确定每次运输任务的开始时间和站点，使整个系统的某些性能指标达到最优，本文的优化指标是最大完工时间。

为了更好地分析问题，对FJSP-MA作出以下假设：

(1)在0时刻，所有AGV和工件原材料都在装卸货点准备就绪；

(2)在0时刻，所有机器处于空闲可用状态；

(3)每台AGV均可运输所有工件且一次只能运输一个工件；

(4)每台机器一次只能加工一个工件且一旦开始加工就不会中断(非抢占式调度)；

(5)每台加工机器的工件缓冲区容量足够大；

(6)不考虑AGV拥堵情况，机器间运输时间固定；

(7)AGV完成运输任务后可以停靠在机床旁边，不返回装卸货点；

(8)每个工件具有固定的加工工艺路线；

(9)不考虑机器故障、AGV故障、AGV电量等因素。

1.2 数学模型

下面对各符号变量进行说明。

(1)集合变量

J表示待加工工件集合，J={J1,J2,…,Jn}，其中n为待加工工件数量；

M表示加工机器集合，M={M0,M1,M2,…,Mm}，0为装卸货站点，m+1为工位数量；

V表示可用AGV集合，V={V1,V2,…,Vv}，其中v为AGV数量；

OPi表示工件Ji的所有工序集合，OPi={OP1,OP2,…,OPni}，其中ni为Ji的工序总数。

(2)相关参数

Oij表示工件i的第j道工序；

Oijk表示工序Oij选择在机器k上加工；

ptijk表示工件Oij在Mk上加工所需时间；

Tij表示工序Oij的配送任务，包含空载行程e和负载行程l；

(3)决策变量

ptijk表示工序Oij由Mk加工，工序Oij的加工时间；

eijw表示工序Oij由Vw运输，小车空载行程运输时间；

lijw表示工序Oij由Vw运输，小车负载行程运输时间；

Cij表示工序Oij的完工时间；

Ci表示工件Ji的最后完工时间；

目标函数如下：

f=min(max(C1,…,Ci,…,Cn))。

(1)

(2)

(3)

(4)

∀p∈(1,2,…,n)，∀q∈(1,2,…,ni)；

(5)

(6)

(7)

(8)

(9)

(10)

∀p∈(1,2,…,n),∀q∈(1,2,…,ni)；

(11)

(12)

(13)

∀i,p∈(1,2,…,n),∀j,q∈(1,2,…,ni)。

(14)

2 改进迭代局部搜索算法

迭代局部搜索算法(Iterated Local Search, ILS)是一种基于轨迹的元启发式算法，简单、易于实现、高效和模块化，已经被广泛应用于离散组合优化问题，如流水作业车间调度问题[19]、车辆路径问题[20]、大学课程时刻表问题[21]等。ILS的主要思想是：从某个随机起始点出发，局部搜索和扰动交替进行，在此过程中只保留最好的解，可在较短时间内找到问题的次优解。本文提出改进迭代局部搜索算法(Improve ILS, IILS)，设计有效的局部搜索、扰动机制和解的接受准则来求解FJSP-MA。

2.1 IILS求解FJSP-MA编码与解码

FJSP-MA包含3个子问题：①机器分配问题，为每道工序选择符合优化目标的机器；②工序调度问题，即在分配好加工任务的机器上确定加工顺序，进而确定各个工序的开始/完成时间；③AGV分配问题，为每一道工序安排最适合的AGV，进而确定每次工件运输任务的起点和终点工位，以及对应的时间节点。利用元启发式算法求解FJSP-MA的首要问题是编码，编码空间与解空间存在映射关系，因此编码方式决定了算法搜索空间的大小，同时影响算法中的局部搜索算子和扰动算子的设计。本文采用在FJSP中应用最为广泛的MSOS-Ⅰ编码方式[22]，如图3所示，该编码方式分为机器选择串和工序顺序串，分别用来解决机器分配子问题和工序排序子问题，FJSP-MA中AGV分配子问题则由启发式规则来解决，在解码过程中完成。

该编码方式的优点在于任意一个由MSOS-Ⅰ编码所生成的解总可以解码成一个可行的调度方案，MSOS-Ⅰ编码中的两条子串具有不同的语义特征，局部搜索算子可以使用符合子串特征的局部搜索方式，分别对两条子串进行操作，从而避免了非法解的产生和修复，提高了算法的运行效率。

解码过程是根据解的编码来计算最大完工时间，同时生成一个具体调度方案的过程。

(15)

(16)

工序Oij的完工时间Cij由工序在Mij的开始时间加上Oij加工时长，Oij开始时间为当前机器Mij上一道工序的完成时间CMij和工件Ji到达Mij时间tw二者中的更大值，最后Cij的计算公式为：

Cij=max{CMij,tw}+ptijMij。

(17)

计算工序Oij的完工时间Cij后更新机器时间CMij=Cij以便后续工序的调度计算。整个时间和工位的推导过程重复进行直到最后一个工件的最后一道工序完成调度，最终所有完成加工的成品再通过运输返回装卸货点。整个模型的优化目标为最小化最大完工时间。

AGV的分配利用了一个“先到先服务”的启发式规则算法，在所有AGV中，如果存在AGV到达工位Mi(j-1)的时间晚于Oi(j-1)的完工时间，则从中选择最早到达的AGV，否则选择最晚到达Mi(j-1)的AGV小车。这是一种贪心的启发式规则，在很短时间内取得优异的调度结果，在确定工序顺序和机器安排之后，每次利用该规则调度AGV完成某工序的运输任务时，可以使工序的开始时间最早。

详细的解码流程如算法1所示，其中输入参数包括MS编码段、由OS编码生成的具体工序Operation、各工序对应加工机器矩阵JobMachine、各工序对应加工时间矩阵ProcessingTime、各个工位之间的运输时间矩阵TransportTime；输出参数为工序时间OperationTime，包含各个工序的开始时间和结束时间，AGVScheduleDetails包含所有AGV小车每次运输任务的起点和终点工位，以及对应的开始时间和结束时间。

算法1解码流程。

输入:MS，Operation，ProcessingTime，JobMachine，TransportTime;

输出:OperationTime，AGVScheduleDetails。

Initializtion

Initialize the available time for each machine Ck=0;

Initialize the available time for each AGV tw=0;

Initialize the current location of all AGV to M0;

For k=1 to Operation.length do

Oij=Operation(k);

Mij←getprocessingmachine of Oijby MS and JobMachine;

Access the available time twand current station Mwof each AGV;

Access the available time Ckof each machine;

Foreach w in V do

End if

End Foreach

Cij=max{CMij,tV*}+ptijMij；

CMij=Cij；

Update Operation Time；

Update AGV Schedule Details；

Endfor

2.2 启发式规则初始化

受FJSP求解方法的启发，为改善初始解的质量，本文在生成初始解时考虑机器工作负载平衡，采用基于全局选择的方法确定各个工序的加工机器[23]，保证了总加工时间最短的机器最先被选到。其基本实现方式为用一个数组来记录所有机器的加工时间，随机在工件集中选择一个工件，从当前工件的第一道工序开始，将当前工序的可选加工机器的加工时间加上数组中的对应时间。从中选择最短时间作为当前工序的加工机器，并将数组更新，以此类推，直到当前工件所有工序的加工机器选择完毕，然后再随机选择一个工件开始，直到所有工件选择完毕。

2.3 改进的邻域搜索

邻域局部搜索算子和邻域搜索策略对IILS的求解效果影响很大，本文针对FJSP-MA特性设计了随机移动和指向性移动两类邻域移动。其中随机移动包括：工序机器移动、工序顺序交换、工序插入；指向性移动包含：最短加工时间机器移动、同机器工序顺序交换。在这两类邻域移动中，指向性移动有助于算法快速收敛到理想的解空间区域中，随机移动有助于扩大搜索范围。两类邻域随机混合使用，可以在保证算法求解精度的前提下，有效提高算法的搜索速度。具体邻域结构描述如下：

N1工序机器移动：随机选择一个加工工序，为其重新分配一个加工机器，具体操作为在MS中随机选择一个位置，重新生成一个机器编码；

N2最短加工时间机器移动：随机选择一个工序，将该工序分配给加工时间最短的机器；

N3工序顺序交换：随机选择两个工序交换其调度顺序，具体实现为在OS中随机选择两个位置交换编码。

2.4 扰动策略与接受准则

(18)

2.5 长期和短期记忆库策略与算法总流程

上述局部搜索策略和接受准则重点强调了算法的局部开发能力，为增强算法的全局探索能力，以进一步提升算法的求解精度和稳定性，设计了长期和短期这两种记忆库策略来提升算法的多样性。

第一种记忆库策略设置短期精英解记忆库，该记忆库中保存固定数量的历史当前解，在每一次迭代过程开始时，运用贪婪—随机策略从中选取一个作为当前解，对当前解进行局部搜索，具体实现方式为保存固定数量的几个最优解，对第一最优解和第二最优解设置较大的选中概率，其余的解则以均等的较小概率选中，在迭代过程结束时更新当前解记忆库，保留最近的最优解，算法2描述了带精英解短期记忆库的总算法流程，用IILS-Ⅰ来表示。

算法2IILS-Ⅰ的算法流程。

输入:ProcessingTime，JobMachine，TransportTime，AGVNumber;

输出：bestSolution。

Initializtion

Initialize MAX_ITERATION and MAX_NO_IMPROVEMAX_ITERATION;

InitializeeliteSet(s1;s2;s3;s4;s5;s6)=(s0;s0;s0;s0;s0;s0);

Initialize φ1,φ2,φ3;

i←0,iidle←0;

Repeat

Select solution sifrom elite Set with probability φ(φ1;φ2;φ3/4;φ3/4;φ3/4;φ3/4)

choice←random generate an integer from in[1,2];

Switch choice

Case 1

End if

End Switch

End if

iidle←0;

else iidle←iidle+1;

End if

Untili≥MAX_ITERATION or i≥MAX_ITERATION*MAX_NO_IMPROVE

(19)

算法3描述了带当前解长期记忆库的总算法流程，用IILS-Ⅱ来表示。

算法3IILS-Ⅱ算法流程。

输入:ProcessingTime，JobMachine，TransportTime，AGVNumber;

输出：bestSolution。

Initialize MAX_ITERATION and MAX_NO_IMPROVEMAX_ITERATION;

i←0,iidle←0;

Assign a value to H, initialize memory bank fv=f(s0)，∀v∈[1,H];

Repeat

choice←random generate a integer in[1,2];

Switch choice

Case 1

If rand<0.8 then

End if

End Switch

End if

iidle←0;

else iidle←iidle+1;

End if

h←i+1 mod H

End if

Until i≥MAX_ITERATION or i≥MAX_ITERATION*MAX_NO_IMPROVE

3 实验验证与分析

所提出的改进迭代局部搜索算法在MATLAB 2018b软件平台上实现，运行在Win10系统上，硬件环境为Intel Corei5-7300U CPU，2.6 GHz，8 GB内存。为了测试所提算法的性能以及验证相关猜想，进行了一系列的数值仿真实验：

(1)算法改进策略有效性证明实验为证明改进策略的有效性，将记忆库策略简记为M，用到的邻域算子记为N1、N2、N3，设计了6种不同策略组合的控制对照实验，对比了这6种算法的性能差异。

(2)算法基准案例测试和算法横向对比实验分别在FJSP-MA的小规模和大规模公开标准算例上测试IILS-Ⅰ、IILS-Ⅱ的性能，并与其他文献中已有的研究结果：遗传禁忌搜索算法(Genetic algorithm with Tabu search, GATS)[8]、带转移瓶颈的遗传禁忌搜索算法(Genetic algorithm with Tabu search and Shift Bottleneck, GTSB)[9]、延迟接受爬山算法(Late Acceptance Hill-Climbing, LAHC)[16]进行比较，验证IILS-Ⅰ、IILS-Ⅱ的有效性和高效性。

3.1 数据集

本文实验所用的基准测试案例(1)基准案例下载地址：https://fastmanufacturingproject.wordpress.com/2019/04/11/fjspt-instances/。均来自于文献[17]，文献[17]的算法在5个案例集上进行了测试，其中两个规模稍小的案例集总工序数都在20以内，文献[17]在FJSP几个经典测试案例基础上添加车间工位布局信息，提出了另外3个规模更大的测试案例，中等规模案例集总工序数在50以内，大规模问题案例集总工序数为50到240不等。本文沿用其中2个测试案例集作为基准案例，共包含20个测试案例，其中小规模用fjspt1:10表示，大规模数据集用MKT1:10表示。所有算例中AGV的数量为2。

3.2 性能指标

3.3 参数设置

图5为IILS-Ⅱ在算例fjspt10上得到的最佳调度方案，图上纵坐标表示机器和AGV，相同颜色的矩形代表同一工件的不同工序，比如p(5,1)=18表示工件5的第一道工序的加工时间为18，AGV部分深灰色和白色矩形分别表示各个AGV的负载行程和空载行程，其节点上面的数字代表到达时间，下面的标注为对应的工位。图5所示的调度方案中工件的加工过程描述如下：首先安排在机器M3加工工件J2的第1道工序，需要将J2从M0运输到M1，此时两台AGV处于空闲状态，完成该运输任务时间相同，由AGV2完成；再安排机器M6加工工件J2的第2道工序，需要将J2从M3运输到M6，各工位之间AGV运输时间可由车间布局信息求得，此时AGV1在M3，则AGV1运送路线为M3→M6，完成运输任务的时刻为56+6=62，此时AGV2在M1，则AGV2运送路线为M1→M3→M6，完成运输任务的时刻为66+4+6=76，AGV1完成该运输任务的时间更早，因此选择AGV1完成该运输任务，后续工件工序操作以此类推。

3.4 结果与讨论

3.4.1 改进策略有效性验证实验

为证明单一改进策略的有效性和对比不同组合策略的性能差异，在MKT1:10上进行测试，实验过程中每一种组合策略在每个问题上进行15次独立测试，将记忆库策略简记为M，所有用到的邻域为N1、N2、N3，IILS-Ⅱ的组合策略为M+N1+N2+N3，对比的组合策略包括M+N1+N3、M+N2，以及无记忆库的策略N1+N3、N2、N1+N2+N3，策略中的M都为长期记忆库，下一节介绍长期记忆库与短期记忆库的对比实验。算法参数MAX_ITERATION=2 000 000，MAX_NO_IMPROVE=0.04，各个算法在10个规模的问题中表现如表1所示。采用Wilcoxon秩和检验[24]检测IILS-Ⅱ所得结果与其他算法所得结果的显著性差异(置信度95%)，符号“+”、“-”、“=”分别表示IILS-Ⅱ显著优于、劣于、等价于对比算法，表中最后一行数据统计IILS-Ⅱ与其他算法的Wilcoxon秩和检验结果，w/t/l表示IILS-Ⅱ分别在w、t和l个问题上优于、等价于和劣于参与比较的算法。

表1 IILS-Ⅱ及其变种所得最优解均值和相对标准差σ%

从表1可以观察到，记忆库策略M大幅度改善了ILS的寻优性能，问题规模越大效果越显著，在所有10个问题上，M+N1+N2+N3策略分别在10、9、10、10个问题上优于M+N2、N1+N3、N2、N1+N2+N3策略，在10个问题上等价于M+N1+N3。对比表中各算法的测试结果，N2邻域算子在每一次迭代过程中将随机选择的工序分配给加工时间最短的机器，是局部贪婪的搜索方式，算法快速收敛于局部最优解中；N1邻域算子每一次迭代过程将选择的工序重新随机分配给加工机器，N3则每次随机交换两个工序的顺序，N1和N3的组合保证了解的多样性，但是多样性过强，难以快速收敛到最优解；在同一邻域搜索策略的基础上加上记忆库策略M，使得算法集中在优良解附近进行局部搜索，算法因此具有适中的多样性；表2对比了M+N1+N2+N3邻域与M+N1+N3邻域策略的平均运行时间，M+N1+N3加上N2之后算法平均运行时间有所降低，M、N1、N3的组合保证了算法适中的多样性，再加上N2指向性移动，在保证求解质量的前提下进一步提升了算法的收敛速度，其原因在于，单纯的混合随机邻域搜索策略N1+N3相比N1+N2+N3的方法算法多样性更强，在搜索过程中可能出现更多的重复搜索和迂回搜索的情况。图7为6种策略在MKT10上测试一次的收敛曲线图，从图中可以看出除M+N1+N2+N3和M+N1+N3外的4种组合很快陷入局部最优解，而M+N1+N2+N3收敛速度更快，并且求解质量也不劣于M+N1+N3。

表2 M+N1+N2+N3邻域与M+N1+N3邻域策略平均运行时间

3.4.2 算法基准案例测试和横向对比实验

表3是fjspt1:10的最优解和GTSB、GATS算法求得的最好解。图8对比了GTSB、GATS、IILS-Ⅰ、IILS-Ⅱ 4种算法在fjspt1:10上的GAP，从图中可知，IILS-Ⅰ、IILS-Ⅱ未求到最优解的次数分别为3和1，对于fjspt1:10基本上能求得最优解，表明IILS-Ⅰ和IILS-Ⅱ在小规模问题上求解精度较高，而GTSB和GATS求得最优解的次数为0，证明了IILS-Ⅰ和IILS-Ⅱ的优越性。

表3 GTSB、GATS算法求得的最好解

表4记录了LAHC(H=1 000)、IILS-Ⅰ和IILS-Ⅱ在fjspt1:10上得到的性能指标，在求解时间方面，IILS-Ⅱ的平均运行时间比LAHC(H=1 000)缩短了84%，其主要原因在于LAHC的解采用3层编码，通过算法搜索来解决AGV分配任务，而IILS采用了MSOS-Ⅰ双层编码，编码长度缩短了1/3，使得求解空间大大缩小，同时该编码方式避免了非法解的产生和修复，进一步提升了算法的运行效率。IILS-Ⅰ的平均运行时间与LAHC(H=1 000)相当，IILS-Ⅱ与IILS-Ⅰ相比计算时间更长，其解释为IILS-Ⅱ在局部搜索过程中反复访问到相同的解，由于相似的优良解其邻域可能重合，从精英库中选取当前解时存在迂回搜索情况，而IILS-Ⅱ采用了激进的劣解接受机制，在H较大时保证了被接受的劣解与当前解存在较大差异，有效减少了迂回搜索。在求解稳定性方面，3种算法的稳定性水平相当。

表4 LAHC、IILS-Ⅰ、IILS-Ⅱ算法在fjspt1:10问题上测试结果

表5记录了LAHC(H=1 000)、LAHC(H=100)、IILS-Ⅰ和IILS-Ⅱ在大规模算例MKT1:10上的测试结果，其中加粗的数字表示每一个算例上最优的Cmax。从求解的最好结果Cmax来看，IILS-Ⅱ在7个算例上是最优的，刷新了LAHC在这7个算例上的最小值，IILS-Ⅰ刷新了LAHC在6个算例上的最小值，证明了双层编码混合AGV分配启发式算法是有效的，最优解刷新的原因可解释为在AGV分配算法有效的前提之下，双层编码使得搜索空间大大缩小，短时间内访问到了更多的解；如图9所示，从求解稳定性来看，LAHC(H=1 000)、IILS-Ⅰ和IILS-Ⅱ的相对标准差σ%水平相当，同时都明显优于LAHC(H=100)；最后从算法的求解速度来看，IILS-Ⅱ在10个算例上的平均运行时间是LAHC(H=100)的约1/50，是LAHC(H=1 000)的约1/5，是IILS-Ⅰ的1/2，证明IILS-Ⅰ在求解速度上具有显著的优越性。另外，如图10所示，4种算法在各算例上的平均运行时间随工序数增加而呈指数增长；总工序数越多，IILS-Ⅰ、IILS-Ⅱ相比LAHC在求解速度上提升越明显。

表5 LAHC、IILS-Ⅰ、IILS-Ⅱ算法在MKT1:10问题上的测试结果

迭代局部搜索算法本质上是一种随机搜索，FJSP-MA面对稍大规模的问题存在巨大的解空间，IILS在求解速度和求解精度方面均有优异的表现。根据优化问题的NoFreeLunch定理，在离散组合优化问题中，除非在算法中考虑了问题的特定结构，否则一种算法不能被证明比随机算法性能更好，甚至还要更差[25]。对于FJSP-MA这个特定的离散组合优化问题，一方面因为采用MSOS编码，其解空间存在这样一个事实：优良解的编码结构是相似的，且优良解具有聚集性，所以不断在优良解邻域进行充分的局部搜索可以增大命中最优解的概率；另一方面优良解又具有分散性，因为相同目标函数值的多个优良解其编码结构可能存在较大差异，所以采用精英解记忆库策略来提升算法多样性，充分利用了搜索过程中产生的信息来指导搜索方向，避免陷入局部最优解。这样对于FJSP-MA来说，IILS算法不再是单纯的随机搜索，而是每次在最优解概率高的解空间区域进行采样，迭代地在优良解邻域局部搜索，局部搜索时算子微调当前解的编码结构，这一操作的计算复杂度低，因此算法整体计算效率较高。