柔性车间调度问题的协作混合帝国算法

吕 聪，魏康林

(三峡大学 电气与新能源学院，湖北 宜昌 443002)(*通信作者电子邮箱zeyuanwei@163.com)

0 引言

柔性作业车间调度问题(Flexible Job-shop Scheduling Problem， FJSP)是传统作业车间调度问题(Job-shop Scheduling Problem， JSP)的拓展，即多工件工序排列在多机器加工的高维规划问题，由Bruker等[1]于1990年首次提出。FJSP与JSP不同的是采用多机器并行生产加工模式，可选择加工路径增多，已被证明是一个NP完全问题，理论上更符合实际工业调度要求，因此柔性车间调度问题的研究具有重要的理论意义和实际应用价值。

目前，国内外相关学者对柔性车间调度问题已经进行了大量研究。Gao等[2]在混合多微型鸟群算法中，提出自适应多种交叉策略，但收敛速度较慢。Zuo等[3]在自适应无功优化多模算法中，提出多种局部搜索方法和特有的邻域结构，但是全局搜索能力下降。Sreekara等[4]在社会网络方法中，分析协作网络评估功能属性，且融入遗传算法，但邻域搜索能力下降。张洁等[5]在两阶段蚁群算法中，建立调度模型与蚁群搜索的映射关系，为任务分派与排序分别设计蚁群优化算法，但求解质量不稳定。基于上述算法的优势和缺陷，采用一种新的启发式算法，Atashpaz-Gargari[6]在2007年受帝国竞争行为启发提出帝国竞争算法(Imperialist Competitive Algorithm， ICA)。该算法具有收敛速度快、收敛效果好、全局搜索能力强的优点，对于相对简单的JSP已有较好的优化效果[7]。因此，本文根据柔性车间调度的特性改进帝国竞争算法，引入帝国殖民地双变异多改革策略和自适应参数，引入大陆间优秀帝国的政治交流机制，减少了早熟现象的发生，提高了寻优精度，得到了较好的调度方案。

1 柔性车间调度问题

1.1 问题描述

柔性车间调度是约束工件工序的调度问题，通常描述[8-9]为：某工厂需要加工多个不同工件，每个工件拥有长短不同的加工工序，各个工序可以选择不同的机器作为加工路线，且不同机器针对某个工件工序的加工时间存在差异。关键就是调整工序顺序以及安排合理机器加工，使最大完工时间最优化。为了更加接近实际工厂操作效果，针对工件加工过程作出如下规定：

1)每个工序都具有预先可用的加工机器以及加工时间——作为实际调度前提。

2)任意工件的工序可以预先设定机器随机选取加工——符合实际调度的目的意义。

3)工件准备时间和等待时间都记录在加工时间内——注重整体的调度规划结果。

4)允许工件的不同工序之间存在等待——考虑实际生产多任务分配优化。

1.2 参数设置

针对柔性车间调度问题的研究，定义参数如下:C表示所有工件加工结束花费时间;g表示加工的总工序;N表示待加工的工件总数;M表示可运行的机器总数;Pi表示工件i，i∈[1,N];Jk表示第k号机器,k∈[1,M];Pij表示工件i的第j个工序;Tijk表示Pij的工序在机器k上工作时间长度;Sijk表示Pij的工序在机器k上开始加工时间;Eijk表示Pij的工序在机器k上加工结束时间。

1.3 建立数学模型

根据柔性车间调度问题，建立数学模型[10]如下：

(1)

Si(j+1)k≥Eijk

(2)

Eijk-Sijk=Tijk

(3)

(4)

其中：式(1)就是本文研究FJSP的目标函数最小化最大完成时间；式(2)代表工件的工艺约束，任何一个工件必须严格按照加工顺序进行加工，即只有在前一道工序完成后才能进入下一道工序加工；式(3)代表工件加工约束，一个工序只允许在一台机器上加工，一旦开始加工，不允许中断加工过程；式(4)代表机器资源约束，机器对某一工序加工完成后可立即加工其他工件，中间可以不设等待时限，同时限制一台机器同一时间只允许操作一个工件。

2 协作混合帝国算法

2.1 帝国竞争算法

帝国竞争算法(ICA)是通过模拟帝国殖民竞争机制而建立智能算法，本质上是群体随机优化搜索方法。ICA基本流程[11]为：产生初始帝国，同化殖民地，帝国之间竞争，帝国消亡。

2.1.1 产生初始帝国

ICA与其他智能寻优算法初始化相同，随机产生的个体并称为国家。在FJSP中，采用双层编码机制，前g个表示工件工序，确定工序加工顺序，后面代表各工序对应加工机器，则一个国家表示为式(5)：

Country=[P1,P2,P3,…,Pg,J1,J2,J3,…,Jg]

(5)

将随机产生的国家编码代入式(6)中的fitness函数计算其调度时间。根据调度时间对每个国家进行强弱估值，即时间越小国家势力越大。

Cost=fitness(Country)

(6)

根据式(7)、(8)，选择势力较大的Nimp作为帝国竞争算法中的帝国，剩余的国家为殖民地。Nimp个数会对算法求解结果产生影响，Nimp较大时，各个帝国分配较少的殖民地，收敛趋势分散，影响收敛速度；Nimp较小时，帝国拥有较多殖民地，趋势收敛单一，容易陷入早熟和局部收敛。

Cm=K×max{Costimp}-Costimp

(7)

(8)

其中：Cm为帝国分配殖民地的修正值；K是修正系数，1≤K≤2；Numi为第i个帝国所分殖民地的个数，以帝国的势力决定拥有殖民地数量。

2.1.2 同化殖民地

18世纪中期，世界帝国主义不断瓜分掠夺殖民地。为了更好地管辖殖民地，强大的帝国将风俗文化和政治思想在殖民地进行推广，ICA的同化操作就是模仿这一过程。

同化操作相当于群体智能算法中的寻优过程，重在保证算法区域搜索能力。ICA优势在于：所有殖民地群体向多个优秀个体进行迁移，增强群体中个体区域搜索能力。其同化式与粒子群的进化式相似：

PNewcol=k1×Poldcol+k2×Pimp

(9)

其中：PNewcol为同化重新生成的殖民地；Poldcol为原始的殖民地；Pimp为殖民地所对应的帝国。k1和k2为控制参数，且k1+k2=1。k1可以体现殖民地本体继承和邻域搜索能力，k2可以体现帝国对殖民的控制约束。本文采用工序、机器双层编码，同化只针对工件工序排列组合，如图1所示。

图1 帝国同化殖民地

简单交换会出现冲突，图1中以帝国基因为基础，采用部分映射的方法消除冲突。新产生的殖民地可能会超越原有对应的帝国势力大小，像当年英国和美国关系一样，所以需要目标函数对其进行强弱估值。如果出现殖民地比帝国强大，将该殖民地与其对应帝国进行角色替换，该殖民地成为帝国，原来的帝国依附这个新的帝国。

2.1.3 帝国竞争机制

ICA通过竞争机制，迫使势力弱的帝国割舍殖民地给势力较强的帝国，不断蚕食势力弱的帝国，实现帝国的统一或少数帝国并立的结局。其算法关键在于弱势殖民地可以向其他帝国移动，不在局限于一个帝国内部搜索，在一定程度上增加了群体多样性，体现全局“勘探”能力。竞争机制要求根据各个帝国的势力大小选择最弱的帝国中最弱的殖民地作为一个竞争对象，转让给势力较大的帝国。帝国势力计算公式如下：

(10)

式(10)表示帝国与殖民地都会对其势力产生影响，其中α决定了殖民地对整个帝国的影响程度，一般取0.2。

2.2 帝国竞争算法的改进

2.2.1 自适应参数改进

在帝国竞争算法的同化操作和竞争规则中，固定参数设置会影响算法的局部“开采”和全局“勘探”能力，因此设计自适应优化参数[12]，使算法更好地求解车间调度问题。

帝国同化殖民地操作中，式(9)的k1和k2影响帝国对殖民地的同化。迭代初始阶段，为保证群体基因的多样性，设置参数k1较大，有助于殖民地进行区域搜索。随着迭代次数的增加，为保证收敛速度，使参数k2变大，有助于群体全局搜索。

帝国竞争过程中，通常设置一个竞争概率μ(0<μ<1)，然后由代码中的rands函数产生一个随机数与其比较，当随机数小于μ时才进行帝国竞争。μ的大小取值对算法的收敛速度和寻优搜索能力有很大影响：如果μ取值过大，则帝国竞争激烈，弱势帝国迅速减弱直至消亡，结果会导致帝国个数减少，算法的收敛速度过快，群体多样性降低，容易陷入局部最优；如果μ取值过小，则帝国竞争相对缓和，各帝国之间交流少，全局搜索能力下降，难以体现帝国竞争算法的关键核心。所以，算法对μ进行自适应调节设置：即迭代初期μ取值较小，削弱帝国竞争，提高邻域搜索能力；迭代中后期，μ不断增大直至为0.5，增加帝国之间交流并加速迭代收敛。

2.2.2 多变异改革策略

柔性车间问题具有高维复杂性，为防止ICA陷入局部最优，基于生物进化思想提出殖民地与帝国双改革的优化，针对车间调度编码特性提出多种改革方案[13]。为保证基本ICA流程中的同化与竞争机制，设计的双改革在竞争机制之后，且只保留优秀个体。

两种工件工序排列改革：

A1 随机选取一段工序，重新分配工序顺序；

A2 随机选取x个位置，交换位置基因。

结合双层编码结构，针对不同FJSP侧重点，提出三种使用机器基因的改革：

B1 完全继承原始使用机器基因；

B2 所有机器基因全部重新分配；

B3 被调整的工序的机器基因重新分配。

上述变异可产生6种改革方案：在算法初始阶段波动大，需要对其全局“勘探”能力优化，殖民地和帝国imp采用A1与B2/B3结合的改革方案；在迭代中期为加速收敛和提高搜索能力，采用A1/A2与B2/B3的改革方案；迭代后期，帝国与殖民地相似程度高，变异改革幅度与对结果影响成反比采取A2与B1/B3方案，加强局部“开采”能力，保证最优解的相对稳定性。

2.2.3 协作帝国算法

柔性车间调度是非线性多局部极值的问题，为此提出协作混合帝国竞争算法[14-15]。相当于几个大陆内部帝国不断竞争，大陆之间某些帝国签订一份公约，它们相互帮助共同获利。单独的大陆的内部帝国竞争随着迭代次数增加会丧失部分“勘探”能力，大陆公约制度会传递一些交流因子——优秀的帝国编码基因，帝国会与另一个大陆上的势力弱些的帝国进行交叉变异，或者取代实力最弱的帝国。对多个大陆之间全局最优进行比较，并根据目标函数去保留优秀的基因。这种交流机制能有效地促进算法的寻优，从而使各个大陆上的帝国相互协助，共同进化。

2.2.4 协作混合帝国算法流程

以最大完工时间最小化为目标值，结合上述对帝国算法的3种改进优化，算法最终流程如图2所示。

图2 协作混合帝国算法流程

图2中需要指出的是，在理想情况下，经过若干次迭代，各大陆统一，即各大陆仅存在一个帝国，此时算法达到终止条件。而在实际应用中，帝国之间不断竞争会导致几个国家势力相近，并始终存在直至达到规定的迭代次数才结束算法。

3 调度实例仿真

为验证本文提出的协作混合帝国算法对柔性车间调度的有效性和优越性，选取侧重点不同的6个FJSP实例运用Matlab工具进行实验研究。实验平台为：Windows 7系统，内存4 GB，处理器i5-CPU 3.3 GHz。

3.1 针对自适应参数的结果改进对比

选取车间实例模型为：10台机器，6个工件，每个工件6个工序，共36个工序。该FJSP侧重工件工序排列。表1为工件工序对应可以使用的机器；表2为工件工序对应使用的机器花费时长。

自适应参数ICA与一般ICA和改进遗传算法比较。实验参数：国家(种群)规模为100，帝国个数为10，帝国同化率为0.8，迭代次数为300。自适应参数设置为：第1～50次，k1=0.9，k2=0.1，μ=0.1；第51～100次，k1=0.8，k2=0.2，μ=0.2；第101～150次，k1=0.7，k2=0.3，μ=0.3；第151～300次，k1=0.6，k2=0.4，μ=0.5。实验独立运行10次。记录算法最优值(Best)、平均值(Mean)和标准偏差(STDEVP)。

表1 工件工序对应使用机器

表2 工件工序对应的机器工作时间

由表3得出，对于6×10问题，3种方法均可以求出最优解；但是从平均值和标准偏差的数据看，相比标准ICA和GA，自适应参数改进的ICA的平均值更好，稳定性更高，由此证明自适应参数改进对柔性车间调度有较好的影响。其中：t指的是所有工件工序加工完成后的总时间(无实际单位)。图3为此6×10调度的甘特图。

表3 自适应ICA与其他算法测试结果比较

3.2 针对多变异改革改进的结果对比

由文献[16-19]提出的4个实例：4×6、8×8、10×10和15×10，该类FJSP侧重工件工序使用机器的选取。设置算法基本参数为：国家(种群)是100，迭代300次。多变异改革策略设置如表4所示。

实验独立运行10次，将变异改革策略ICA与文献[16]的改进蚁群、文献[17]的两级遗传算法、文献[18]的IPSO(Improved Particle Swarm Optimization)和文献[19]的多规则遗传进行比较，结果记录于表5(最优值/平均值)。

由表5得出，算法对于4个柔性车间调度均可以取得最优值；但是由于4个实例中对工序机器选择权有较大范围，一般的种群变异不能有效寻求到最合适的使用机器，导致求解质量下降。而本文提出的变异改革策略针对ICA和车间调度流程设计，可以进行高效区域搜索，从表5中结果也可以看出其求解质量稳定性较高。图4为以上4个柔性车间问题的最优调度甘特图。

图3 6×10算例甘特图

Tab. 4 Multi-mutation reform strategy

表5 多变异改革ICA与其他算法测试结果比较

3.3 协作混合帝国算法

前面提到的5个实例，FJSP的侧重点不同，相对应的改进也不同。为了进一步贴合实际验证提出的协作混合帝国算法求解FJSP的有效性和稳定性，采用文献[20]的车间实例模型：8台机器6个工件，共26道工序。基础参数与其保持一致，即：种群总规模为100，并设置15个帝国。

为体现协作混合帝国算法的优越性，按照文献[20]要求将协作混合帝国算法独立运行30次，并与文献[21]的改进双层粒子群优化(Improved Two-Layer Particle Swarm Optimization, ITLPSO)算法、文献[22]的改进量子粒子群优化(Opposition-Based Learning Quantum-behaved Particle Swarm Optimization with Bounded mutation, OBL-QPSOB)算法、文献[20]的骨干双粒子群优化(Double Bare Bones Particle Swarm Optimization, DBBPSO)算法进行比较。图5为协作混合帝国算法的30次收敛曲线。表6为测试结果记录算法最优值(Best)、平均值(Mean)。

表6 协作混合帝国算法与其他算法测试结果比较

由文献[20]得知3种改进粒子群算法每次迭代4 000次，且只有DBBPSO存在解收敛于最佳值53。对比图5协作混合帝国算法的30次平均结果收敛图，其具有较高的收敛速，(迭代1 000次后不会出现明显变异，即本算法只迭代1 000次)，而且多数平均值都收敛于最优值附近，具有较高收敛精度和稳定性。同时表6中数据也可以表明协作混合帝国算法求解结果的质量和稳定性均为最优。图6显示一组最优解对应调度甘特图。

图4 4个实例的甘特图

图5 协作混合帝国算法的平均结果收敛曲线

4 结语

针对求解柔性车间调度(FJSP)算法的易早熟与波动性大的问题，提出一种协作混合帝国算法。该算法为增强全局“勘探”能力和局部“开采”能力，提出自适应参数、多变异改革策略和协作交流机制3种改进方式。通过对6个柔性车间调度实例仿真对比，结果可以证明所提改进算法具有区域探索能力强易于寻最优值、收敛速度快、求解结果稳定性高的特点，对实际调度生产问题具有一定指导作用；但是，本文仅探究单目标的FJSP求解，后续工作将会运用协作混合帝国算法求解多目标FJSP。

图6 车间实例[20]模型调度甘特图