基于混合粒子群算法的航空零件生产车间柔性调度研究

ComputerKnowledgeandTechnology电脑知识

与技术

计算机工程应用技术本栏目责任编辑：梁书

第6卷第7期(2010年3月)基于混合粒子群算法的航空零件生产车间柔性调度研究王超1,张永强2，史峰2（1.95959部队，北京100076；2.94565部队，安徽蚌埠233000）摘要：航空零件生产车间调度具有目标多样性和不确定性问题，普通方法难以求得最佳调度顺序。针对这个问题，采用了混合粒子群算法优化加工工序。该算法通过个体交叉，变异的方法来反复迭代寻优，从而得到更好的零件加工工序。通过仿真实验验证了该算法的有效性，从而为航空零件加工车间调度优化提供了一种新的思路。

关键词：航空零件；模糊目标；柔性；车间调度；混合粒子群中图分类号：TP18文献标识码：B文章编号：1009-3044(2010)07-1741-02AerialAccessoryFlexibleJopShopSchedulingBasedonMixedPSOAlgorithmWANGChao1,ZHANGYong-qiang2,SHIFeng2

(1.95959Army,Beijing100076,China;2.94565Army,Bengbu233000,China)Abstract:Aerialaccessoryjopshopschedulinghavetheproblemsofthediversityanduncertaintyofitsobjectives,Commonmenthodcan'tgetbestmachiningprocess.MixedPSOAlgorithmisusedoftooptimizemachiningprocess.Thealgorithmiteratestogetbestmach-ingprocessthroughindividualcrossandmutation.Theexperimentshowstheeffectivenessofthealgorithm,providinganewmethodforaerialaccessoryjopshopscheduling.

Keywords:aerialaccessory;fuzzyaim;flexible;jopshopscheduleing;mixedPSO航空零件生产是一个复杂的过程，往往需要经过多个生产车间的加工才能完全加工成型。并且由于各零件的安装顺序不通，对于不同的零件，需求的时间不同。因此在航空零件加工的过程中需要合理分配各零件的加工车间顺序，从而达到合理利用产品制造资源，提高零件加工效率，更好地完成飞机组装线需求的目的。粒子群算法（ParticleSwarmOptimization,PSO）是Kennedy博士和Eberhart博士在1995年提出的一种基于群体智能的优化算法，它源自对鸟类捕食的研究，个体通过竞争搜索完成对复杂搜索空间最优解的搜索。PSO算法虽然具有收敛速度快的特点，但是容易陷入局部最优。混合粒子群算法是标准粒子群算法的改进，该算法摒弃了标准粒子群算法的依靠速度跟踪极值的方法，而是引入了遗传算法中交叉和变异算子，粒子通过和个体极值和群体极值交叉和粒子变异的方法来跟踪极值，寻找最优问题最优解，本文用混合粒子群算法来对车间调度进行优化。1问题模型

1.1调度问题模型

航空零件柔性车间调度问题可以描述为有n个待加工的航空零件要在m(m>2)台机器上加工，已知的参数如下所示[1-2]：

1）机器集M={m1,m2,…mm},mj表示第j台机器，j=1,2,…,m；

2）航空工件集P={p1,p2,…,pn}，pi表示第i个航空工件，i=1,2,…,n；

3）工序序列集OP={op1,op2,…,opn}，opi={opi1,opi2,…,opik}表示航空工件pi的工序序列。

4）可选机器集OPM={opi1,opi2,…,opik}，OPij={opij1,opij2,…,opijk}表示航空工件pi的工序j可以选择的加工机器。

5）使用机器加工工件的时间矩阵T,tij∈T表示第i个工件pi使用第j个机器的时间。

6）使用机器加工工件的费用矩阵C,cij∈T表示第i个工件pi使用第j个机器的加工费用。

并且问题满足下列条件：1）每个工件的每道工序使用每台机器不能多于1；

2）每个工件的加工遵循一定的顺序，只有在前面工序完成后才能进行下一个工序；

3）每个工件的每道工序的生产开始后就不能停顿，直到该工序完成为止。

求解工件加工的排序S，使得所有工件的提交时间和总费用的加权和最小。1.2模糊提交时间

在航空零件的加工过程中，由于加工顺序不同，各零件组装的时间不一样，以最小完工时间作为优化指标并没有意义。因此，本文采用了遵循安装时间不通的模糊提交时间，对于零件pi的交货期，用下面的梯形模糊数来表示：

收稿日期：2010-01-08作者简介：王超（1980-），北京人，助理工程师，空军工程大学飞行器设计专业硕士毕业，研究方向为智能算法，优化组合；张永强（1973-），安徽蚌埠人，工程师，空军工程大学机械工程专业毕业，研究方向为航空维修；史峰（1983-），安徽蚌埠人，助理工程师，空军工程大学航空宇航推进理论与工程专业硕士毕业，研究方向为智能算法，优化组合。

ISSN1009-3044ComputerKnowledgeandTechnology电脑知识

与技术

Vol.6,No.7,March2010,pp.1741-1742,1763

E-mail:kfyj@cccc.net.cnhttp://www.dnzs.net.cnTel:+86-551-56909635690964

1741ComputerKnowledgeandTechnology电脑知识

与技术

计算机工程应用技术本栏目责任编辑：梁书

第6卷第7期(2010年3月)Ti=(ti1,ti2,ti3,ti4)模糊隶属度计算公式如下：

（1）式中，μd(x)表示x属于模糊集Di的隶属程度，其范围为0到1之间的数，这样每得到一个工件的提交时间时，都计算提交时间的模糊隶属度作为该个体适应度值中的提交时间。2混合粒子群算法

2.1混合粒子群算法

粒子群算法是一种群体智能优化算法，它是Kennedy博士和Ebehart博士在1995年提出的。算法首先初始化一群随机粒子，每个粒子都有自己的运动速度，粒子通过跟随个体极值和全局极值更新速度和位置完成寻优过程，粒子寻优的公式如（2）,（3）所示

[3]：

（2）（3）其中，Vkid为粒子速度，Xk，Xk+1是粒子位置，就是问题的潜在解，Pkibest是个体极值，Pkgbest是群体极值，c1和c2是加速度因子；r1和r2

是分布于[0,1]之间的随机数。

标准粒子群算法虽然操作简单，算法能够快速收敛，但是随着迭代次数的不断增加，在种群收敛集中，各粒子也越来越相似，可能在局部解周围无法跳出。因此，本文采用了一种混合粒子群算法，该算法引入了算法中的交叉和变异操作，通过粒子通过和个体极值，群体极值交叉以及只身变异的方法来搜索最优解[4-5]。

2.2个体编码和适应度计算

粒子采用实数编码的方法，每个粒子表示零件在所有机器上的加工顺序，当零件数为n，加工顺序为m时，个体的长度为2*n*m，其中前面表示所有工件的加工顺序，后面表示加工机器序号。

根据每个粒子的编码求解该粒子的适应度值，由于机器的加工数量限制，每一个零件的某一工序投入加工时，首先应该判断加工机器的上一个零件是否加工完，没加工完则等待上一个零件加工完再投入加工。适应度的计算公式如公式4所示：ftness(s)=k1/time(i)+k2*cost(i)（4）

其中，time(i)表示所有任务的提交时间模糊隶属度和，cost(i)表示所有任务所需费用和，k1，k2为系数，fitness(i)为粒子i对应的适应度值。2.3进化算子

混合粒子群算法中的进化算法为交叉和变异，其操作方法如下：1）交叉方法：交叉方法采用整数交叉法，首先选择出全局极值或个体极值的前n*m和个体的前n*m位，然后随机选择交叉位

pos后，将交叉位pos后的加工顺序互换得到新个体，然后对新个体编码的工件重复加工和未加工完的编码进行调整，把重复加工的

工件变化为没有加工完的工件。然后按照旧粒子的机器安排重新排列新粒子的n*m+1-2*n*m位。采用了保留优秀个体策略，只有当新粒子适应度值好于旧粒子时，采用新粒子更换旧粒子。3）变异方法：变异方法采用个体内部两维互换方法，对于变异个体，首选选择变异位置pos1和pos2，然后把个体中pos1和pos2位的加工工序以及对应的加工机器序号对换。同样采用了保留优秀个体策略，只有当新粒子适应度值好于旧粒子时，采用新粒子更换旧粒子。2.4计算步骤

混合粒子群算法优化柔性车间调度问题的计算步骤如下所示：Step1：初始化种群，计算种群适应度值，找到个体最优和群体最优位置；

Step2：粒子进行交叉操作；

Step3：粒子进行变异操作；

Step4：计算新种群的适应度值，更新个体最优和群体最优位置；

Step5：判断迭代是否结束，若否返回Step2。

3仿真实验

采用混合粒子群算法进行航空零件加工模糊车间调度，共有10台机器，6个航空零件，每个零件都有6道加工工序，每个工序可以选择的机器如表1所示。每个零件的加工均需要一定的时间和费用，根据飞机安装时间的需求，每个零件的提交时间满意度遵循不同的模糊隶属度矩阵。采用混合粒子群算法求解该问题，每个粒子有72维整数，前36维表示加工顺序，后36维表示所选机器，种群中共有20个个体，个体通过同最优个体交叉和自身变异寻找新个体。进化次数为50次，最优个体适应度值随进化变化趋势和对应最终优化零件加工甘特图如图1，2所示。（下转第1763页）

表1工序可选机器表

1742