基于改进蛙跳算法的可重构装配线调度研究

，，，

(浙江工业大学 机械工程学院,浙江 杭州 310014)

近年来，制造企业都面临着许多变化，在一个动态的市场环境中，企业需要新的生产条件来满足市场个性化需求和市场的快速转换，所以我们希望尽量减少制造系统和设备的投资，减少转换所需的准备工作，提高产品质量，增强在竞争激烈的市场的适应能力.因此，需要一种制造组装线，来提供快速，有效的可重新配置的功能.在这种情况下，可重构装配装配线调度有一个很现实的理论和实践意义.

可重构装配线(Reconfigurable assembly line，RAL)[1-2]是一类基于现有的装配线基础结构，重建和改变该装配线的各种结构，并调整装配线的现有功能和装配能力，来满足市场需求变化.Ding等[3]研究使用的生产计划周期P和品种k的可重构装配生产线调度和生产计划问题，首先提出了两个阶段的方法，就是，所有的产品周期率的平衡式及平衡部件的消耗率和使用速率.Kubiak[4]可重构装配生产线计划进行全面阐述讲解，但提出方法是难以满足实际的调度的要求，尤其是当规模的问题大的和非常复杂的.黄雪梅等[5]的agent和holon混合想法代理提供基于可重构装配生产线和其他基础设施，以实现的基本结构理论的分析，并提出了数字化制造技术下的结构信息可重构装配生产线仿真平台.余剑锋[6]可重构制造系统调度优化过程中，具有系统的自我分析，以及其他相关功能，并且保持一定程度的灵活性和可重构性.分析现有的研究，大多是单一的装配生产线调度目标优化，但可重构装配生产线，简单的优化目标，难以满足实际需要，因此需要研究和组合更多的装配线调度优化的目标，以及为重新构装配线多目标优化提出一个典型的组合优化模型.数学编程方法可以解决一些问题但局限性较大，目前迫切需要一种新的高效算法解决去可重构装配线多目标调度问题.

1 可重构装配线调度问题描述

1.1 可重构装配线

刚性装配线的产生，以适应高容量，高生产效率的装配系统，但缺乏灵活性.柔性装配线提供了冗余能力和生产能力，实现了系统的灵活性，但是其昂贵的系统及硬件投资是一个重要制约因素.可重构制造系统的可重构装配装配线是其一个非常重要的部分，它将被应用到可重构制造装配系统中，以建立本地和全局化的模块化、自动化生产的系统，让系统具有灵活的生产能力，快速反应能力和可重构能力.

1.2 可重构装配线调度模型描述

注，这项研究是基于以下假设[8]：1)各类产品通过每个可重构装配顺序装配生产线工作站；2)可重构装配线工作站成立的每一块设备，产品的标准处理时间已确定；3)如果一个任务需要多个处理设备，每个设备具有相同的生产容量；4)工人完成上一产品处理后，返回到下一单元产品的时间可以忽略不计.

2 调度的目标函数设计

可重构装配生产线，以反映调度负载均衡，产生平滑和低成本的生产理念，因此根据具体的工厂现状，可同时考虑最小重构装配线成本、最小零部件需求变化率、最小延误工作量三个优化目标，建立各目标函数.

2.1 最小重构装配线成本

假定在可重构装配线上[7]，线上有r个工作站，这些不同的工作站组成了一个集合Jw，Jw= {1,2,…,r}.且这些线上工作站的长度为Lj(j=1,2,…,r)，平顺匀速的皮带连接着各个工作站，并且传送速度为vc，产品投产到可重构装配线上是以固定的周期tc，tjB为工作时间，特指制品j在工作站B上；在装配区间里，Eij为第i个制品进入第j个工作站的后，工人开始装配过程中所需要的行走距离；E1j为制品开始投产的初始工人行走距离，且E1j=0.

为了调度在不同的生产工艺流水线中的可重构装配线，往往是对设备，工具和装夹设备等进行各种调整，甚至有时需要重建整个装配生产线，因此调整的成本是不同的.因为制造业的低率润，所以应将最小重构装配线成本作为最重要的调度目标来考虑.给出了一个最小重构装配线的数学模型，并运用到实际生产中，其目标函数为

(1)

其中：Cjmn为在工作站j这个范围内，由装配类型m转变成n时所需要的调整总费用；N为制品类别为n时总数量.

2.2 最小零部件需求变化率

可重构装配线调度要满足的另一个重要目标就为生产的顺滑和稳定性，就是要求装配线对各种配件需求变化率小.引用Toyota公司经典调度目标函数[9]，构建相应模型为

(2)

其中：i为制品的约定标识号；P为线上需求的零配件类别总数目；p为调度中子装配的铭号；βi，p为在调度过程中，前i-1的位置总消耗零配件p的总和；K为装配线上制品类别的总数目；k为制品型号数的标识号；dk为在一个生产循环中型号k的数目；αp为零配件p的理想消耗速率；βkp为制造产品型号k时，需要的零配件p的数目之和.

2.3 最小延误工作量

可重构装配线最小延误工作量[10](包括工人等待时间可转换成的工作量和产品过多投入而不能完成的工作量)，其可以反映装配线效率高低和工人的劳动强度率，其目标函数为

(3)

(4)

(5)

其中：I为一个生产循环中需要装配的产品总数量；J为工作站总数；W1为工人等待时间可转换的工作量；W2为产品过多投入而不能完成的工作量.

在现有算法中，通常将多个目标糅合成一个目标，虽然这样操作可以得到一个显而易见的结果，但也将弱化各个目标各自的实际意义.并且，由于糅合方法的无标准性和各个企业的独特性，糅合将导致调度结果的失真[11],所以给出的为一个非劣解集，决策者可以根据企业实际调度情况来选择合适的调度方案.

约束条件如下：

1) 最小重构装配线成本目标函数约束：

(6)

(7)

(8)

(9)

(10)

其中：式(6)为制品位置固定约束，确保制品在生产排序中，某个位置只被分配某一种制品；式(7)和式(8)保证不断循环这个过程中，维持原先预设的调度方式；式(9)为满足MPS要求；式(10)为一个布尔变量.

2) 最小零部件需求变化率目标函数约束：

(11)

(12)

(13)

(14)

其中：式(11)为在生产中，某一个时间段时间内，一个站只能生产一种制品；式(12)为确保一种制品的最小MPS.

3) 最小延误工作量目标函数约束：

(15)

(16)

(17)

其中：式(15)为为在生产中，某一个时间段时间内，一个站只能生产一种制品；式(16)确保一种制品的最小的MPS.

3 求解模型的SFLA-PSO优化算法

3.1 算法的流程

步骤1初始化青蛙种群的数量n和每个种群青蛙的个数m(即可行解)这两个算法的基础参数，并且每个青蛙个体的维数为D，因此，总的初始青蛙个数就为F=mn，最大迭代次数Tmax，加速常数c1和c2[12].

步骤2通过启发式算法(EH，SPT与EDD)产生三个高质量解和以随机方式构造的共F个初始解.

步骤3逐个计算种群内青蛙个体的适应度值，并从当中得到种群的最优解Pg，然后在全群体中进行更新.

步骤4把经过适应度值计算过后的青蛙个体皆分配到m个种群当中，来实现基于PSO算法的局部搜索[13].

1) 通过粒子群算法中的个体更新策略来更新最差青蛙PW的位置；

2) 对新产生的青蛙个体与旧的青蛙个体进行比较，区分优劣，选择优秀进行保留；

3) 循环进行蛙群种群内部局部搜索，达到预设的迭代次数为止，则进行步骤5.

步骤5判别是否已经满足预设优化条件(理想的适应值大小或预设的最大迭代次数)，若已达到，则要输出全群体最优解.否则需循环步骤3到4.

改进蛙跳算法求解多目标可重构装配线调度流程如图1所示.

3.2 算法的具体设计

在求解大规模非确定性困难问题(NP-hard)上，通过蛙跳算法，具有良好的表现，其进化方程描述为

Si=rand()(Pb-Pw)

(18)

Pw(k+1)=Pw(k)+Si

(19)

Smax≥Si≥-Smax

其中：rand()∈[0，1](k=1，2，…，n)；Smax为最大步长.且针对多目标可重构装配线调度问题，建模出了基于三个较不关联和重要的目标的可重构装配线数学调度模型，并提出了一种基于蛙跳算法的多目标改进算法综合运用了非劣解存放于精英解集当中，并结合小生境法维护精英解集，从而使精英解集稳定.用三种启发式算法得到高质量初始解[14].该算法在工厂实例进行测试，通过与其他多目标算法的结果对比分析，验证了算法求解的高效性.

图1 改进蛙跳算法求解多目标可重构装配线调度流程图

1) 个体编码

运用了随机编码(Smallnest position value，SPV)[15]方式来确定连续青蛙个体的位置，表示为Xi={xi，1，xi，2，…，xi，n}，蛙个体对应到一个随机的加工顺序π=(j1，j2，…，jn).表1为制品加工顺序和编码中位置矢量的关系[12].

解得工件排序π=(3，5，6，4，2，1).

2) 初始化

采用启发式算法和随机方式两种方式来产生初始解，EDD，NEH与SPT算法可产生三个较高质量的初始解，剩余的解随机产生.

3) 小生境法保护精英解集

精英解集保护用小生境法[12]，每一代生产的非劣解将进入精英解集之中，且删除相互关联解.如果超过解集容量，则使用小生境法逐个计算，按照计算值排序，删除小值.适应度计算方法为

(20)

(21)

(22)

(23)

其中：F(p)为p的适应度值；a为常数；Q为非劣解的个数；σshare为小生境半径；sh(dpq)为个体p和q的共同享用数；dpq为两蛙体间向量距离.

4) 蛙群多样性

采用青蛙个体间的支配关系与密度联系结合来确定适应度值.先要将蛙群体内所有非支配解按聚集距离值降序排列，求得解排序P1=(P1,P2,…,PL)，L为群体中非支配解的数量.

聚集距离P[i]distance计算式为

(24)

然后计算群体中支配的解和其距离最相近的非支配解，在解维度中的欧氏距离D[i]distance，且按照升序得到序列P2=(PL+1,PL+2，…,PF).按个体顺序合并成两个序列P1和P2，最终得到初始解个体排序集合P={P1,P2}=(P1,P2,…,PF)接着划分到M个种群中，每个种群中有N个青蛙.

(25)

5) 基于PSO的局部搜索过程

针对调度解个体中无明显关系，同时结合了粒子群算法中的粒子更新策略，提出了新的个体更新方法.种群内采用的搜索方法[15]如下：

步骤1确定最优蛙体为Pb、最差蛙体为Pw、种群最优蛙体为Pg，且Pb对应种群Y1，Pw对应种群YN.且要从精英解集中获得Pg，来引领解的进化方向.

步骤2利用PSO算法的个体更新策略，变换Pw的运动速度和位置，用Pb替代历史最好位置的个体，个体更新计算式为

Xw=c1rand1()Vid+c2rand2()(Pb-Xw)

(26)

Xw=Xoldw+Xw

(27)

其中：rand1()，rand2()分别为[0，1]之间的随机数.

步骤3对比新产生的个体与旧个体的好坏，取优.

步骤4继续进行局部种群内搜索，直到满足预定迭代的次数为.

4 实际案例验证分析

YYFJ为一家专业生产各类吸尘器及其附件的公司.现在客户需求逐渐由少品种大批量转变为多品种小批量的形式，客户的订单量大小及品种差异很大，为在激烈的市场竞争中生存，所以制定一个合理的可重构装配线调度方案对于企业来说为意义重大.本案例采用YYFJ产值和产量最高的第四车间PTVL1的可重构装配线，2013年7月份生产计划进行仿真实验.

采用Matlab编写了算法程序，该生PT产线生产6种类型的产品，其产品型号和月生产计划如表2所示，以下表中产品数量和产品所需要的零件数都基于MPS取值.

表2 PTVL1生产线2013年7月份生产计划

基础参数值:vc=1,tc=15,m=10,n=50,c1=c2=2.0，w=9，Tmax=200；计算的基础数据见表3—5.

表3 各产品所需求的子装配零件数量

采用提出的进蛙跳算法算法对该装配线进行调度优化，所求出的Pareto非劣解集平均值与现有调度方案产生的目标值比较如表6所示，Pareto非劣解集分布仿真图如图2所示.

表4 各工作站的装配时间和长度

表5 不同种类产品转换时的调整费用

表6较为清晰的表明了改进的蛙跳算法而得到的目标值较明显优于原有方案，这也证明了算法的有效性和适应性.由图2可看出：pareto非劣解集分布的聚集性，从而也可得出算法有效性的结论.

表6 Pareto非劣解集平均值与现有调度方案产生的目标值比较

图2 Pareto非劣解集分布仿真图

5 结 论

研究了可重构装配线调度存在的主要问题[7]，从而提炼出了影响其调度的三个主要因素，即最小重构装配线成本、最小零部件需求变化率、最小延误工作量，根据这三个目标，建立了调度模型，而且提出了基于改进蛙跳算法的可重构装配线调度优化算法.该算法综合运用了SPV规则编码、启发式算法和随机方式初始化、自适应小生境的精英解集维护、结合粒子群算法中的粒子局部更新策略保证蛙群的多样性，很好避免了算法过早限于布局极值，且对蛙群整体寻优能力进行了改善，并以某吸尘器企业的一条可重构装配线为实际案例，运用提出的算法模型进行了仿真实验，与现有调度方案进行了对比.仿真结果表明：该算法求出的Pareto非劣解平均值优于现有调度方案较多，从而验证了该算法的有效性和可行性.

参考文献：

[1] KOREN, HEISEL U, JOVANE F, et al. Reconfigurable manufacturing systems[J]. Annals of the CIRP,1999,48(2):527-540.

[2] MEHRABI M G, ULSOY A G, KOREN Y. Reconfigurable manufacturing systems: key to future maufacturing[J]. Journal of Intelligent Manufacturing,2000,1(1):113-130.

[3] DING F Y, TOLANI. Production planning to support mixed model assembly[J]. Computer&Industrial Engeering,2003,45(1):375-392.

[4] KUBIAK W. Minimzing variation of production rates in just in time systems: a survey[J]. European Joumal of Operational Research,1993,66(3):259-271.

[5] 黄雪梅,肖田元.智能可重构汽车变速器装配生产线制造系统研究[J].机械科学与技术,2009,25(4):403-406.

[6] YU Jian-feng, YIN Yue-hong, Shen Xin-jun, et al. Modeling strategies for reconfigurable assembly system, Assembly Automation[J]. Assembly Automation,2003,13(3):266-272.

[7] 苑明海,白颖,李东波.可重构装配线多目标优化调度研究[J].中国机械工程,2008,19(16):1898-1903.

[8] 李富明;刘江峰.一种基于工作站Petri网模型的混流装配线重构方法[J].广西大学学报:自然科学版,2012,37(6):1204-1210.

[9] 朱剑英.现代制造系统模式、建模方法及关键技术的新发展[J].机械工程学报,2000,36(8):1-5.

[10] 苑明海.可重构装配线建模、平衡及调度研究[D].南京：南京理工大学，2008.

[11] 陈勇,阮幸聪,王亚良.基于元胞机的大型机械构件生产车间柔性调度求解[J].浙江工业大学学报，2011,39(4)：433-439.

[12] 郑章元.蛙跳算法及其在置换流水车间调度中的应用研究[D].武汉：华中科技大学，2011.

[13] 贺毅朝，曲文龙，许冀伟．一种改进的混合蛙跳算法及其收敛性分析[J]．计算机工程与应用，2011,47(22):37-40.

[14] CHUNG G, LANSEY K. Application of the shuffled frog leaping algorithm for the optimization of a general large-scale water supply system[J]. Water Resources Management,2009,23(4):797-823.

[15] 赵晓波,张鸣,罗振壁,等.可重组FMS中缓冲区容量的优化配置问题[J].系统工程学报,2000,15(2):158-162.

[16] 胥小波,郑康锋,李丹,等.新的混沌粒子群优化算法[J].通信学报,2012,33(1):24-37.