基于蚁狮算法求解柔性作业车间调度问题的研究

王彦杰，向凤红

（昆明理工大学 信息工程与自动化学院，云南 昆明 650000）

0 引 言

生产调度的出现，使人们脱离了原始的生产模式，解放了劳动力。但随着社会的发展，单一的生产调度模式已经不符合人们日益增长的需求，需寻求更加符合实际生产模式，可以有效解决此类问题的方法[1]。柔性作业车间调度问题（Flexible Job Shop Scheduling Problem，FJSP）[2]符合现代多变、复杂的生产环境，解决此类问题变得困难。因此众多学者对其的关注度越来越高。

伴随着智能时代的来临，对于柔性作业车间调度问题的研究过渡到运用智能算法解决该问题。算法的出现可以极大程度地解决复杂性强、问题规模大的FJSP问题，为解决这一问题提供了工具。SINGH[3]等在传统粒子群算法中引入量子行为策略，根据该策略的特点，提出了混合量子行为粒子群算法求解FJSP问题；乔兵[4]等在遗传算法中设计了新的基因编码方式，对不合法以及不合理基因进行重新设计，极大程度地增加优秀基因的出现，在此基础上解决FJSP所出现的问题，使收敛速度加快；贺仁杰[5]等利用不同种群之间的进化方式以及调整参数设置来推演优秀种群的演进过程，并且根据种群之间的不同方式的演进过程和资源竞争，达到种群之间的信息共享，来推动算法整体的进化，提出用知识型协同进化算法求解FJSP问题；MASTROLOLLI[6]等利用禁忌搜索算法与新领域结构相结合的方式，增加了求解FJSP问题时算法搜索的效率与范围，避免了算法过早陷入局部最优。

对于柔性作业车间调度问题的研究方法，主要是利用智能算法模拟实际生产，找寻最好的调度方案。但这些算法已被广泛地使用，无法达到研究课题的创新性。目前，国内外尚无人证明蚁狮算法求解FJSP问题的可行性。基于蚁狮算法具有种群多样、寻优与适应性强、调节参数少、求解与收敛精度高以及不受研究对象约束等各方面的优点，本文使用蚁狮算法（Ant Lion Optimization，ALO），尝试解决以最小最大完工时间为目标的FJSP问题，对实验结果进行分析。

1 柔性作业车间调度

1.1 问题描述

FJSP包括两个子问题，一是对加工工序进行合理的机器分配，二是对在所选加工机器上进行不同加工工件的加工工序进行紧前紧后安排。具体描述如下：柔性作业车间调度问题是n个工件 (j1,j2,j3,…,jn)可以在m台机器(m1,m2,m3,…,mn)上加工，工件i(i=1,2,3,…,n)有qi道工序，每道工序所用的加工时间为t，允许工序可以在多个机器上进行加工操作，根据所选择的加工机器的不同，加工时间也不同。调度问题研究的实质就是解决工件工序是否可以在某几台机器上加工，根据选择加工机器的不同，所产生的加工时间也不同。为实现最理想化的生产，为工件的工序进行安排以及选择合适的加工机器，是整个调度方案的重点。Oij表示工件i的第j道工序；Mij表示工件i的第j道工序的可选工序集，Ri为每个工件的释放周期，Di为每个工件的交货期；Tijk表示工序Oij在机器k上的加工时间；Pij表示工序Oij的加工结束时间。在建立问题模型之前，需要对加工过程进行条件约束，具体如下：

（1）机器在某时刻有且只有一个工件可以进行加工操作；

（2）工件工序加工在某时刻只能选择一台机器进行加工操作；

（3）工件工序加工开始就不会停止，直到该工件工序完成加工；

（4）所待加工的工件，在选择加工时无主次之分，仅根据调度方案安排工件的加工；

（5）相同工件的不同工序需考虑加工先后顺序。

为了帮助读者更好地理解，本文对文中所用符号进行定义，具体如表1所示。

表1 本文所用符号定义

1.2 模型建立

为证明蚁狮算法求解柔性作业车间调度问题的可行性，本文建立以最小最大完工时间Cm为优化目标的单目标柔性作业车间调度模型。数学模型表示为：

具体约束条件如下。

（1）对于加工过程的约束，每个工件的每道工序一旦加工开始就不能中断，如式（2）所示：

（2）确认是否可以在机器k上进行加工。式（3）为0-1决策变量，若工件i的第j道工序可以在机器k上加工，则，否则。

（3）工件的不同工序之间在加工时有着紧前紧后关系，如式（4）所示：

（4）Cij表示工件i的第j道工序开始加工时间，与在机器k上的加工时间Tijk之和不得超过工序Oij的结束加工时间Pij，如式（5）所示：

（5）工序Oij的加工结束时间要小于等于Oi(j+1)道工序的起始加工时间Ci(j+1)，如式（6）所示：

（6）工件的结束加工的时间Pj要小于调度方案最大完工时间Cm，如式（7）所示：

（7）某工件的所有工序可以在相同的机器上进行加工操作，如式（8）所示：

式中：Yijk表示工件i的第j道工序在机器k上的加工操作在机器k+1之前，Xijk表示工件i的第j道工序是否可以在机器k上加工。Yijk与Xijk都是0-1决策变量。

2 基于蚁狮算法求解单目标柔性作业车间调度问题

2.1 蚁狮算法

蚁狮优化算法（ALO）[7]是通过模拟自然界中一种生物——蚁狮狩猎蚂蚁的行为，来实现对目标函数优化问题的求解。借助于蚁狮周边蚂蚁的随机游走，保证该算法的全局搜索能力。与粒子群等算法不同，ALO算法有蚁狮和蚂蚁两个种群，通过蚁狮对蚂蚁的捕获，实现种群的进化。ALO算法具有求解精度高、调参少等优点，得到了广泛的应用[8-9]。蚁狮算法具有蚂蚁的随机游走机制、陷阱对蚂蚁随机游走的影响、蚁狮的捕获方式、捕获蚂蚁后重筑陷阱以及精英更新等机制，故ALO算法在多个领域得到应用[10-12]。但无人证明其求解FJSP问题的可行性，故本文首次尝试使用蚁狮算法求解柔性作业车间调度问题，证明其可行性，并分析问题，为下一步改进做准备。

2.2 编码解码

2.2.1 编码

由于传统的FJSP问题只考虑工件工序的加工顺序，故一般只是对工件工序进行设计编码，但是FJSP调度问题不仅要设计工序的加工方案，使其合理安排加工，不会出现因加工顺序安排出错导致加工冲突的事件发生，还要根据约束以及调度方案为每道工序设计合理的可加工机器，避免机器利用率不高以及加工工序在机器上加工时出现冲突的情况发生，因此仅对工序进行编码设计无法达到合理安排以及解决问题的目的。因此，本文使用基于工序和机器的双层实数编码方法。该编码针对工序以及加工机器两部分进行编码设计，合理解决加工工序间和机器间的冲突以及机器利用率不够的问题，且最终得到正确可行的调度解。

例如，图1显示了扩展的基于工序和机器的双层整数编码方式所产生的染色体。为便于读者理解，提出一个3×5的MOFJSP例子。现有工序集为O1={O11,O12,O13}，O2={O21,O22}，O3={O31,O32,O33}；机器集为M={M1,M2,M3,M4,M5}。该编码表示工件2的第1道工序可以在机器4上加工，工件1的第1道工序可以在机器3上加工，其表示的序列为：(O21,M4)，(O11,M3)，(O31,M1)，(O12,M1)，(O32,M2)，(O13,M5)，(O22,M2)，(O33,M5)。其中，基于工序编码方案基因是确定具体合理的工件工序的加工安排；基于机器编码方案是根据约束与调度方案安排合理的可加工机器，且机器与工序基因长度相呼应。

图1 扩展的基于工序和机器双层编码方式

2.2.2 解 码

解码是对设计的编码信息以及编码规则所形成的调度方案，利用甘特图的形式，清晰地看出是否合理地安排加工过程，根据甘特图所表示出来的问题进行进一步修改，直到找寻到最佳的调度方案，且不同的解码设计方案会产生不同的调度解，影响着最终调度结果的优越性。因此本文利用插入式贪婪算法，根据编码信息以及编码规则进行解码操作。具体过程为：找寻到加工机器的空闲时间，判断在该机器加工空闲时间里是否可以加工其他工件的工序。利用插入式贪婪算法对图2编码方式进行解码，可得到可行解的甘特图，其中图2编码方式的加工时间为[4，3，7，2，6，8，3，5]。如图2所示，机器5上共可以加工两道工序即O13与O33，判断工序O13后是否有空闲时间可将工序O33前插进行加工操作；机器2可加工两道工序O32与O22，判断O32之后有无大面积的空闲时间将工序O32后插进行加工操作，这种操作可以使机器之间利用均衡，达到理想的加工效果。

图2 基于插入式贪婪算法解码得到的甘特图

3 仿真实验分析

本文使用Matlab 2014b进行编程，操作系统为64位 Windows10，处 理 器 为Intel（R） Core（TM） i5-6200U CPU 2.40 GHz，内存4 GB。算法参数设置种群大小为100，迭代次数为200次。以Brandimarte基准算例中的MK01算例进行实验验证和分析。Brandimarte基准算例由MK01-MK10共计10个测试算例组成，算例均是在给定取值范围中均匀且随机分布生成，所需要加工的工件数根据算例的不同有10到20个不等，机器数也不同，有4到15个不等。初步使用MK01算例求解该问题。收敛迭代图如图3所示，实验结果甘特图如图4所示。

图3 收敛迭代图

图4 甘特图

从图3迭代收敛图可以看出，蚁狮算法可以求解柔性作业车间调度问题，但第一次迭代时，得出的最优解为65，说明蚁狮算法随机生成的初始种群在解决单目标柔性作业车间调度问题时的质量不好。从全局看，该算法迭代160次左右时才求得最优值，算法的收敛速度较慢。算法在40代到135代之间共有100代左右，最优值长时间处于55，逃离局部最优的能力较弱，减缓了算法的收敛速度。从加工时长来看，蚁狮算法在MK01算例的加工环境中，完成加工所花费的最小最大完工时间较长，为55。从图4柔性作业车间调度甘特图来看，5号机器利用率极低，只有工件5的第1道工序和工件3的第5道工序这两道工序在该机器上进行加工操作；而4号机器的加工空闲时间较多，没有充分利用。

4 结 语

本文尝试使用蚁狮算法求解单目标柔性作业车间调度问题，通过实验验证发现，蚁狮算法可以求解柔性作业车间调度问题。在实验分析中，尽管蚁狮算法可以应用在解决此问题上，但根据实验分析发现，还是会出现随机生成的初始种群质量不好、算法的收敛速度较慢、逃避局部最优能力较弱、完成加工所花费的最小最大完工时间较长、加工机器利用率低以及加工空闲时间较多等问题。下一步的工作是尝试改进蚁狮算法，设计一种混合策略以优化初始化种群，使初始种群的质量变佳；引入遗传算法中的交叉变异策略，提高迭代过程中的收敛与择优能力，降低局部最优的发生。