基于混合粒子群算法的混流装配线投产顺序研究及仿真

南 翔，党保华，颉潭成，张朋俊

NAN Xiang1，DANG Bao-hua2，XIE Tan-cheng1，ZHANG Peng-jun1

（1. 河南科技大学 机电工程学院，洛阳 471003；2. 洛阳理工学院 机电工程系，洛阳 471023）

0 引言

随着市场竞争越来越激烈和用户对产品的个性化要求，混流装配线被越来越多的企业采用。在混流装配线上，不同装配工位对不同产品装配的作业时间相差很大，产生闲置和超载现象，装配时所需零部件也不完全相同使装配过程中各种零部件的消耗速率变化很大，导致零部件的需求量产生很大波动。每个工位的闲置和超载时间及零部件的消耗速率与流过这个工位的产品投产顺序有关。因此不同产品的投产顺序直接影响企业的生产效率，解决产品投产顺序成为关键问题。

1 混流装配线投产顺序的数学模型

设装配线上产品类型为M，在计划期内总产量为D，第m种产品的产量为Dm。通常研究产品投产顺序问题时以最小生产循环(MPS)为对象，若Dm的最大公约数为g，则当M种产品以MPS投入装配线时,循环次数为g。以MPS为对象，建立混流装配线投产顺序的数学模型。

1.1 最小化工位的闲置和超载时间

对某一投产序列，在第s个工位上，每一个循环开始时，第一个产品的开始时间Bs,1=0(s=1,2,...,S)。若第k(k=1,2,...,d)个产品的开始时间为Bs,k，则该产品的结束时间Es,k=Bs,k+Ts,k。第k个产品装配结束后，该装配工位装配第k+1个产品。第k+1个产品的加工起点有操作工提前完成装配和未提前完成装配两种情况：

则投产序列的第k个产品在第s个工位上的闲置和超载时间分别为：

则混流装配线投产排序的目标函数：

S：装配线上工作站数目；

Ts,k：MPS中，在第s个工位，第k个产品的装配时间。

1.2 保持均匀的零部件消耗速率

MPS中需要的零件aj(j=1,2,...,J)的数量为pj，那么单位产品中零件aj的平均需求量mj=pj/d。MPS中生产第k个产品需要零件aj的平均数为k.mj。在投产顺序计划中，将k.mj是消耗零件aj的目标值，实际上生产前面k个产品所需零件aj的数量为实际值。要使aj的出现率为恒值，就应该使aj的实际值和目标值尽可能接近。目标函数：

J：装配所需零部件种类数；

d：MPS中所有产品的需求量；

k：MPS中投入的第k个产品；

xm,j：前k个产品中产品m的累积量；

cm,j：单件产品m所需要部件aj的数量。

2 混流装配线投产顺序的数学模型的求解算法

2.1 粒子群算法

粒子群优化算法(PSO)是一种源于对鸟群捕食行为的研究而发明的进化计算技术。最初在二维空间图形化模拟鸟群捕食过程，后来将其推广到维空间。每个优化问题的解是搜索空间中的一只鸟，也看成是一个粒子，每个粒子在搜索空间中以一定的速度飞行，此速度根据自已和其他粒子的飞行经验动态调整。然后定义一个适应度函数来衡量每个粒子解的优劣程度，这样每个粒子就可以根据自己和其他粒子的飞行经验群游，来达到从全空间搜索最优解的目的[1,2]。全局优化模型如下：

其中，Vid是粒子i的速度；Xid是粒子i的位置；pid是粒子i所经历的最好位置（pBest）；pgd是所有粒子所经历过的最好位置（gBest）；W是惯性权重；C1，C2是加速度常数，表示把粒子拉向pBest和gBest的权值；Rand， rand是两个在[0，1]范围变化的随机数。

标准粒子群优化算法的执行过程如下：1）初始化种群，随机产生每个粒子的位置和速度；2）评价每个粒子的适应度；3）对每个粒子，其适应度值与与自身pBest做比较，如果当前值好于pBest，则将当前值设为粒子的pBest；4）对每个粒子，其适应度值与与gBest做比较，若当前值好于gBest，则将当前值设为粒子的gBest；5）调整变化每个粒子的速度和位置；6)如未达到终止条件（预先设定的最大代数或足够好适应度值）则返回2），否则结束[3,4]。

2.2 混合粒子群算法

通常，各个目标函数之间冲突的可能性使得多目标优化问题不存在唯一的全局最优解，使各个目标函数同时达到最优。针于这种多目标优化问题，提出一种混合粒子群算法。该算法在变量空间中初始化种群，各个目标函数共同指导粒子在变量空间中的飞行，飞行过程中对粒子的全局极值和个体极值的选取做了改进。混合粒子群算法的基本思想如下：

1）参照遗传算法编码的思想，给出粒子的构造方法。

2）对各个目标函数对应粒子个体极值的选取做了改进。各个目标函数个体极值的选取过程中，结合遗传算法交叉操作思想，先将初始种群的粒子与各个目标函数个体极值交叉，产生两个新的种群，再将这两个新的种群与初始种群合并成新的种群，按照各个目标函数的适应度值大小从种群中选取规模同初始种群相同的种群，重新计算各个目标函数的个体极值。

3）对粒子的全局极值和个体极值的选取做了改进。首先找到每个粒子对应于各个目标函数的全局极值和个体极值；其次，在更新每个粒子的速度时，用各个粒子全局极值的均值作为全局极值，若个体极值的离散程度小于全局极值的离散程度，个体极值随机取各目标函数个体极值，反之，个体极值取各目标函数个体极值的均值。

若MPS对应9个产品，借鉴遗传算法中实数染色体的编码方法，粒子构成有九维[5,6]。把A型绑定1，2，3位置，B型绑定4，5，6，7位置，C型占据绑定8，9位置，对每个粒子中的每维值进行排序，根据排序的序号和对应的位置，可以映射出一个对应产品型号的排序方式。粒子构架图如表1所示。

表1 粒子构架图

为了增加各个目标函数对应粒子个体极值的收敛速度及防止其陷入局部最优，通过遗传算法的两点式随机交叉增加种群规模来克服，同时更新种群。在更新粒子速度时，本文的选取方式使得每个粒子向解移动时的行为各不相同，每个粒子都移向解区域中不同的解。选取避免了所有个体落于某一目标函数的最优点，体现了各个目标函数间的制约关系[5,6]。

3 实例分析

对某一发动机混流装配线，在计划期内，要生产300件A，400件B，200件C，生产节拍为105s，零件p11，p12，p21，p22的供应节拍分别是24s，30s，22s，20s。以装配线的两个关键工位为研究对象，则在MPS中，不同产品的数量，零件使用情况和工位装配时间如表2所示。表2中m表示产品类型，dm表示不同产品的数量，psj表示在工位s每种产品需要零部件j的数量，其中tsj表示在工位s每种产品装配一个零部件j所需要的时间。

表2 各种发动机需要零件数及装配时间

为了将混合粒子群算法运用到产品投产顺序的优化问题上，需要对微粒的位置和速度做出重新定义。设一个MPS中有d个产品，不妨设某个位置X=(x1,x2,...,xd)，该位置的速度为V=(v1,v2,...,vd)。运用上文提出的粒子构架方式构造粒子。针对本文提出的两个目标函数J1，J2，运用混合粒子群算法，算法流程如下：

1）设定种群数40，最大循环代数30代，给定参数C1=C2=2，当前代数gen=0，随机产生每个粒子的位置与速度；

2）用目标函数J1，J2分别计算每个粒子的适应度；

3）针对两个目标函数J1，J2分别对每个粒子求得个体极值pBest1，pBest2，令pop再与pBest1，pBest1进行交叉，产生粒子群pop1，pop2,将pop和pop1，pop2合并；

4）用目标函数J1，J2分别计算合并后种群每个粒子的适应度值，适应度值分别按升序排列，选择对应两个目标函数适应度值都小的粒子，构成新的种群newpop，种群大小不变；

5）针对目标函数J1，J2对每个粒子重新求得个体极值pBest11， pBest22，计算每个粒子在两目标函数下个体极值的差值；

6）针对两个目标函数J1，J2分别求两个全局极值，计算两全局矢量的均值和距离，全局极值取两全局极值的平均值；

7）若个体极值的差值小于全局极值的差值，个体极值取两个目标函数任一个体极值。若个体极值的差值大于等于全局极值的差值，个体极值取两个目标函数个体极值的平均值；

8）由6）和7）求得全局极值和个体极值和公式调整粒子的速度和位置；

9）gen=gen+1，是否达到最大循环代数，如果满足结束条件，则结束搜索，否则转入步骤2)；

10）输出最后一代粒子群中的全局最优解gBest。

在VC++平台上运行程序，求得最佳排序BACBABCAB。

4 用AutoMod软件仿真验证

建立发动机装配线在投产顺序BACBABCAB下的仿真模型，运行8个小时。图1是发动机模型运行时的效果图，产品按照BACBABCAB投产顺序循环装配。sta1，sta2分别代表工位1，工位2。每个工位旁边有两个队列，零件以一定节拍进入队列，等待操作工把零件装配到不同产品上。

图1 模型运行时的效果图

图2 零件实际使用值与目标值的动态图

由图2可以看出，图形右侧有8个参数，参数C_11.Cur、C_12.Cur、C_21.Cur、C_22.Cur分别表示零件p11、p12、p21、p22的实际使用量；参数V1、V2、V3、V4分别表示零件p11、p12、p21、p22的目标使用量。由图3可知，每个零件目标值与实际值的曲线比较接近，随时间变化目标值与实际值之间的差值增加。目标值与实际值之间的差值的变化从另一个角度反映队列中库存量的变化。库存量达到一定量时，可以采取措施，减慢或者加速零件的供应速度。

图3 工位闲置和超载时间的动态图

从图3看出装配线运行一天，装配线的工位闲置和超载时间大约是1000s。另外从该仿真模型中还可以得到操作工R1的利用率为90%，操作工R2的利用率为98.3%。选3种投产顺序方案：A B A C B C B A B，C A B A C B A B B，BCBABCABA。分别对这几种投产方案仿真运行并与求得的方案对比。三种方案工位闲置和超载时间分别是1273s，1530s，1420s均大于1000s，并且操作工的利用率都不及求得的方案。所以方案BACBABCAB是最佳排序方案。

5 结论

本文通过把粒子群算法与遗传算法编码交叉的思想相结合，利用最优解评估选取方法，改进个体极值和全局极值的选取办法，提出了混合粒子群算法。用该算法解决了混流装配线投产顺序的多目标优化问题，得到了较优的可行解。并用AutoMod仿真验证，证明了该算法求解混流装配线投产顺序的有效性以及AutoMod仿真混流装配线投产顺序的可行性。

本文作者创新点：通过改进个体极值和全局极值的选取解决混流装配线投产顺序的多目标优化问题；用AutoMod仿真混流装配线的投产顺序，验证算法的有效性，证明AutoMod仿真混流装配线投产顺序的可行性，为简化数学基础奠定了基础。

[1] 林献坤,等.混合粒子群算法在混流装配线优化调度中的应用[J].工业工程与管理,2006(1)：35-39.

[2] 刘亚欣,等.基于粒子群算法的数据库查询优化[J].微计算机信息,2007(3)：7-11.

[3] 苏平,等.基于混合遗传算法的混合装配线排序问题研究[J].计算机集成制造统,2008(5)：14-19.

[4] 曹振新,等.混流装配线负荷平衡与投产排序的优化研究[J].信息与控制,2004(6)：33-38.

[5] 张利彪,等.基于粒子群算法求解多目标优化问题[J].计算机研究与发展,2004 (7)：41-45.

[6] 赵建军,等.基于Flexsim混流装配线投产排序的仿真[J].控制与管理,2007(3)：8-11.