改进ICA求解柔性作业车间插单重调度问题

唐 亮，程 峰，吉卫喜，金志斌

江南大学 机械工程学院，江苏 无锡 214122

柔性作业车间调度问题[1]（flexible job shop scheduling problem，FJSP）是经典车间调度问题的延伸，扩展了每道工序的机器柔性，相对经典车间调度问题来说更加复杂。然而在车间实际生产过程中，会面临各种各样的扰动因素，如机器故障、紧急插单、订单延期等一系列不确定因素，要充分考虑到当前的工作环境及系统状态，及时对生产中产生的扰动因素做出响应，制定出合理的重调度方案，因此就出现了柔性作业车间动态重调度问题。

目前，针对柔性作业车间动态重调度的研究，广大学者进行了大量的尝试。何小妹等[2]针对多目标多阶段混合流水车间的紧急订单插单重调度问题，分别采用NSGA-II 和NSGA-III 求解该问题，验证了NSGA-III 在求解三目标优化问题上的有效性。张守京等[3]针对车间调度调整提出了基于免疫度的规则导向策略，以确保实际生产计划的健康执行。卫少鹏等[4]在求解绿色柔性作业车间动态调度问题上，采用改进的头脑风暴算法进行求解，即在编码环节引进转换机制和多层编码策略，优化了机器选择和工序排序问题。张洁等[5]提出一种基于滚动窗口的改进蚁群算法来求解混合流水车间动态调度问题，即通过压缩蚂蚁可选路径，来缩短蚂蚁搜索周期和刺激蚂蚁尝试具有较弱信息素路径来提高所得解的全局性。李聪波等[6]提出一种基于多目标引力搜索算法的重调度节能优化求解方法，来解决机械加工过程中出现紧急任务插单和机床故障等动态事件导致原调度能耗增高、完工时间延长等问题。Akkan[7]为兼顾重调度的稳定性和鲁棒性，提出分支定与局部搜索结合混合算法。一些学者[8-10]针对重调度易导致生产系统的振荡，以事件驱动策略为研究对象进行一系列改进研究。张祥等[11]利用动态交互层机制，结合PSGA算法，提高了动态调度处理紧急订单的能力。陈超等[12]利用结合遗传算法和模拟退火算法的混合算法，求解以平均流经时间和能耗为目标的DFJSP优化模型。

帝国竞争算法是一种受社会政治行为启发而提出的智能优化算法，它既是有效的全局搜索算法，又具有很强的局部搜索能力，能有效地实现全局搜索和局部搜索的协调，适用于不同种类的优化问题，同时具有灵活性、鲁棒性、可扩展性等显著特征[13]。但是ICA 算法在产生初始解在空间上分布不均会使最终解易于偏向局部最优解。针对此类问题，李明等[14]提出一种新型帝国竞争算法来解决高维多目标柔性作业车间调度问题，采用新方法构建初始帝国，引入殖民国家同化，应用新的革命策略和帝国竞争方法来获得高质量解。操三强等[15]设计一种多目标帝国竞争算法，采用简化的初始帝国构建过程，在同化过程中引入向外部档案学习机制，并基于新的帝国竞争方法获得高质量的解。吕聪等[16]提出一种协作混合帝国算法，设计一种自适应参数的改进，来提高算法的收敛速度，引入帝国殖民地双改革变异，提高算法的局部搜索效率，最后创建大陆间国家交流机制，提高算法的全局搜索能力。而韩忠华等[17]在标准帝国竞争算法的基础上，引入汉明距离的概念判断个体之间的相似度，同时将各帝国集团内最弱殖民地用一个随机解代替并保留所有失去所有殖民地的个体，提高了算法的局部搜索能力。张清勇等[18]设计一种新型ICA，采用最大处理时间解码和基于加工速度的概率分配方法构建初始种群，运用基于工件-工速积的新型插入算子改善解的质量。

针对柔性车间动态重调度问题，广大学者进行了大量研究，但对于插单重调度，同时考虑设备待机能耗和加工能耗的研究较少。然而在实际生产过程中，紧急插单是十分普遍的扰动事件，如何制定合适的重调度方案对车间生产是十分重要的。本文提出一种改进的帝国竞争算法解决此类调度问题，即在帝国同化阶段采用离散帝国竞争算法的交叉变异实现，增加帝国革命机制，帝国消除机制，以及外部帝国入侵机制，并采用基于事件驱动的重调度策略来解决此类调度问题，验证了算法的有效性。

1 问题描述

柔性作业车间调度问题[19]可简单描述为：初始时刻，有若干工件Ji(i=1,2,…,n)到达，要将这n个工件安排在设备Mj(j=1,2,…,m)上进行加工；每个工件有多道加工工序，每个工件的每道工序都可以选择不同的设备进行加工，所选设备不同其对应的加工时长也不相同。但在实际生产过程中，车间会面临许多突发的扰动因素，这些扰动因素会对实际的调度计划产生较大影响，针对车间加工过程中可能出现的各种扰动因素，本文针对订单插入这一类动态事件。柔性作业车间动态重调度研究存在以下几个假设条件：

（1）初始时刻，所有设备均处于待机状态。

（2）相同工件不同工序有严格的加工顺序，即相同工件前道工序加工完成后，后道工序才能进行加工。

（3）每道工序可在可选设备集中任选一台设备加工，但同一时刻只能选择一台设备加工。

（4）一台设备同一时刻只能加工一个工件，同一工件同一时刻只能在一台设备上加工。

（5）每道工序的加工时间包括工序的准备时间和设备变更时间。

（6）原调度已加工和正在加工的工序保持不变，重调度时只需考虑未加工的工序。

在车间实际生产过程中，当有新的订单到来时，预调度方案不再适用，为保证车间的生产效率和订单的按时完成，此时应及时调整预调度方案，并结合重调度策略生成新的调度方案。

1.1 约束条件

车间实际生产过程中需考虑工件自身的约束和设备的加工约束：

式中，i、j、k分别表示工件号，工序号和设备号，Mij为工序Oij的可选设备集，θijk为决策变量0/1，若工序Oij在设备Mk上加工，决策变量为1，反之为0，CTij、STij和PTij分别表示工序Oij的加工结束时间、开始时间和加工时间，CTijk和STijk分别表示工序Oij在设备Mk上的加工结束时间和开始时间。

式（1）表示工序自身的加工约束，即每道工序每次只能选择一台设备进行加工；

式（2）表示工序自身的时间约束，即工序的完工时间为工序开始时间和加工时间之和；

式（3）表示工件各工序间的时间约束，即同一工件只有上一道工序加工完成后，下一道工序才能开始加工；

式（4）表示加工设备上各工序的时间约束，即同一设备同一时刻只能加工一道工序。

1.2 目标函数

本文的目标函数为最小最大完工时间、最小加工能耗、最小总延迟时间和最小设备变更次数，具体公式如下：

（1）最小化最大完工时间

式中，CTi表示第i个工件的最后一道工序的完工时间，CTmax为所有工件中的最大完工时间。

（2）最小化总能耗

本文采用文献[14]的加工能耗E的表示方法，初始时刻所有设备均处于待机状态，设备的总能耗为设备的待机能耗和加工能耗之和，总能耗的数学模型可表示为公式（6）：

式中，E0ijk和Pijk分别表示工序Oij在设备Mk上的单位时间加工能耗和加工时间，θijk为决策变量0/1，若工序Oij在设备Mk上加工，决策变量为1，反之为0，E1K和FTK分别表示设备Mk单位时间的待机能耗和待机时间，TE表示所有工件加工完成时的总能耗。

（3）最小总延迟时间

订单插入前后的最大完工时间的差值称为总延迟时间，总延迟时间的数学模型可表示为公式（7）：

式中，CT1max和CT0max分别表示重调度后所有工件的最大完工时间和预调度所有工件的最大完工时间，DT表示重调度前后完工时间差。

（4）最小化设备变更次数

本文最小设备变更次数是指订单插入前后，工件工序加工设备变更的累计。工件工序操作设备的变更，会增加人力劳动及调运成本，以此重调度需充分考虑工序加工设备的变更次数[20]。

工序Oij的变更，可描述为：

设备总变更次数可表示为：

式中，EC表示重调度前后，工序Oij操作设备的变更次数，TEC表示重调度完成后所有工序设备变更次数的总和。由于目标函数的量纲不统一，需要分别对其进行归一化处理，计算过程如式（10）所示：

其中，λ*、λ、λmax和λmin分别表示归一化的目标函数值、当前目标值、全局目标最大值和最小值。

本文采用线性加权和法，首先对本文的目标函数进行归一化处理，将多目标优化问题转化为单目标优化问题，如式（11）所示：

其中，CT*max、TE*、DT*、TEC*分别表示归一化后的最大完工时间、加工能耗、总延迟时间和总设备变更次数的数值，ω1、ω2、ω3、ω4分别为最大完工时间、总能耗、总延迟时间和总设备变更次数的权重系数，且满足：

2 FJSP动态重调度策略

柔性作业车间动态重调度策略，指系统在生产过程突发情况下将采取何种应对措施来解决发生的突发事件。事件驱动、周期驱动和周期与事件的混合驱动是广大学者普遍采用解决柔性车间动态重调度的方法，针对订单插入重调度，本文采用事件驱动策略。

在实际生产过程中，当出现订单插入时，确定订单插入点，插入点前已加工工序和正在加工的工序保持不变，找出插入点后未加工工序和新插入的订单用改进帝国竞争算法进行重调度，订单插入重调度的具体流程如图1所示。

图1 订单插入重调度流程Fig.1 Order insertion reschedule process

3 算法设计

3.1 基于I-ICA的柔性作业车间调度

本节采用I-ICA 求解柔性车间的插单重调度问题。ICA[21]是一种受社会启发的随机优化搜索算法，使其在解决大规模组合优化问题上具有一定的优越性，但是由于ICA 算法在产生初始解在空间上分布不均会使最终解易于偏向局部最优解。针对此类问题，本文相对于传统帝国竞争算法，做出了以下改进：

（1）I-ICA与标准ICA不同的是，在帝国内同化环节采用交叉变异方式来实现殖民地向殖民国家的移动。

（2）为提高算法的搜索广度，在帝国内同化环节之后，增加帝国革命机制，有利于实现算法的全局搜索。

（3）为提高算法的收敛速度，在帝国间竞争环节，增加帝国消除机制，同时保留较优解，即没有殖民地的帝国，将其归属于殖民地交由其他帝国去竞争。

（4）为进一步提高解的搜索广度，提高算法的收敛速度，本文在帝国竞争结束之后，引入外部帝国入侵机制。即产生新的帝国集团，以二元锦标赛的形式从新帝国集团和原帝国集团挑选战胜国集团，战胜国携带优质殖民地进入原帝国集团，战败国删除。

为更好理解算法的运行流程，图2 给出了I-ICA 求解的具体流程。

图2 I-ICA流程图Fig.2 I-ICA flowchart

3.2 编码与解码

为了同时描述工件的加工顺序信息与加工设备信息，本文采取基于工件编码和设备编码的双层结构，编码的第一层为工件码，其中工件出现的次数代表工件的第几道工序；第二层为设备码，每一个设备码表示该道工序可选设备集的索引号。每一个双层编码结构对应一个调度方案，表示为各工件各道工序所选择的加工机器。如图3所示，若某个国家编码为[2，2，1，3，3，2，1，1，3，1，1，3，2，2，1，2，3，3]，则工件码为[2，2，1，3，3，2，1，1，3]，设备码为[1，1，3，2，2，1，2，3，3]，工件对应的工序码为{O21,O22,O11,O31,O32,O23,O12,O13,O33}，根据各工序对应的可选设备集，可确定该设备码对应的设备编号依次为{1，1，6，3，4，3，5，6，7}。

图3 双层编码与解码Fig.3 Double layer encoding and decoding

3.3 初始化国家

ICA 初始化产生的个体成为国家。初始化产生的个体采用双层编码结构，前n个表示工件顺序，确定工件的加工顺序，后面表示各工序对应的设备，则一个国家个体表示为式（13）：

将随机产生的个体代入式（14）fitnesss 函数计算各个国家的归一化成本，具体如公式（11）所示。每个国家势力的大小由归一化后的成本衡量，成本越小国家势力越大。

根据成本大小进行排序，前Nimp成为帝国，其余沦为殖民地。采用赌轮盘为每个帝国分配殖民地，通常势力越大的帝国分配的殖民地越多。

3.4 帝国内同化

帝国内同化环节[16]相当于群体智能算法中的寻优过程，重在增强算法的区域搜索能力。离散型帝国竞争算法与标准帝国竞争算法最大的不同在于帝国集团内殖民地朝殖民国家的同化过程。本文殖民地向殖民国家的同化借鉴遗传算法中的交叉变异方式实现。由于优先操作交叉（precedenceoperation crossover，POX）方式产生的子代都是可行的，不会违背生产工艺约束，因此本文采用基于POX的交叉规则对工件码和设备码进行交叉。

图4 给出了POX 交叉的一个例子。先对工件码进行交叉，假定初始工件集为O={1，2，3}，随机将工件集分为两个子工件集Oi={2}和Oc={1，3}，其中Oi来自帝国，Oc来自殖民地，则新殖民地由帝国中的Oi工件集和殖民地中的Oc工件集两部分组成。完成工件码交叉后，其对应的加工设备也进行同样的交叉操作。

图4 个体交叉示意图Fig.4 Individual crossover diagram

3.5 帝国革命和殖民地革命

柔性作业车间调度问题[16]具有高维复杂性，为了增加算法的全局搜索，防止ICA 过早陷入局部最优，基于生物进化思想提出殖民地与帝国双改革的优化。

3.5.1 帝国革命

针对柔性作业车间调度问题，为满足工序和设备加工过程中的约束，采用简单交换会出现冲突，图5 采用部分映射的方法消除冲突。本文针对帝国改革的机制主要针对设备码的变异，即随机产生两个变异点，两个变异点间的位置基因采用随机变异的方式，即在可选设备集任选一台设备进行加工，其他位置的基因保持不变。计算新帝国的成本，若新帝国的成本优于原帝国，则替换原帝国成为新的宗主国。

图5 帝国革命Fig.5 Imperial revolution

3.5.2 殖民地革命

本文殖民地革命采用的机制与帝国革命机制相同，即都是采用部分映射的方式消除冲突，主要针对设备码的变异。图6 给出了殖民地革命机制。计算新殖民地的成本，若新殖民地的成本优于原帝国的成本，则替换原帝国成为新的宗主国，原帝国成为该宗主国的殖民地。

图6 殖民地革命Fig.6 Colonial revolution

3.6 帝国竞争

帝国竞争机制[16]是帝国竞争算法的核心思想，ICA通过竞争机制，不断迫使势力弱的帝国割舍殖民地给强大的帝国，不断削弱势力弱的帝国，最终实现帝国统一和少数帝国并立的局面。

3.6.1 帝国间竞争

帝国集团势力的大小通过总成本值来衡量，总成本越小，帝国集团势力越大。因此在进行竞争前需计算每个帝国集团的总成本，总成本由帝国集团下的殖民地成本和宗主国成本构成，其二者对帝国势力影响程度不同，因此需要重新构造帝国集团的总成本目标函数来衡量各个帝国集团的势力，即：

其中，TotalCostn代表第n个帝国集团的总成本；Costimp为帝国集团中的宗主国成本；Costcol为殖民地成本，其中ncol表示该帝国集团下殖民地个数；ζ表示殖民地成本对帝国集团总成本的影响程度（本文取ζ=0.1）。帝国集团间的竞争是将势力最弱的帝国集团的最弱殖民地释放，交由其他帝国集团竞争。若存在某个帝国集团的殖民地数量为0，则将其宗主国归属于殖民地交由其他帝国集团去竞争，原帝国集团消除，通常势力越强的帝国集团获得该殖民地的概率越高。

3.6.2 外部帝国入侵

标准帝国竞争算法[21]仅在随机产生的初始国家中迭代，考虑到产生的解若在解的空间上分布不均，则算法易陷入局部最优。现实社会中，当有外部较强的势力入侵时，会加剧冲突的演变，根据物竞天择，适者生存的原则，生存下来的各方会快速变强。本文基于这一现象，提出一种外来帝国入侵机制，用来增加解的多样性，以此来增加解的搜索广度，提升国家的质量，使最终结果更加贴近最优。外部帝国入侵机制步骤如下：

步骤1 随机产生国家群来组建一批外来帝国入侵集团。

步骤2 在原有帝国集团和入侵帝国集团中采用二元锦标赛的形式挑选战胜国。

步骤3 战胜国将挑选与原有帝国殖民地数量相同的优秀殖民地组建战胜国集团，并进入原有帝国集团进行竞争。

3.7 帝国覆灭及算法终止

在算法迭代过程中，势力强大的帝国集团会以一定的概率获取最弱帝国集团的最弱殖民来增强自身的势力，当某个帝国集团国家数量为1 时（即失去所有殖民地），帝国覆灭，该集团的宗主国沦为殖民地交由其他帝国竞争。理想状态下，算法迭代若干次后，弱小帝国全部覆灭，大陆统一，算法终止。实际运行过程中，帝国竞争过程中会始终存在几个势力相近的帝国，这些帝国始终存在直到达到最大迭代次数。此时应将势力最强的帝国集团中的宗主国作为最优解输出。

4 仿真结果及分析

本章通过仿真实验来验证I-ICA在求解柔性车间插单重调度问题上的有效性。随机假设三种插单的情景，得出最优重调度方案，验证算法在求解柔性作业车间插单重调度问题的有效性。

4.1 参数设置

本文的实例数据来自于南通某离散制造企业，本文的动态调度案例经过简化为9×8 的柔性作业车间调度问题，具体仿真数据如表1所示，可简化为9个工件，8台设备，30道工序的柔性车间调度问题。表2和表3分别为每台设备的待机能耗和假设的三种插单场景，三种插单场景独立发生。

表1 仿真实例数据Table 1 Simulation instance data

表2 设备待机能耗Table 2 Equipment standby power consumption

表3 三种插单场景Table 3 Three insertion scenarios

本文使用Matlab 2020a 对该企业生产实例数据进行实验，根据问题的规模和性质，在综合考虑求解结果和计算时间的前提下，本文I-ICA的参数设置参照文献[21]帝国竞争算法参数的设定，并通过多次实验验证该参数设定在求解本文调度问题上能取得较好的结果，最后确定本文提出的I-ICA参数设置为：最大迭代次数为200，国家个数为200，帝国数量为10，ω1、ω2、ω3和ω4分别设置为0.2、0.2、0.3 和0.3。同化概率、革命概率和入侵概率分别设置为0.8、0.4和0.33。

4.2 仿真结果

本文采用I-ICA 生成预调度方案，图7 为初始最优调度方案对应的甘特图，其中最大完工时间为18 min，总能耗为217.2 J。图7中不同颜色代表不同工件，工件的加工顺序由矩形块左上角的数字表示：其中“-”前的数字代表工件号，“-”后的数字代表工件的工序号，例如“5-1”代表工件5的第1道工序。

图7 初始调度方案甘特图Fig.7 Initial scheduling scheme Gantt chart

场景1 是在时刻t=3 时插入工件9，重调度后的最优调度方案对应的甘特图如图8所示，其中最大完工时间为18 min，总能耗为225.5 J，总延迟时间为0，总设备变更次数为0。

图8 重调度方案甘特图(t=3)Fig.8 Rescheduling scheme Gantt chart(t=3)

场景2 是在时刻t=6 时插入工件9，重调度后的最优调度方案对应的甘特图如图9所示，其中最大完工时间为19 min，总能耗为228.7 J，总延迟时间为1 min，总设备变更次数为0。

图9 重调度方案甘特图(t=6)Fig.9 Rescheduling scheme Gantt chart(t=6)

场景3是在时刻t=10 时插入工件9，重调度后的最优调度方案对应的甘特图如图10 所示，其中最大完工时间为18 min，总能耗为234.4 J，总延迟时间为0，总设备变更次数为0。

图10 重调度方案甘特图(t=10)Fig.10 Rescheduling scheme Gantt chart(t=10)

在以往研究中，GA 和PSO 作为常见的单目标优化算法，被广大学者用来解决调度优化问题。ICA在收敛速度和全局最优解方面表现出极好的特性，具有较好的优化效果，而ICA算法产生初始解在空间上分布不均会使最终解易于偏向局部最优解。因此为验证I-ICA求解的有效性，分别采用标准ICA、GA、PSO 对以上三种插单场景进行求解。各对比算法均进行相应的离散化处理，在综合考虑求解结果和计算时间的前提下，通过多次实验对比，确定各算法参数如表4所示。

表4 算法参数详情表Table 4 Algorithm parameter details table

四种算法求解的四种优化指标数据如表5所示，除场景3插单时间为10 min时，I-ICA的能耗指标较GA的能耗指标稍有不足，但其他指标均优于其他算法指标。可以说明I-ICA对比其他三种算法，实验结果更好，说明该算法在求解柔性作业车间插单重调度问题上的有效性。

表5 实验数据对比Table 5 Experimental data comparison

最后，为验证I-ICA求解的稳定性，针对场景2的插单情景，分别采用上述四种算法进行求解，四种算法运行10次的各项指标的平均值和方差如表6所示。从表6中可以看出，I-ICA 与ICA、GA 和PSO 相比各优化指标的平均值和方差较小，验证了I-ICA求解的稳定性。

表6 四种算法的性能对比Table 6 Performance comparison of four algorithms

针对上述假设的插单场景的实验数据分析，通过比较I-ICA 与ICA、GA、PSO 算法的求解结果，可以说明，插单前后的最大完工时间、总能耗、总延迟时间和总设备变更次数均能维持在一个较好的范围之内，满足车间实际加工的需求。

5 结语

本文针对柔性作业车间插单重调度问题，对传统帝国竞争算法进行了改进，相比较于传统帝国竞争算法，I-ICA加入了帝国革命机制，增加帝国消除机制，同时引入外部帝国入侵机制，采用基于事件驱动的重调度策略，以最大完工时间、总能耗、总延迟时间以及总设备变更次数为优化指标，对该类动态事件进行求解。对假设的三种不同插单场景进行实验仿真分析，得出的结果较为符合实际生产需要。针对三种不同插单场景，将I-ICA同ICA、GA和PSO求解的结果进行对比，I-ICA求解的各项指标均优于其他算法，验证了I-ICA求解的有效性。同时在同一插单场景下，通过比较四种算法运行10次各项指标的平均值和方差，I-ICA求解四项指标的平均值和方差较小，验证了I-ICA求解的稳定性。

柔性作业车间在实际生产中容易受到各种扰动因素的影响，接下来将对帝国竞争算法进行更加深入的研究，将其应用到其他扰动环境下的重调度中，例如设备故障、工单延误和交货期变更等扰动事件中。