1、【214】第45卷 第02期 2023-02收稿日期：2021-03-30作者简介：李凯（1978-），男，湖北武汉人，硕士，研究方向为航空发动机柔性加工控制系统。基于改进粒子群算法的智能排产研究Research on intelligent scheduling based on improved particle swarm optimization李 凯1*，肖 熙2，董山恒3，宋 旭2LI Kai1*，XIAO Xi2，DONG Shan-heng3，SONG Xu2（1.南京理工大学 自动化学院 南京 210014;2.中国航空规划设计研究总院有限公司 北京 100032;3.北京机
2、械工业自动化研究所有限公司，北京 100120）摘 要：车间的排产对于提高车间的生产效率至关重要，尤其对于柔性机加车间，智能排产可以极大提高加工的自动化与智能化水平。排产问题已经被证实是一个NP-hard问题，以最小化最大完工时间为目标，构建了柔性机加车间排产问题的数学模型，并提出了一种改进的粒子群算法对模型进行求解，在标准粒子群算法的基础上增加了变异和局部搜索的步骤，既减少了算法陷入局部最优的概率，又提高了算法的求解精度。并利用某航空发动机的柔性机加生产线验证了模型和算法的有效性。关键词：智能排产；粒子群算法；柔性加工中图分类号：V263.1+1 文献标志码：A 文章编号：1009-0134
3、(2023)02-0214-030 引言计划排产长期以来都是生产调度的难题1，随着制造业的快速发展，尤其是柔性加工在车间的兴起，传统的排产方法已不能满足调度快速响应的需求，在此背景下，智能排产逐渐替代了传统排产。智能排产2就是在工艺约束和资源约束等条件下，利用智能算法对加工任务进行快速合理的分配，具有很强的工程实用价值。高效的智能排产可以极大地减少企业的时间成本、人力成本，是提高企业生产效率、增强企业竞争力的关键因素。国外学者Fisher3在1963年首次提出排产调度问题，随着实际生产复杂度的不断提高，该问题在学术界的关注度逐渐增加。这类问题属于NP-hard问题，其求解的方法主要有两种：其一
4、对于小规模的问题，采用精确算法进行求解，如分支定界、动态编程等。这些方法在解决小规模问题是具有很好的效果，但是在解决大规模问题时需要花费大量的计算时间；其二用近似或者启发式的求解算法对该类问题进行求解，这些方法可以克服精确求解时计算时间长的缺点，并且可以在有限时间内找到高质量的解，如拉格朗日松弛法、禁忌搜索算法等，这些方法对于改善求解质量也取得了很好的效果。随着启发式算法的不断应用，越来越多的学者提出利用智能算法对排产问题进行求解，张昕4提出了一种改进的遗传算法用于解决车间的排产调度问题，宋代立5等人利用蚁群算法（Ant Colony Optimization,ACO）求解混合流水线车间的调度
5、问题，Suresh6等人提出利用模拟退火算法（Simulated Annealing,SA）求解车间的排产问题，Lian7等人利用粒子群算法（Particle Swarm Optimization,PSO）求解车间排产问题。这些智能算法可以在有限时间内找到一个合理的解，但是，每种智能算法都有其自身的优势和缺点。其中一些方法可以达到很好的求解效果，但是需要大量的工作，其性能的优劣很大程度取决于初始参数的选择。PSO算法模拟了自然界中鸟群的觅食行为，利用种群的分布和协助快速找到食物，PSO算法的优点就是容易实现、具有较高的鲁棒性、并能够快速收敛，但是粒子群算法容易陷入局部最优解。针对排产问题和粒子
6、群算法的特点，本文构建了柔性机加生产线的排产模型，并提出了一种改进的粒子群算法进行求解，既能保证算法的求解速度，又能提高算法的求解精度。1 问题描述及建模1.1 问题描述柔性机加车间属于典型的离散加工行业，其排产问题可以描述为：现在有A种产品共n个待加工工件，需要在k台机器上加工，每个工件有对应的加工时间，在一定的约束条件下使得所有工件的加工时间最短。在上述问题中，工件集、机器集、工件加工时间集都用矩阵表示，其中，工件任务集P=p1,p2,pn，pi表示第i个工件（i=1,2,n）；机器集M=m1,m2,mk，mj表示第j台机床（j=1,2,k），工件加工时间集T=t1,t2,tn，ti表示第
7、i个工件的加工时间。1.2 约束分析将实际生产中的调度排产问题转换为可以用来使用及行业通用的理想化模型，需要对实际问题中存在的客观影响和约束进行分析，因此，本文对车间的排产调度问题建立了相应的约束，并做了如下假设：1）每台机器在同一时间段内只能加工一个工件；2）每个工件的加工的工艺路线已知；3）在初始加工时刻，所有工件均可以被加工；第45卷 第02期 2023-02【215】在排产的过程中不考虑设备发生故障，所有进行中的加工任务不会被中断。1.3 问题建模基于以上分析，我们以最小化最大完工时间为目标，构建柔性机加车间的排产模型，具体表达如下所示：MinCmax=Minmax(Ci)=Minma
8、x(Si+ti)(1)其中，Cmax表示所有工件的最大完工时间，Ci表示工件i的完工时间，Si表示工件i的开始加工时间，ti表示工件i的加工时间。2 求解算法设计2.1 粒子群算法PSO算法是Kennsdy和Eberhart8基于鸟类捕食行为提出的一种缘起法算法。在PSO算法中，每一个粒子在求解空间内不断移动，每个状态都代表了问题的一个潜在解。每个粒子在空间中的速度决定了粒子移动的方向和移动的距离，每个粒子会根据自身和其他粒子的运动动态调整自己的速度，从而实现在可行解空间的个体最优。每个粒子的特性由三个指标确定：粒子的位置，粒子的速度和适应度值。适应度的值决定了粒子所对应解质量。在可行解空间中
9、，粒子根据式(2)和(3)更新自己的速度和位置：(2)11kkkiiixxv+=+(3)其中，k是迭代次数的索引；vki和xki分表示粒子i在第k次迭代时的速度和位置；pibest是粒子i的个体最优解；pgbest表示全局最优位置，可以被任何粒子搜索到；w是惯性权重，r1和r2服从0到1之间的随机分布；c1和c2是粒子学习的加速系数。2.2 编码与解码本文采用遗传算法的编码方法，将每个机器上加工的工件序列编码为一个染色体，每个基因在染色体中出现的位置就表示了该工件在某台机器上的加工的顺序。如每个染色体编码为3,6,2,7,9，则表示在该机床上加工的工件序列为3、6、2、7、9。2.3 变异因为
10、粒子群算法的缺点是容易陷入局部最优解，所以本文结合遗传算法中基因变异的特性，以一定的变异概率对粒子编码进行变异操作，具体步骤如下：1）随意选择任意两个粒子；2）将它们的位置进行交换，并计算交换后的适应度函数；3）比较交换后的适应度值，更新个体最优解和全局最优解；4）以一定的概率接受更新后的最优解。2.4 局部搜索为了进一步克服粒子群算法容易陷入局部最优解的缺点，每次粒子更新位置后，我们都进行一次局部搜索操作，从而提高算法的求解精度，具体操作如下：1）选取适应度前5%的个体和其他任意15%的个体；2）随机产生三个整数d1、d2、d3，其中，d1服从0到1之间的均匀分布，d2和d3的值位于1和基因
11、长度l之间；3）如果d10.5，则被选中的个体向前搜索d2个位置，反之则向后搜索d3个位置；4）计算搜索后的适应度值；5）比较重新计算后的适应度值，并更新最优解。2.5 算法步骤结合上面的分析，本文用改进的粒子群算法求解柔性车间的调度问题，具体的步骤如下：Step1：确定粒子群算法的初始参数；Step2：给定初始解并计算适应度值，并确定个体最优解和全局最优解；Step3：按照式(1)和式(3)更新每个粒子的速度和位置；Step4：执行变异操作，计算适应度值，更新个体最优解和全局最优解；Step5：执行局部搜索操作；Step6：计算适应度值，并更行体最优解和全局最优解；Step7：判断是否满足算
12、法的终止条件，如果满足则结束算法，否则，转入Step3，继续进行计算。3 案例验证3.1 参数选择在粒子群算法中，惯性权重w，加速系数c1和c2对算法的性能有很重要的影响，所以选择一个合适的参数对于问题求解质量至关重要。我们通过固定其他参数，改变某一个参数的值，并在测试集上运行，最后确定c1的值是0.8，c2的值是1.2。惯性权重w对粒子的搜索能力有很大的影响，一个较大的惯性权重值有利于粒子的全局搜索，一个较小的惯性权重有利于粒子的局部搜索。所以，理想的惯性权重值应该在算法开始时比较大，随着算法迭代次数的增加，其值不断减小。为了平衡算法的全局搜索能力和局部搜索能力，本文按照式(4)确定算法的惯
13、性权重值。2max()()kstartstartendkwwwwT=(4)其中，startw是初始惯性权重值，endw是最大迭代次数时的惯性权重值，k是当前的迭代次数，Tmax是最大迭代次数。【216】第45卷 第02期 2023-02此外，算法其他相关的参数如下：算法的最大迭代次数MaxIt=500；种群规模PopSize=50。3.2 案例验证为了验证本文构建模型和算法的有效性，选取了某航空发动机柔性机加生产线作为实例验证。该车间有3种工件共20个任务需要在4台机床上进行加工，每种工件的加工工艺和每个工序的加工时间已知。3.3 结果分析基于上面提出的数学模型和改进的粒子群算法，本文将3.2
14、中的案例进行编码设计与模型构建，并在MATLAB上进行运算，具体结果如下图1和图2所示。图1 车间排产甘特图图2 车间排产算法迭代图由上图可知，通过本文提出的算法对车间现有问题进行求解，得到的结果是116min，按照车间现有的排产方法完成该案例中的零件加工需要324min，因此，本文提出的模型和算法具有较好的求解表现，可以用于指导实际生产。4 结语本文构建了柔性机加车间的排产调度问题的数学模型，并提出了一种改进的粒子群算法对模型进行求解，既保留了标准粒子群算法收敛速度快的特点，又改进了其容易陷入局部最优解的缺点，并通过实际案例验证了本文构建的模型和算法的有效性。参考文献：1 王明星,李利民.改
15、进的遗传算法在机加车间排产优化的研究J.制造业自动化,2014,36(15):34-37.2 周原令,胡晓兵,江代渝,李航.基于改进NSGA-II的车间排产优化算法研究J/OL.计算机工程与应用:1-92021-01-16.3 Fisher H.Probabilistic learning combinations of local job-shop scheduling rulesJ.Industrial scheduling,1963:225-251.4 张昕.改进的遗传算法在车间作业调度中的应用研究J.国防制造技术,2013(02):44-47.5 宋代立,张洁.蚁群算法求解混合流水车间
16、分批调度问题J.计算机集成制造系统,2013,19(07):1640-1647.6 Suresh R K,Mohanasundaram K M.Pareto archived simulated annealing for job shop scheduling with multiple objectivesJ.The International Journal of Advanced Manufacturing Technology,2006,29(1-2):184-196.7 Lian Z,Jiao B,Gu X.A similar particle swarm optimization algorithm for job-shop scheduling to minimize makespanJ.Applied mathematics and computation,2006,183(2):1008-1017.8 Kennedy J.Particle Swarm OptimizationC/Icnn95-international Conference on Neural Ne
