改进人工免疫算法求解柔性作业车间调度问题

张永强， 高锐敏

(1.河南财经政法大学 计算机与信息工程学院 河南 郑州 450002；2.河南牧业经济学院 基础部 河南 郑州 450044)

改进人工免疫算法求解柔性作业车间调度问题

张永强1， 高锐敏2

(1.河南财经政法大学 计算机与信息工程学院 河南 郑州 450002；2.河南牧业经济学院 基础部 河南 郑州 450044)

柔性作业车间的合理调度是提高生产效率和效益的关键，为了解决柔性作业车间调度问题求解过程中的难题，提出一种改进人工免疫算法的柔性作业车间调度方法.首先对当前柔性作业车间调度的研究现状进行分析，然后基于总加工时间最短构建数学模型，采用人工免疫算法进行求解，并针对标准人工免疫算法存在的不足，引入粒子群算法保持种群的多样性，以避免出现局部最优解，最后采用标准算例集对算法的性能进行仿真测试.结果表明，相对于其他算法，改进人工免疫算法获得了较优的柔性作业车间调度方案，尤其在解决大规模问题时，优势更加显著.

柔性车间调度； 人工免疫算法； 粒子群优化算法； 变异算子

0 引言

随着生产制造市场化的加剧，生产资源并不是可无限利用的，单从每道工序的加工时间来讲也往往不是一成不变的，这便形成了生产过程的柔性.柔性作业车间调度问题(flexible job-shop scheduling problem，FJSP)应运而生，其更加符合实际的生产情况，但是也增加了问题的复杂性[1].FJSP是一种典型的组合优化问题，属于非确定性多项式(non-deterministic polynomial,NP)难题，一直是生产制造业领域研究中的重点和难点[2].

针对FJSP问题，大量学者和研究人员投入了许多时间和精力进行深入研究，取得了一些研究进展，提出许多FJSP问题求解算法[3].当前FJSP问题的求解算法大致可分为3类：精确求解算法、启发式算法和人工智能算法.分支定界法是最为经典的精确求解算法，其简单、易实现，对于小规模FJSP问题，求解效率高；然而随着生产制造业规模的不断壮大，加工产品规模越来越大，分支定界法难以满足现代生产制造业的FJSP问题求解要求[4].

启发式算法最具代表性的为拉格朗日松弛法，其对小规模FJSP问题求解效率高，但是存在精确求解算法一样的缺陷，应用范围受限[5].人工智能算法主要通过模拟自然界的生物群体行为，具有并行性、搜索速度快等优点，在FJSP问题求解中应用最广，成为当前主要的研究方向[6].

一些学者采用遗传算法、模拟退火、微粒群优化算法、蚁群算法、萤火虫算法对FJSP问题进行求解，获得了比较好的效果[7-9].然而在实际应用中，这些人工智能算法均存在各自不足，如后期收敛速度慢、易获得局部最优解等.相对于其他进化算法，人工免疫算法(artificial Immune algorithm，AIA)具有较好的全局搜索能力，己经在云计算资源调度、机器人路径规划等领域成功应用[10]，为解决FJSP问题提供了新的研究工具.

为获得更加理想的FJSP问题优化方案，降低生产制造业生产成本，本文提出一种改进人工免疫算法(modified artificial immune algorithm，MAIA)的FJSP问题求解方法，并采用一些标准算例对算法的性能进行测试.

1 FJSP的数学模型

FJSP的目标函数为：

式中的相关参数定义见文献[11] .

2 改进人工免疫算法求解FJSP

2.1 人工免疫算法

人工免疫算法是一种受生物免疫系统启发的算法，相对其他算法更简单、易实现，比较适合于FJSP问题的求解，其工作流程如图1所示[12].

2.2 人工免疫算法的改进

粒子群优化(particle swarm optimization，PSO)算法，相对于其他进化算法如遗传算法，易于实现﹑调整参数少，在许多领域得到了广泛应用.第i个粒子位置表示为向量Xi=(xi1,xi2,…,xiD)，第i个粒子历史最优位置为Pi=(pi1,pi2,…,piD)，整个粒子群历史最优位置为Pg=(pg1,pg2,…,pgD)，第i个粒子的速度为向量Vi=(vi1,vi2,…,viD)，每个粒子的位置按如下公式进行变化：

其中:c1,c2为正常数，称为加速常数；rand ()为[0,1]之间的随机数；ω为惯性权[13].

AIA算法到了后期，易使种群多样性降低，出现局部最优解概率大.为此，本文融合了粒子种群优化算法与人工免疫算法的优点，将PSO算法引入到抗体优化过程中，提出一种改进人工免疫算法.

为了测试本文对AIA改进的有效性，采用标准函数测试AIA和MAIA的性能 .

f2(x)=exp(-(x1-4)2-(x2-4)2)+exp(-(x1+4)2-(x2-4)2)+

对于上述函数，AIA和MAIA的求解结果如图2所示.对图2的结果进行对比与分析，可以发现，改进后算法优点体现在：MAIA的求解效率明显加快，求解的精度更高，较好地解决了AIA算法存在的难题 .

图2 人工免疫算法改进前后性能对比

2.3 求解FJSP的改进人工免疫算法设计

2.3.1 初始化种群 采用随机方式产生初始种群，产生的种群对应着初始工序分配方案，而且满足各个工件的所有工序的执行顺序.

2.3.4 变异算子 在免疫算法中，抗体变异率的选择需要兼顾种群的多样性和最优解的稳定性 .本文采用基于亲和度的变异率，即当亲和度越大，搜索空间越小，反之则搜索空间越大，从而实现了自动调节各代抗体的搜索空间.假设k为当前迭代次数，自适应变异率为

式中：P为初始变异率；G为总迭代次数；fmax(k)为第k代抗体的最大亲和度；fmax为前k代抗体的最大亲和度；pl为变异调节因子.

3 MAIA在JSP问题中的应用实例

3.1 仿真参数

为了全面测试MAIA算法的性能，在Intel 双核 2.85 GHz的CPU，4GB的RAM，Windows XP的个人计算机上，采用VC++语言编程实现算法.在标准算例集XWdata[14]中选取8工件8机器、10工件10机器以及15工件10机器的3个不同规模问题进行仿真测试.

为了使本文的结果更具说服力，选择粒子群优化算法(PSO)、遗传算法(GA)、基本人工免疫算法(AIA)进行对比实验.粒子群优化算法参数设置为：学习因子c1=c2=2，种群大小为20；遗传算法的参数设置为：交叉概率为Pc=0.85，变异概率为Pm=0.01，种群大小为20；改进人工免疫算法的参数设置为：初始变异率p=0.95；种群大小为10.

3.2 结果与分析

3.2.1MAIA的求解结果MAIA对3组算例仿真结果的甘特图如图3～图5所示.从图3～图5可知，MAIA可以对FJSP问题进行有效求解，获得十分理想的柔性车间调度方案，优化结果可以为生产制造业提供有价值的参考意见，有利于企业提高生产效率，降低成本，创造更多的利润.

图3 8×8的 JSP 求解结果

图4 10×10的 JSP 求解结果

图5 15×10的 JSP 求解结果

3.2.2 与其他算法性能对比 MAIA、AIA、PSO、GA的20次仿真实验的结果如表1所示，主要统计找到最优的解次数及相应的迭代次数.从表1可以看出，对于8×8问题、10×10问题以及15×10问题， MAIA得到最优解成功次数显著高于对比算法.而且得到最优解的迭代次数相对较少，综合性能要优于对比算法.对比结果表明，MAIA具有种群规模小、迭代次数少的优点，在解决大规模问题时，具有较好的稳定性和收敛性.

表1 不同算法的算例集实验结果对比

图6 算法的平均CPU时间对比Fig.6 Average CPU time of the above algorithm

3.2.3 求解效率对比 为了测试所有算法对柔性作业车间调度问题的求解效率，采用平均执行时间作为性能评价指标，所有算法平均执行时间统计结果如图6所示.从图6可以清楚看出，相对于其他算法，MAIA的平均CPU时间最短，求解速度最快，大幅度提高了FJSP的求解效率，可以满足大规模制造业的FJSP优化要求，这主要是由于MAIA集成了人工免疫算法和粒子群算法全局搜索能力优点，可在较短时间内得到满意解.

4 结束语

柔性作业车间调度通常面临多个相互矛盾的优化目标，有多个条件约束.针对柔性车间调度问题，融合了粒子种群优化算法与人工免疫算法的优点，提出一种改进人工免疫算法的FJSP求解方法，将粒子群优化算法作为算子嵌入人工免疫算法中，增加了种群的多样性，避免陷入局部最优问题出现.通过标准算例集XWdata对算法性能进行测试，并与其他智能算法进行对比仿真实验.结果表明，MAIA较好地克服其他人工智能算法存在的缺陷，加快了问题的寻优速度，可在较短时间内得到满意解.仿真实验结果证明了本文算法的有效性和优越性.

[1] 曾强, 沈玲, 潘启东, 等. 批量生产柔性作业车间多目标精细化调度方法[J]. 计算机工程与应用, 2014, 50(2): 263-270.

[2] GUO Y D, LUN S X. Flow shop scheduling problem with partial skill flexibility of workers[J]. Journal of Bohai university, 2013, 34(2):232-236.

[3] FENG M Y. A grouping particle swarm optimization algorithm for flexible job shop scheduling problem[C]∥ Proceedings of IEEE Pacific-asia Workshop on Computational Intelligence and Industrial Application. Wuhan, 2008: 332-336.

[4] RUIZ R, VAZQUEZ R J A. The hybrid flow shop scheduling problem[J]. European journal of operational research, 2010, 205(1): 1-18.

[5] KAHRAMAN C, ENGIN O, KAYA I, et al. Multiprocessor task scheduling in multistage hybrid flow-shops: a parallel greedy algorithm approach[J].Applied soft computing, 2010, 10(4): 1293-1300.

[6] ZHANG G H,ZHANG L J,WANG Y C,et al. An effective hybrid particle swarm optimization algorithm for flexible job-shop scheduling problem[J]. The open automation and control systems journal, 2014,6(1):1604-1611.

[7] 王长明, 聂建军. 基于遗传算法的二次曲面提取技术研究[J]. 郑州大学学报(理学版),2013,45(1):65-68.

[8] 刘长平, 叶春明. 置换流水车间调度问题的萤火虫算法求解[J].工业工程与管理,2012,17(3):56-59.

[9] 宋雪枫, 融合蚁群算法和遗传算法的矩形件排样问题研究[D]. 郑州:郑州大学, 2011.

[10] 唐建平, 宋红生, 王东署. 一种移动机器人动态环境下的路径规划[J]. 郑州大学学报(理学版), 2012, 44(1): 75-78.

[11] 薛宏全, 魏生民, 张鹏, 等. 基于多种群蚁群算法的柔性作业车间调度研究[J]. 计算机工程与应用, 2013, 49(24): 243-248.

[12] 申丽君, 刘丽, 陆锐, 等. 基于改进免疫进化算法的云计算任务调度[J]. 计算机工程, 2012, 38(9): 208-210.

[13] 宋存利. 求解柔性作业调度问题的协同进化粒子群算法[J]. 计算机工程与应用, 2013, 49(21): 15-18.

[14] ALVAREZ V R,FUERTES A, TAMARIT J M,et al. A heuristic to schedule flexible job shop in a glass factory [J]. European journal of operational research, 2005, 165(2):525-534.

(责任编辑：王浩毅)

Flexible Job-shop Scheduling Problem Solved by Improved Artificial Immune Algorithm

ZHANG Yongqiang1,GAO Ruimin2

(1.SchoolofComputerandInformationEngineering,HenanUniversityofEconomicsandLaw,Zhengzhou450002,China;2.DepartmentofBasicCourse,HenanUniversityofAnimalHusbandryandEconomy,Zhengzhou450044,China)

A novel flexible job shop scheduling method based on improved artificial immune algorithm was proposed. Mathematical model of the flexible job shop scheduling was established, and the total shortest processing time was taken as the objective function.The particle swarm optimization algorithm as the operator was embedded into artificial immune algorithm to maintain the diversity of population and prevent obtaining local optimal solution. The performance of the algorithm was tested by simulation experiments on standard set. Results showed that compared with other algorithms, the proposed algorithm could obtain better flexible job shop scheduling scheme, especially large-scale problems.

flexible job-shop scheduling; artificial immune algorithm； particle swarm optimization algorithm； mutation operator

2015-11-27

国家自然科学基金资助项目(61202285)；河南省科技攻关项目(132102210501).

张永强(1972—)，男，河南唐河人，副教授，主要从事智能推荐、软件工程研究；E-mail: zyq0371@sina.com．

张永强，高锐敏.改进人工免疫算法求解柔性作业车间调度问题[J].郑州大学学报(理学版)，2016,48(2):53-57.

TP301

A

1671-6841(2016)02-0053-05

10.13705/j.issn.1671-6841.2015288